Meta·Software Engineer·Onsite - Coding / Algorithms·Senior

Senior

Apr 2026

Summary

Meta SWE coding round, got a maze traversal problem that looked like basic BFS until you realize you have to track key state too. Not a question you want to see if you've only ever done vanilla shortest path stuff.

Questions Asked (1)

Given a grid maze with a start, an end, walls, keys (a-f), and locked doors (A-F), find the minimum number of steps from start to end moving in 4 directions. A door can only be passed if you're carrying the corresponding key. Return -1 if the end is unreachable.

Algorithms & Data Structures

Author's notes

I started with regular BFS and got maybe two minutes in before realizing the visited set was wrong.

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, key_mask). Use BFS to explore all reachable states, updating the key mask when picking up keys and checking door access. Return the distance when reaching the end, or -1 if unreachable.

Pro tip: Mention that the state space is at most m*n*2^k, and that BFS is optimal because all edges have unit weight. Also, note that you can optimize by only considering keys that are actually present in the maze.

1. Understand the problem and define state

Clarify that the state must include position and collected keys. Represent keys as a bitmask (6 bits for a-f).

2. Choose BFS for shortest path

Since each move costs 1, BFS guarantees the shortest path. Use a queue to explore states level by level.

3. Handle transitions and constraints

For each move, check boundaries, walls, and doors. If a door is encountered, verify the corresponding key is in the mask. If a key is picked up, update the mask.

4. Track visited states and distance

Use a 3D visited array or a set to avoid revisiting the same state. Store distance in the queue or a separate array.

5. Return result

When the end cell is reached, return the current distance. If BFS exhausts all states without reaching the end, return -1.

Key Points to Mention

State representation: (row, col, key_mask) where key_mask is a 6-bit integer.
BFS ensures shortest path because all moves have equal cost.
Time complexity: O(m * n * 2^6) and space complexity similar.
Handling doors: only pass if (key_mask & (1 << (door - 'A'))) != 0.
Picking up keys: update key_mask with bitwise OR when stepping on a key cell.
Edge cases: start equals end, unreachable end, multiple keys of same type (only need one).

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