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

IntermediatePrefer not to say

Jun 2026

Summary

Meta SWE coding round, one problem the whole session. Grid BFS with keys and doors. Felt manageable once I figured out the state representation, but getting there took longer than I'd like to admit.

Questions Asked (1)

Given a 2D grid with a start cell, an exit cell, walls, empty cells, keys (a-f), and doors (A-F) that require the matching key to pass through, find the minimum number of steps to get from start to exit moving in four directions. Return -1 if it's not reachable.

Algorithms & Data Structures

Author's notes

The first thing I tried was plain BFS and the interviewer just kind of waited.

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 includes the current position and the set of keys collected. Use BFS to explore states level by level, ensuring the first time you reach the exit is via the minimum number of steps. Represent keys as a bitmask to efficiently track which keys have been collected.

Pro tip: Emphasize that the state must include the key set; otherwise, you might revisit a cell with a different key set and miss the optimal path. Also, mention that BFS is optimal for unweighted graphs, which this is.

1. Understand the problem and define state

Clarify that the grid has walls, empty cells, keys, and doors. Define the state as (row, col, keys_bitmask) where keys_bitmask tracks which keys (a-f) have been collected.

2. Initialize BFS

Find the start position, initialize a queue with the start state (keys_bitmask=0), and a visited set to avoid revisiting the same state. Also, set steps=0.

3. Explore neighbors

For each state, try moving in four directions. If the neighbor is a wall, skip. If it's a door, only proceed if the corresponding key is in the bitmask. If it's a key, update the bitmask. If it's the exit, return steps+1.

4. Track visited states and steps

Use a visited set (or 3D array) to mark states as visited. Increment steps after processing all states at the current level. If the queue empties without reaching the exit, return -1.

5. Return result

If BFS completes without finding the exit, return -1. Otherwise, return the number of steps when the exit is first reached.

Key Points to Mention

BFS guarantees shortest path in unweighted graphs.
State space includes position and key set (bitmask).
Doors require matching keys; keys are collected and persist.
Visited set must include key set to avoid redundant work.
Time complexity: O(R * C * 2^K) where K is number of keys (≤6).
Space complexity: O(R * C * 2^K) for visited and queue.

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