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 maze to find target

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given an exploration interface for an unknown 2D maze that exposes only local actions (e.g., move(up/down/left/right) -> bool indicating success, position() -> (r,c), and atCheese() -> bool). Starting from an initial cell, design an algorithm to find the cheese with the fewest steps if it is reachable, minimizing redundant moves. You may adapt/override the interface to enable breadth-first exploration on the fly (e.g., by building a discovered map and backtracking). Specify visited-state representation, frontier management, termination conditions, and complexity in terms of reachable cells. Follow-up: Propose unit tests, including obstacles at start, multiple cheeses, unreachable cheese, loops, unknown bounds, and large open areas.

Quick Answer: This question evaluates understanding of graph traversal and exploration algorithms, representation of visited state and frontiers, path optimality, and complexity analysis in an environment constrained to local actions.

A mouse explores an unknown 2D maze and must reach the cheese using the fewest moves. The maze is modeled as a grid of integers: - `0` — an open cell the mouse can stand on - `1` — a wall / obstacle the mouse cannot enter - `2` — the cell containing the cheese (the target) The mouse starts at cell `start = (r, c)` and may move one step at a time **up, down, left, or right** (no diagonals). Implement breadth-first exploration of the unknown maze and return the **minimum number of moves** needed to reach a cheese cell. Return `-1` if the start is out of bounds, the start cell is a wall, or no cheese cell is reachable from the start. If the mouse already starts on the cheese, the answer is `0`. This is the executable core of the classic "mouse finds cheese" / unknown-maze interface problem: BFS guarantees the first time the target is dequeued (or discovered) it is reached via a shortest path, so redundant moves are minimized. The `visited` grid is the visited-state representation, the FIFO queue is the frontier, and termination occurs when the cheese is found or the frontier empties. **Example 1** ``` grid = [[0, 0, 0], [1, 1, 0], [0, 0, 2]] start = (0, 0) ``` The direct path down is blocked by the wall row, so the mouse goes right along the top row then down the right column: (0,0)->(0,1)->(0,2)->(1,2)->(2,2). That is **4** moves. **Example 2** ``` grid = [[0, 1, 2], [1, 1, 1], [0, 0, 0]] start = (0, 0) ``` The cheese at (0,2) is fully walled off from the start, so the answer is **-1**.

Constraints

1 <= R, C <= 1000 (R = number of rows, C = number of columns).
Each cell value is one of: 0 (open), 1 (wall), or 2 (cheese).
There is at most one cheese cell relevant to the answer; if several exist, return the distance to the nearest reachable one.
0 <= start[0] < R and 0 <= start[1] < C for valid input, but the function must also return -1 for an out-of-bounds or wall start.
Movement is restricted to the four orthogonal directions (up, down, left, right).

Examples

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

Expected Output: 4

Explanation: The wall row forces a detour: (0,0)->(0,1)->(0,2)->(1,2)->(2,2), which is 4 moves — the shortest path around the obstacle.

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

Expected Output: 6

Explanation: A vertical wall splits the grid, so the mouse must go all the way down the left column, across the bottom row, and up the right column to reach the cheese — 6 moves.

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

Expected Output: -1

Explanation: Unreachable cheese: the cheese at (0,2) is walled off from the start region, so BFS exhausts the frontier without finding it and returns -1.

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

Expected Output: 0

Explanation: Boundary case: the mouse starts directly on the cheese, so zero moves are needed.

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

Expected Output: 2

Explanation: Open 2x2 grid — the cheese is at the opposite corner, reachable in 2 moves (right then down, or down then right).

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

Expected Output: -1

Explanation: Obstacle at the start: the starting cell itself is a wall, so the mouse cannot move at all — return -1.

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

Expected Output: 6

Explanation: Large open area with no obstacles — the shortest path is the Manhattan distance from (0,0) to (2,4), which is 2 + 4 = 6 moves.

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

Expected Output: 4

Explanation: Non-corner-origin sanity check: starting at (2,2) and the cheese at (0,0), the Manhattan distance across the open grid is 2 + 2 = 4 moves.

Hints

BFS, not DFS: BFS explores cells in order of increasing distance, so the first time you reach the cheese you have used the fewest possible moves. DFS can find a path but not necessarily the shortest one.
Mark a cell visited the moment you enqueue it (not when you dequeue it). Otherwise the same cell can be pushed multiple times, inflating the queue and risking redundant exploration.
Handle the degenerate cases up front: start out of bounds, start on a wall, and start already on the cheese (answer 0). Walls (value 1) must never be entered or enqueued.
Track distance by storing it alongside each queued cell (or by processing the queue one 'level' at a time). When the frontier empties without finding a 2, the cheese is unreachable — return -1.

Quick Overview

This question evaluates understanding of graph traversal and exploration algorithms, representation of visited state and frontiers, path optimality, and complexity analysis in an environment constrained to local actions.