How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

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.

Input: ([[2]], 0, 0)

Expected Output: True

Explanation: The single starting cell already contains the cheese.

Input: ([[0]], 0, 0)

Expected Output: False

Explanation: A 1x1 grid with no cheese has nothing to find.

Input: ([[1,2],[0,0]], 0, 0)

Expected Output: False

Explanation: The start (0,0) is itself a wall, an invalid position, so the mouse cannot begin and returns False.

Input: ([[0,0,0],[0,1,0],[0,0,2]], 1, 0)

Expected Output: True

Explanation: Starting mid-grid, the mouse routes around the central wall to reach the cheese at (2,2).

Input: ([], 0, 0)

Expected Output: False

Explanation: An empty grid has no cells to explore.

Input: ([[0,0],[0,2]], 5, 5)

Expected Output: False

Explanation: The start position is out of bounds, so the search returns False immediately.

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.

Quick Overview

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.