Meta·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

Meta SWE coding round with a stateful BFS maze problem. The twist was managing key collection state alongside position, which made the standard visited-set approach fall apart pretty quickly.

Questions Asked (1)

Given a 2D maze with walls, a start, an exit, open cells, keys (a-f), and locked doors (A-F), find the minimum number of steps from start to exit. A door can only be passed if you're carrying the matching key. Return -1 if the exit is unreachable.

Algorithms & Data Structures

Author's notes

My first instinct was plain BFS and I started coding it before really thinking about what 'visited' means here.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a shortest path search in a state space where each state is (row, col, keys_bitmask). Use BFS to explore states level by level, updating the key bitmask when picking up keys and only passing through doors if the corresponding key bit is set. Return the distance when reaching the exit, or -1 if BFS exhausts all reachable states.

Pro tip: Emphasize that the state space is bounded by rows * cols * 2^6 (since there are at most 6 keys), making BFS efficient. Also, mention that you can optimize by not revisiting states with the same position and key set, and consider using a queue with distance tracking.

1. Define State Representation

Represent each state as (row, col, keys_bitmask) where keys_bitmask is a 6-bit integer indicating which keys (a-f) have been collected. This captures all necessary information to determine possible moves.

2. Initialize BFS

Start BFS from the initial position with an empty key set (bitmask 0) and distance 0. Use a queue to process states in order of increasing distance.

3. Explore Neighbors

For each state, consider all four adjacent cells. If the cell is a wall, skip. If it's a door (A-F), only proceed if the corresponding key bit is set. If it's a key (a-f), update the bitmask by setting the appropriate bit.

4. Track Visited States

Maintain a visited set (or 3D boolean array) to avoid revisiting the same (row, col, keys_bitmask) state. This ensures BFS terminates and runs in O(rows * cols * 2^6) time.

5. Return Result

When the exit cell is reached, return the current distance. If BFS completes without reaching the exit, return -1.

Key Points to Mention

State space includes position and key set, leading to at most rows * cols * 64 states.
BFS guarantees shortest path in terms of steps because all edges have unit weight.
Bitmask efficiently represents up to 6 keys (a-f) and allows O(1) key checks and updates.
Doors are only passable if the corresponding key is held; otherwise, the move is invalid.
Visited set must include the key bitmask to avoid incorrect pruning of paths that revisit a cell with a different key set.
Time complexity: O(rows * cols * 2^6), space complexity: O(rows * cols * 2^6).

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