Meta·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026Remote

Summary

Meta SWE coding round, one problem the whole session. They took a classic BFS maze and layered on keys and locked doors, which sounds manageable until you realize your state space just tripled in complexity. Felt okay about my solution but not great.

Questions Asked (1)

You have a working BFS maze solver on a 2D grid with walls, open cells, a start S and end E. Now extend it: the grid has keys (lowercase letters) and locked doors (uppercase letters). You can only pass through a door if you already hold the matching key. Design a state-augmented BFS where each state tracks position plus which keys you currently hold, and find the shortest path from S to E.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to just track visited cells like normal BFS and I immediately started coding that before catching myself.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Explain that the state space expands from (row, col) to (row, col, key_mask), where key_mask is a bitmask of collected keys. Then describe a BFS over these states, where transitions depend on whether a door can be unlocked with the current key_mask. Finally, discuss how to track visited states and reconstruct the shortest path.

Pro tip: Emphasize that the key_mask is a compact representation of collected keys and that BFS remains optimal because all edges have unit weight. Also, mention that the state space is at most rows*cols*2^K, which is manageable for small K.

1. Define the augmented state

Represent each state as (r, c, key_mask), where key_mask is an integer bitmask of collected keys. Map each key letter to a bit index (e.g., 'a' -> 0, 'b' -> 1).

2. Initialize BFS

Start from S with key_mask=0. Use a queue for BFS and a visited set (or 3D boolean array) to avoid revisiting states.

3. Define transitions

From a state, explore four directions. If the neighbor is a wall, skip. If it's a door, only proceed if the corresponding key bit is set in key_mask. If it's a key, update key_mask by setting the bit.

4. Track path and termination

Store parent pointers or distances to reconstruct the path. When E is reached, return the distance (or path). If BFS exhausts all states without reaching E, return -1.

5. Analyze complexity

Time and space complexity are O(R*C*2^K), where K is the number of distinct keys. This is efficient for small K (e.g., K ≤ 10).

Key Points to Mention

State augmentation with key bitmask to track collected keys.
BFS guarantees shortest path because all moves have equal cost.
Visited set must include key_mask to avoid cycles and redundant work.
Handling doors: only pass if key bit is set; otherwise treat as wall.
Handling keys: update key_mask when stepping on a key cell.
Complexity: O(R*C*2^K) time and space, where K is number of keys.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.