Keys and Rooms

Keys and Rooms

1. What is this problem about?

The Keys and Rooms interview question is a graph reachability problem. There are $N$ rooms, and you start in room 0, which is unlocked. Each room has a list of keys to other rooms. Your goal is to determine if you can eventually visit all the rooms.

2. Why is this asked in interviews?

Companies like Microsoft, Meta, and Nvidia use the Keys and Rooms coding problem to test a candidate's knowledge of basic Graph Traversal. It tests if you can correctly identify a directed graph structure and implement BFS or DFS to find all reachable nodes. It’s a core Graph interview pattern.

3. Algorithmic pattern used

This problem is a direct application of Depth-First Search (DFS) or Breadth-First Search (BFS).

1. Initialization: Use a boolean array visited of size $N$, and mark visited[0] = true.
2. Traversal: Use a stack (DFS) or queue (BFS). Start with room 0.
3. Explore: While the structure is not empty:
   • Pop a room.
   • For every key in that room, if the corresponding room hasn't been visited:
     • Mark it as visited and add it to the structure.
4. Conclusion: After the traversal, check if all values in the visited array are true.

4. Example explanation

rooms = [[1], [2], [3], []]

1. Start in room 0. Get key [1].
2. Visit room 1. Get key [2].
3. Visit room 2. Get key [3].
4. Visit room 3. No keys.
5. All rooms (0, 1, 2, 3) visited. Result: True. If rooms = [[1, 3], [3, 0, 1], [2], [0]], room 2 is isolated (only has a key to itself, but no one has a key to it). Result: False.

5. Common mistakes candidates make

• Missing rooms: Only checking keys from room 0 and forgetting that room 1's keys might unlock room 2.
• Infinite Loops: Not using a visited set, which leads to cycles (Room 0 unlocks 1, Room 1 unlocks 0).
• Efficiency: Using a list and contains() instead of a boolean array or set for the visited check.

6. Interview preparation tip

Reachability in a graph is always solved by BFS or DFS. Practice implementing these iteratively, as they are more robust than recursive solutions for graphs with thousands of nodes. This is a fundamental Graph interview pattern.