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 Onsite rounds at Meta.

What role is this question designed for?

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

Solve grid shortest path and robot cleaning

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Question LeetCode 1091. Shortest Path in Binary Matrix; LeetCode 489. Robot Room Cleaner https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ https://leetcode.com/problems/robot-room-cleaner/description/

Quick Answer: This question evaluates a candidate's ability to implement grid-based graph traversal and stateful simulation, assessing skills in shortest-path search and systematic exploration for cleaning tasks.

Shortest Path in Binary Matrix

Given an `n x n` binary matrix `grid`, return the length of the shortest **clear path** from the top-left cell `(0, 0)` to the bottom-right cell `(n-1, n-1)`. If there is no clear path, return `-1`. A clear path is a path from `(0, 0)` to `(n-1, n-1)` such that: - All visited cells of the path are `0` (open). - All adjacent cells of the path are connected **8-directionally** (they share an edge or a corner). The **length** of a clear path is the number of visited cells along that path (counting both the start and end cell). Return `-1` if the start or end cell is blocked, or if no clear path exists. Example: `grid = [[0,1],[1,0]]` -> `2` (path: (0,0) -> (1,1)). Example: `grid = [[0,0,0],[1,1,0],[1,1,0]]` -> `4`. Example: `grid = [[1,0,0],[1,1,0],[1,1,0]]` -> `-1` (start is blocked). This is LeetCode 1091.

Constraints

n == grid.length == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1

Examples

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

Expected Output: 2

Explanation: Move diagonally from (0,0) to (1,1): path length 2.

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

Expected Output: 4

Explanation: (0,0)->(0,1)->(0,2)->(1,2)->(2,2) is 4 cells (diagonals allowed shorten alternatives).

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

Expected Output: -1

Explanation: The start cell (0,0) is blocked, so there is no clear path.

Input: ([[0]],)

Expected Output: 1

Explanation: Single open cell is both start and end; path length is 1.

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

Expected Output: 4

Explanation: Center is blocked, but 8-directional movement reaches the corner in 4 cells, e.g. (0,0)->(0,1)->(1,2)->(2,2).

Hints

Each cell has 8 neighbors (including diagonals). BFS explores cells in order of distance, so the first time you reach (n-1, n-1) gives the shortest path length.
Count cells, not edges: start the BFS distance at 1 for the start cell.
Guard the trivial blockers first: if grid[0][0] or grid[n-1][n-1] is 1, immediately return -1.

Robot Room Cleaner (Count Cleaned Cells)

A robot starts on an open cell of an `m x n` grid and must clean every open cell it can reach. In the original problem the robot only senses the room through a movement API; here we model it as an executable challenge over a known grid. You are given: - `grid`: an `m x n` matrix where `1` means an open cell and `0` means an obstacle/wall. - `start_row`, `start_col`: the robot's starting position (guaranteed to be inside the grid). The robot can move to any of the 4 edge-adjacent cells (up, right, down, left). It cleans a cell when it first stands on it and can only pass through open (`1`) cells. Using DFS with backtracking, the robot will clean **every open cell reachable** from its start. Return the number of distinct cells the robot cleans. If the starting cell is itself an obstacle, return `0`. Example: `grid = [[1,1,1],[1,1,1],[1,1,1]]`, start `(1, 1)` -> `9` (the whole room is reachable). This is the executable form of LeetCode 489.

Constraints

1 <= m, n <= 100
grid[i][j] is 0 (obstacle) or 1 (open)
0 <= start_row < m, 0 <= start_col < n

Examples

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

Expected Output: 30

Explanation: The classic LeetCode 489 example room. All 30 open cells are reachable from (1,3).

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

Expected Output: 1

Explanation: A single open cell; the robot cleans just itself.

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

Expected Output: 1

Explanation: The two open cells touch only diagonally; the robot moves 4-directionally, so it can only clean its own cell.

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

Expected Output: 9

Explanation: The entire 3x3 room is open and connected; all 9 cells are cleaned.

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

Expected Output: 0

Explanation: The starting cell is an obstacle, so the robot cleans nothing.

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

Expected Output: 7

Explanation: All 7 open cells are reachable by routing around the wall row through column 2.

Hints

Treat the reachable open cells as a connected component: a DFS/flood-fill from the start over 4-directional moves through open cells visits exactly the cells the robot can clean.
Track cleaned cells in a visited set so you never re-clean or loop. The count is the size of that set.
The real LeetCode 489 forces backtracking because the robot has no coordinates; here you have the grid, so a plain DFS that returns after exploring each branch already mirrors the backtracking behavior.

Quick Overview

This question evaluates a candidate's ability to implement grid-based graph traversal and stateful simulation, assessing skills in shortest-path search and systematic exploration for cleaning tasks.