Navigate unknown grid to locate target
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You control a mouse in an unknown 2D maze. You do not know the maze dimensions or your absolute coordinates. The interface exposes move() → bool (attempts to move one step forward; returns false if blocked), turnLeft(), and turnRight(). A cell may contain cheese; calling atCheese() returns true iff the current cell has cheese. Design an algorithm that guarantees the mouse will locate the cheese if it exists, exploring the maze via relative coordinates and marking visited cells. Provide correctness arguments and complexity analysis.
Quick Answer: This question evaluates algorithmic problem-solving and spatial reasoning skills, particularly graph traversal, exploration in unknown environments, state encoding for relative coordinates, and reasoning about correctness.
You control a mouse that explores an unknown 2D maze using only relative moves and a visited-cell marker. You can model the maze as a grid where `0` is an open cell, `1` is a wall the mouse cannot enter, and `2` is the cell containing the cheese (which is also passable). The mouse starts at `(start_row, start_col)` and may step to the four orthogonally adjacent non-wall cells.
Return `true` if the mouse can reach the cheese starting from its position, and `false` otherwise. This captures the core guarantee of the real exploration algorithm: by systematically visiting every reachable open cell exactly once (marking it visited so it is never re-explored), the mouse is guaranteed to find the cheese if and only if it lies in the same connected open region as the start.
Edge cases: an empty grid, a start position on a wall, an out-of-bounds start, and cheese walled off from the start all return `false`.
Constraints
- 0 <= number of rows, number of columns
- Each cell value is one of 0 (open), 1 (wall), 2 (cheese)
- At most one cell contains cheese in a valid maze
- start_row / start_col may be out of bounds or on a wall, in which case return False
- The mouse may only move to orthogonally adjacent (up/down/left/right) non-wall cells
Examples
Input: ([[0,0,2],[1,1,0],[0,0,0]], 0, 0)
Expected Output: True
Explanation: From (0,0) the mouse moves right to (0,1) then (0,2), which holds the cheese.
Input: ([[0,1,2],[0,1,0],[0,1,0]], 0, 0)
Expected Output: False
Explanation: A full column of walls separates the start's region from the cheese, so it is unreachable.
Hints
- The interactive move()/turnLeft()/turnRight()/atCheese() interface reduces to a graph traversal: every reachable open cell is a node, and the visited marker prevents infinite loops.
- A flood fill (DFS or BFS) from the start that marks each visited cell guarantees you explore the entire connected open region exactly once.
- Treat the cheese cell as passable (you can stand on it) and check for it as you visit each cell; remember to guard against an out-of-bounds or wall start position before traversing.