Meta·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Meta MLE technical phone screen, one coding question the whole time. Classic grid traversal but with the keys/doors twist that makes it way more interesting than a plain BFS.

Questions Asked (1)

Given a grid with walls, open cells, a start, an end, keys (lowercase letters), and locked doors (uppercase letters), find the shortest path from start to end, picking up keys as needed to pass through doors. Return the path length or indicate it's unreachable.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The naive BFS instinct gets you killed here because you can revisit the same cell under different key states and they're all valid.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a state-space search where each state is (row, col, keys_bitmask). Use BFS to find the shortest path because each move has uniform cost. The keys_bitmask tracks which keys have been collected, allowing passage through corresponding doors.

Pro tip: Emphasize that the state space is at most R*C*2^K, and for typical constraints (K ≤ 6) this is manageable. Mention that BFS guarantees the shortest path and discuss potential optimizations like bidirectional BFS or A* with a heuristic if the state space is large.

1. Clarify problem and constraints

Ask about grid size, number of keys, and whether multiple keys of the same type exist. Confirm that keys are reusable and doors remain open once unlocked.

2. Define state representation

Represent each state as (row, col, keys_bitmask) where keys_bitmask is an integer bitmask of collected keys. Use a visited set or 3D array to track visited states.

3. Apply BFS for shortest path

Perform BFS from the start state, exploring four directions. When encountering a key, update the bitmask; when encountering a door, check if the corresponding key is in the bitmask. Stop when reaching the end cell.

4. Handle unreachable cases

If BFS exhausts all reachable states without finding the end, return -1 or indicate unreachable. Discuss how the visited set prevents infinite loops.

5. Analyze complexity and trade-offs

Time complexity is O(R*C*2^K), space O(R*C*2^K). Discuss trade-offs: BFS is optimal for unweighted graphs; for large K, consider A* with a heuristic or bidirectional BFS.

Key Points to Mention

State-space search with bitmask for keys
BFS guarantees shortest path in unweighted graphs
Visited set to avoid revisiting states
Time and space complexity O(R*C*2^K)
Handling doors and keys dynamically
Potential optimizations for large state spaces

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