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

SeniorPrefer not to say

May 2026

Summary

Meta SWE coding round, one problem the whole time. They took a classic BFS maze question and kept layering on requirements until it was basically a full state-space search problem. Not the hardest thing I've done but the extension caught me a bit flat-footed.

Questions Asked (1)

You have a BFS-based maze solver for a grid with walls, open cells, a start, and an end. Now add keys and doors: keys have identities (like 'a', 'b', etc.), doors block movement unless the agent already holds the matching key. Modify the BFS to handle this, and discuss the resulting complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I got the basic BFS part out fast, that wasn't the issue.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the state as (position, key set) and run BFS on this expanded state space. Use bitmasking to represent key sets efficiently, and discuss how the state space grows exponentially with the number of keys, affecting time and space complexity.

Pro tip: Emphasize that BFS remains optimal for unweighted graphs, but the state space explosion means the algorithm may become impractical for many keys; mention potential optimizations like bidirectional BFS or A* with admissible heuristics.

1. Define the state representation

Represent each state as (row, col, keys_bitmask) where keys_bitmask tracks collected keys. This captures all necessary information for future decisions.

2. Adapt BFS transitions

From a state, explore neighbors; if a neighbor is a door, only allow passage if the corresponding key bit is set in the current keys_bitmask. If a neighbor is a key, update the bitmask by setting the key's bit.

3. Handle visited states

Use a 3D visited array or a hash set to track visited (row, col, keys_bitmask) states to avoid cycles and redundant work.

4. Analyze complexity

Time and space complexity become O(R * C * 2^K) where R and C are grid dimensions and K is the number of distinct keys. Discuss how this exponential factor impacts scalability.

5. Discuss trade-offs and optimizations

Mention that while BFS guarantees shortest path, the exponential state space may be prohibitive. Suggest alternatives like A* with a heuristic that ignores doors, or bidirectional BFS to reduce explored states.

Key Points to Mention

State space expansion: (position, key set) pairs
Bitmasking for efficient key set representation
Doors as conditional transitions based on key possession
Visited state tracking to prevent infinite loops
Complexity: O(R * C * 2^K) time and space
Potential optimizations: bidirectional BFS, A*, or heuristics

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