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 Pinterest.

What role is this question designed for?

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

Compute reachable cells for a cleaning robot

Q: Compute reachable cells for a cleaning robot

This question evaluates understanding of graph traversal, state-space modeling, and scalability when computing reachable cells on a 2D grid under 8-direction movement and variants that allow limited obstacle removal or multiple agents.

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a 2D grid representing a floor plan: - `0` = free cell (the robot may stand on it) - `1` = blocked cell (obstacle) The robot can move from a cell to any of its **8 neighbors** (up, down, left, right, and 4 diagonals) as long as the destination cell is allowed under the rules of the sub-question. Return answers as a set/list of reachable coordinates `(r, c)` (order does not matter). ### Sub-question 1 (basic reachability) **Input:** grid `m x n` and a start cell `(sr, sc)` that is free. **Task:** return **all free cells** reachable from `(sr, sc)` using 8-direction moves. ### Sub-question 2 (one obstacle can be cleared) Same as Sub-question 1, except the robot may **convert at most one blocked cell (`1`) into free (`0`)** during its traversal (think: it can clear/remove one obstacle exactly once). **Task:** return all cells that are reachable under this rule. ### Sub-question 3 (two robots) **Input:** grid `m x n` and two start cells `(s1r, s1c)` and `(s2r, s2c)` that are free. **Task:** return the set of cells that are reachable by **at least one** of the two robots (union of their reachable areas) using 8-direction moves. ### Constraints (assume) - `1 <= m, n <= 2000` (choose an approach that is safe for large grids) - Grid is not necessarily fully connected. - Start cells are within bounds. Clarify in the interview how to represent the returned set for large outputs (e.g., boolean mask vs coordinate list).

Quick Answer: This question evaluates understanding of graph traversal, state-space modeling, and scalability when computing reachable cells on a 2D grid under 8-direction movement and variants that allow limited obstacle removal or multiple agents.

Part 1: Reachable Free Cells with 8-Directional Moves

You are given a 2D grid representing a floor plan. A cell contains `0` if it is free and `1` if it is blocked. A robot starts at a free cell `(sr, sc)` and may move to any of its 8 neighbors: up, down, left, right, and the 4 diagonals. The robot may move only onto free cells. Return every free cell that is reachable from the start. For deterministic output, return the coordinates in ascending row-major order: sorted first by row, then by column.

Constraints

`1 <= m, n <= 2000`
`grid[r][c]` is either `0` or `1`
The start cell is within bounds in valid inputs
Use an iterative approach that is safe for large grids

Examples

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

Expected Output: [(0, 0), (0, 2), (1, 0), (1, 1), (2, 1), (2, 2)]

Explanation: Diagonal moves let the robot pass through the connected free region.

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

Expected Output: [(0, 0)]

Explanation: All neighboring cells are blocked, so the start cell is the only reachable free cell.

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

Expected Output: [(0, 0)]

Explanation: Single-cell edge case.

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

Expected Output: [(0, 0), (1, 1)]

Explanation: The robot can move diagonally from `(0, 0)` to `(1, 1)`.

Hints

Model the grid as a graph where each free cell is a node connected to up to 8 neighboring free cells.
Use BFS or DFS iteratively; recursion can overflow on large grids.

Part 2: Reachable Cells with At Most One Obstacle Clear

You are given a 2D grid where `0` means free and `1` means blocked. A robot starts at a free cell `(sr, sc)` and may move to any of its 8 neighbors. This time, the robot may clear at most one blocked cell during its traversal. Clearing a blocked cell turns it into a free cell for that traversal, and the robot may stand on it. Return every coordinate that is reachable under this rule. A coordinate should be included if there exists at least one valid traversal that reaches it. That means the answer may include coordinates that were originally blocked, because the robot could choose to clear that cell. Return coordinates in ascending row-major order.

Constraints

`1 <= m, n <= 2000`
`grid[r][c]` is either `0` or `1`
The start cell is free in valid inputs
The algorithm should be safe for large grids

Examples

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

Expected Output: [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]

Explanation: By choosing different blocked cells to clear, every coordinate in the grid becomes reachable in some valid traversal.

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

Expected Output: [(0, 0), (0, 1)]

Explanation: The robot can clear `(0, 1)`, but then it cannot pass through `(0, 2)` because only one obstacle may be cleared.

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

Expected Output: [(0, 0)]

Explanation: Single-cell edge case.

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

Expected Output: [(0, 0), (0, 1), (1, 0), (1, 1)]

Explanation: No obstacle needs to be cleared; all cells are reachable.

Hints

A plain visited set is not enough. The state must also track whether the one allowed obstacle clear has already been used.
The same cell may need to be explored twice: once with the clear still available, and once after it has been used.

Part 3: Union of Reachable Cells from Two Robots

You are given a 2D grid where `0` means free and `1` means blocked. Two robots start at free cells `(s1r, s1c)` and `(s2r, s2c)`. Each robot may move to any of its 8 neighbors, but only onto free cells. Return the set of free cells reachable by at least one of the two robots. For deterministic testing, return the coordinates in ascending row-major order.

Constraints

`1 <= m, n <= 2000`
`grid[r][c]` is either `0` or `1`
Both start cells are within bounds and free in valid inputs
Use an iterative solution that works for large grids

Examples

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

Expected Output: [(0, 0), (0, 1), (1, 1), (2, 0), (2, 2)]

Explanation: The two starts lie in the same 8-connected free component, so the union is that entire component.

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

Expected Output: [(0, 0), (0, 1), (2, 0), (2, 1)]

Explanation: The blocked middle row separates the two reachable regions.

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

Expected Output: [(0, 0), (0, 1), (1, 0), (1, 1)]

Explanation: Both robots are in the same open grid, so every free cell is reachable.

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

Expected Output: [(0, 0)]

Explanation: Single-cell edge case; both robots start on the same cell.

Hints

You can run one multi-source BFS by placing both start cells into the queue initially.
If both robots can reach the same region, a shared visited structure avoids duplicate work.

Quick Overview

This question evaluates understanding of graph traversal, state-space modeling, and scalability when computing reachable cells on a 2D grid under 8-direction movement and variants that allow limited obstacle removal or multiple agents.