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

IntermediatePrefer not to say

Jun 2026

Summary

Meta SWE coding round, one algorithmic problem that looks straightforward until you actually think about the state space. The BFS angle is obvious but the key/door mechanic is where people trip up.

Questions Asked (1)

Given a 2D grid maze with a start, an exit, walls, empty cells, keys (a-f), and locked doors (A-F), find the minimum number of steps from start to exit. You can only pass through a door if you've already collected the matching key. Return -1 if unreachable.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was plain BFS and I started coding it before really thinking.

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_collected). Use BFS to explore states in order of steps, since each move costs 1. Track visited states to avoid cycles and return the step count when reaching the exit.

Pro tip: Use bitmask to represent keys (e.g., bit 0 for 'a', bit 1 for 'b', etc.) for efficient state encoding and visited tracking. Mention that BFS is optimal for unweighted graphs, and discuss potential optimizations like bidirectional BFS if the state space is large.

1. Understand the problem and state representation

Clarify that the state includes 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 minimum steps. Initialize a queue with the start state and a visited set.

3. Explore neighbors and handle keys/doors

For each neighbor, check if it's a wall. If it's a door, ensure the corresponding key is in the bitmask. If it's a key, update the bitmask.

4. Track visited states and return result

Mark each state as visited to avoid revisiting. If the exit is reached, return the current step count. If the queue empties, return -1.

5. Analyze complexity and trade-offs

Time: O(R*C*2^K), Space: O(R*C*2^K). Discuss if K is large, but here K<=6 so it's fine.

Key Points to Mention

State space includes position and keys collected, represented as (r, c, key_mask).
BFS is optimal for unweighted graphs, ensuring minimum steps.
Use bitmask for keys to efficiently encode and check key possession.
Visited set must include the key mask to avoid missing paths that require revisiting a cell with different keys.
Time and space complexity: O(R*C*2^K) where K is number of keys (max 6).
Edge cases: start is exit, no keys needed, unreachable exit, multiple keys/doors.

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