Parallelize the lock BFS safely
Overview
This question evaluates a candidate's ability to design and reason about concurrent algorithms, including parallel BFS, synchronization, thread-safe data structures, partitioning strategies, and correctness guarantees for shortest-path searches.
Snapchat
Jul 31, 2025, 12:00 AM
Software Engineer
Technical Screen
System Design
0
0
Parallelizing BFS for the Rotating-Lock Problem
Context
You are given the classic rotating-lock problem (e.g., a 4-wheel lock from "0000" to a target like "0202" with deadends). In the single-threaded solution, we use BFS over the implicit state graph where each state has up to 8 neighbors (turn each wheel +1 or −1 mod 10). The goal is to find the minimum number of moves.
Assume:
- State space size is at most 10,000 (for a 4-digit lock with digits 0–9).
- There is a set of deadend states to avoid.
Task
If multiple threads are available, design a parallel BFS for this problem. Describe:
- How to partition work across threads.
- How to maintain BFS level ordering (if required for shortest-path correctness).
- How to implement a thread-safe visited set and queues.
- How to prevent duplicate exploration across threads.
- Trade-offs: contention, memory overhead, determinism, and when to prefer one approach over another.
Solution
Login required
Show