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 rotating-lock BFS with blockers | Snapchat Coding Question

Solve rotating-lock BFS with blockers

Company: Snapchat

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given a 4-digit lock starting at "0000". In one move, you may pick a single position and rotate it +1 or −1 with wrap-around (0→9 on −1, 9→0 on + 1). Given a target combination and a list of forbidden combinations (you cannot enter these states), return the minimum number of moves required to reach the target from "0000", or −1 if it is impossible. Implement an efficient solution and write unit tests covering: target equals "0000"; forbidden includes "0000"; unreachable targets; duplicate entries in the forbidden list; and large forbidden sets.

Quick Answer: This question evaluates a candidate's understanding of state-space modeling, shortest-path search strategies, and constraint handling when navigating combinatorial configuration spaces.

You are given a 4-wheel combination lock starting at the string "0000". Each wheel shows a single digit 0-9. In one move you may pick exactly one wheel and rotate it by +1 or -1 with wrap-around: rotating up from 9 yields 0, and rotating down from 0 yields 9. You are given a `target` combination (a 4-character string) and a list `forbidden` of combinations (4-character strings) that the lock can never display — if any single move would put the lock into a forbidden state, that move is illegal. The lock also cannot start in or pass through a forbidden state. Return the minimum number of moves required to reach `target` starting from "0000", or `-1` if it is impossible. The `forbidden` list may contain duplicates, may include "0000", and may be large. Because every move has unit cost, breadth-first search over the 10000-state space finds the shortest path. Mark "0000" reachable only if it is not forbidden; from each state, generate the 8 neighbors (each of the 4 wheels turned both directions), skipping forbidden and already-visited states. Method: openLock(target, forbidden) -> int.

Constraints

target is a 4-character string of digits '0'-'9'.
Each forbidden entry is a 4-character string of digits '0'-'9'.
0 <= len(forbidden) <= 10000 (it may exceed the number of distinct states; duplicates are allowed).
Wrap-around: '0' rotated down becomes '9'; '9' rotated up becomes '0'.
The lock may not occupy any forbidden state, including the start '0000'.
Return -1 when the target cannot be reached.

Examples

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

Expected Output: 6

Explanation: The direct routes through 0201/0102 are blocked, so BFS detours around the deadends and reaches 0202 in 6 moves.

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

Expected Output: -1

Explanation: All 8 neighbors of the target 8888 are forbidden, so the target is completely walled off and unreachable: -1.

Input: ("0000", [])

Expected Output: 0

Explanation: The lock already shows the target, so no moves are needed.

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

Expected Output: -1

Explanation: The start state 0000 is itself forbidden, so the lock can never make a legal first move: -1.

Input: ("0001", ["0001", "0001", "0001"])

Expected Output: -1

Explanation: Duplicate forbidden entries collapse to {0001}; the target is forbidden, so it can never be entered: -1.

Input: ("9999", [])

Expected Output: 4

Explanation: Each wheel goes 0 -> 9 in a single downward wrap move, so four wheels take 4 moves total.

Input: ("0009", [])

Expected Output: 1

Explanation: Only the last wheel moves, 0 -> 9 via one downward wrap, for a single move.

Hints

Every move costs exactly 1, so the shortest sequence of moves is the shortest path in an unweighted graph — use BFS, not DFS or greedy.
Put the forbidden list into a hash set first so membership tests are O(1) and duplicates collapse automatically. Check the start state against it before doing anything.
From a state, the 8 neighbors are each of the 4 wheels turned up and down; use (d + 1) % 10 and (d - 1) % 10 (the latter wraps 0 to 9) to compute the new digit.
Track visited states so you never re-enqueue one; skip any neighbor that is forbidden or already visited. If the queue empties without hitting the target, return -1.

Quick Overview

This question evaluates a candidate's understanding of state-space modeling, shortest-path search strategies, and constraint handling when navigating combinatorial configuration spaces.