Meta·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

Meta MLE coding round, one problem the whole session. It started as a basic BFS maze question and then they kept adding constraints until I was basically rewriting the whole thing live.

Questions Asked (1)

You have a 2D grid maze with walls, open cells, a start, and an end. Implement BFS to find the shortest path. Then extend it: add keys (lowercase letters) and doors (uppercase letters) where you can only pass through a door if you already hold the matching key. How does your visited state need to change, and what's the minimum steps to reach the goal?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The first part felt easy and I think I got a little too comfortable.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clearly explaining standard BFS on a grid, emphasizing the visited set and queue. Then, for the key-door extension, highlight that the visited state must include the set of keys collected, transforming it from (row, col) to (row, col, key_mask). Finally, discuss how BFS still guarantees the shortest path and mention potential optimizations like bitmask representation.

Pro tip: Mention that the state space size is O(R*C*2^K) where K is the number of keys, and that BFS is still optimal because all edges have unit weight. Also, note that you can prune states where you have a superset of keys but same position, though it's not necessary for correctness.

1. Clarify the problem and constraints

Restate the problem to ensure understanding: grid with walls, start, end, keys, and doors. Ask about grid size, number of keys, and whether multiple keys of same type exist.

2. Explain standard BFS for shortest path

Describe BFS on the grid: queue of (row, col, steps), visited set of (row, col), and exploring 4 directions. Emphasize that BFS finds shortest path in unweighted graph.

3. Extend state to include keys

Introduce key collection: state becomes (row, col, key_mask) where key_mask is a bitmask of collected keys. When encountering a key, update mask; when encountering a door, check if corresponding key bit is set.

4. Analyze complexity and correctness

State that BFS still guarantees shortest path because each move costs 1. Complexity: O(R*C*2^K) time and space, where K is number of distinct keys.

5. Discuss optimizations and trade-offs

Mention possible optimizations: using bitmask for keys, early exit when goal reached, and pruning visited states that are dominated (same position with superset of keys).

Key Points to Mention

BFS guarantees shortest path in unweighted graphs.
Visited state must include key set to avoid revisiting same cell with different keys.
Use bitmask to represent keys efficiently.
Doors are passable only if corresponding key is held.
Time and space complexity: O(R*C*2^K).
BFS remains optimal because all moves have unit cost.

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