Meta·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Meta SWE interview with a maze exploration problem that sounds deceptively simple until you're actually in it. The question is all about navigating unknown state with limited primitives, which is harder to reason about cleanly under pressure than it looks on paper.

Questions Asked (1)

You're controlling a mouse in a 2D maze with no knowledge of the maze's dimensions or your absolute position. You only have three operations: move one step forward (returns false if blocked), turn left, and turn right. There's cheese somewhere in the maze. Design an algorithm that guarantees the mouse finds the cheese, using relative coordinates to track visited cells. Argue correctness and analyze complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The part that tripped me up initially was the coordinate tracking.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Treat the problem as online exploration of an unknown graph where the mouse maintains a relative coordinate system and a map of visited cells. Use a systematic exploration strategy like depth-first search with backtracking, leveraging the ability to turn and move to navigate back to known cells. Argue that the algorithm guarantees finding the cheese because it exhaustively explores all reachable cells, and analyze complexity in terms of the number of moves relative to the maze size.

Pro tip: Emphasize that the mouse must maintain its orientation and use relative coordinates to build a consistent map; this is crucial for backtracking and avoiding infinite loops. Also, discuss how the algorithm handles dead ends and revisits efficiently.

1. Model the Problem

Represent the maze as an unknown grid graph where each cell has up to four neighbors. The mouse's state includes its relative position (x, y) and orientation (facing direction).

2. Choose an Exploration Strategy

Select a systematic exploration algorithm such as depth-first search (DFS) with backtracking. The mouse will explore each branch fully before returning to explore other branches.

3. Implement Navigation and Mapping

Maintain a map of visited cells and their connectivity. Use the move and turn operations to navigate: to move to an adjacent cell, turn to face it, then move forward. To backtrack, reverse the path using the map.

4. Argue Correctness

Prove that the algorithm explores all reachable cells: since the maze is finite and connected, DFS will eventually visit every cell, including the one with cheese. The relative coordinate system ensures no cell is missed due to orientation changes.

5. Analyze Complexity

The number of moves is O(N) where N is the number of reachable cells, but constant factors depend on backtracking. Each edge may be traversed multiple times, but the total moves are bounded by O(N * D) where D is the maximum degree (4). Space complexity is O(N) for the map.

Key Points to Mention

Relative coordinate system: track position and orientation relative to start, update on moves and turns.
Depth-first search with backtracking: explore each direction systematically, return to previous cell when dead end.
Handling blocked moves: when move forward returns false, treat as wall and try other directions.
Avoiding infinite loops: mark visited cells and do not re-enter unless backtracking.
Correctness proof: induction on reachable cells, DFS covers all.
Complexity: O(N) moves for exploration, O(N) space for map, where N is number of cells.

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