How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snapchat.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snapchat during technical interviews.

Solve Open the Lock BFS | Snapchat Coding Question

Solve Open the Lock BFS

Company: Snapchat

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question LeetCode 752. Open the Lock – Given an initial lock state "0000", a target combination, and a list of deadend combinations that cannot be used, each move rotates one digit ±1 (with wrap-around), find the minimum number of moves to reach the target. https://leetcode.com/problems/open-the-lock/description/

Quick Answer: This question evaluates the ability to model the lock as a state-space and apply graph traversal and shortest-path techniques (breadth-first search) to determine minimal move sequences under constraints.

You have a lock with 4 circular wheels. Each wheel has 10 slots: '0'..'9'. The wheels rotate freely and wrap around: '9' -> '0' and '0' -> '9'. Each move turns exactly one wheel one slot (±1). The lock starts at "0000". You are given a list of `deadends` — combinations that, if any wheel is ever set to such a value, will jam the lock so it can never be opened from there. You are also given a `target` combination. Return the minimum total number of moves required to turn the lock from "0000" to `target`, or -1 if it is impossible. Function signature: `solution(deadends, target)` where `deadends` is a list of 4-character strings and `target` is a 4-character string.

Constraints

1 <= deadends.length <= 500
Each deadends[i] and target has exactly 4 digits ('0'..'9').
Each move turns one wheel by ±1 with wrap-around ('9'->'0', '0'->'9').
If "0000" is itself a deadend, the lock can never move and the answer is -1.
target may equal "0000" (answer 0).

Examples

Input: (["0201", "0101", "0102", "1212", "2002"], "0202")

Expected Output: 6

Explanation: A valid 6-move sequence is 0000 -> 1000 -> 1100 -> 1200 -> 1201 -> 1202 -> 0202. Note 0102 is a deadend, so the more direct route 0000 -> 0001 -> 0002 -> 0102 ... is blocked, forcing the longer 6-move path.

Input: (["8888"], "0009")

Expected Output: 1

Explanation: Turn the last wheel down once: 0 -> 9 wraps around, so 0000 -> 0009 in a single move. The deadend 8888 is never on the path.

Input: (["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"], "8888")

Expected Output: -1

Explanation: Every one of the 8 neighbors of 8888 is a deadend, so 8888 is fully surrounded and can never be reached from 0000.

Input: ([], "0000")

Expected Output: 0

Explanation: The lock already starts at the target, so zero moves are needed.

Input: (["0000"], "8888")

Expected Output: -1

Explanation: The starting combination 0000 is itself a deadend, so the lock is jammed before any move can be made.

Input: ([], "9999")

Expected Output: 4

Explanation: Each of the 4 wheels needs exactly one move because 0 wraps directly to 9 in a single ±1 turn, giving 4 total moves with no deadends to avoid.

Hints

Model each 4-digit combination as a node in an unweighted graph; an edge connects two combinations that differ by a single ±1 wheel turn. Minimum moves on an unweighted graph = shortest path, which is exactly what BFS finds.
From any state, generate its 8 neighbors by turning each of the 4 wheels up and down by one, using modulo 10 for wrap-around (so digit 9 goes to 0 and 0 goes to 9).
Treat deadends as blocked nodes you may never enter (skip them when expanding), and use a visited set so you never revisit a combination. Handle the edge cases first: if "0000" is a deadend return -1, and if target == "0000" return 0.

Quick Overview

This question evaluates the ability to model the lock as a state-space and apply graph traversal and shortest-path techniques (breadth-first search) to determine minimal move sequences under constraints.