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

What role is this question designed for?

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

Compute nearest-exit distances in a grid | DoorDash Coding Question

Quick Overview

Compute nearest-exit distances in a grid evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Compute nearest-exit distances in a grid

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a 2D grid representing a building floor with three cell types: -1 for walls, 0 for exits, and a large sentinel value for empty rooms. Update each empty room with the Manhattan distance (4-directional moves) to its nearest exit; if unreachable, leave it as the sentinel value. Solve it efficiently and analyze time and space complexity. Follow-ups: extend to a 3D grid (multiple floors) and to weighted movement costs.

Quick Answer: Compute nearest-exit distances in a grid evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given an `m x n` 2D grid representing a building floor. Each cell is one of three values: - `-1` — a wall or obstacle (impassable). - `0` — an exit (gate). - `2147483647` — an empty room (a large sentinel value meaning "infinity"). Fill each empty room with the distance (number of 4-directional moves) to its **nearest** exit. If it is impossible to reach an exit from a room, leave that room as the sentinel value `2147483647`. Return the grid after filling it in (the grid may also be mutated in place). **Example** Input: ``` [[INF, -1, 0, INF], [INF, INF, INF, -1], [INF, -1, INF, -1], [ 0, -1, INF, INF]] ``` Output: ``` [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]] ``` where `INF = 2147483647`. **Approach hint:** Run a single multi-source breadth-first search starting simultaneously from every exit. The first time BFS reaches a room, that is its shortest distance to any exit. This is O(m·n) rather than running a separate BFS from each room. **Follow-ups discussed in the interview:** extend the same multi-source BFS to a 3D grid (multiple floors, 6 neighbors) and to weighted movement costs (replace the BFS queue with a min-heap / Dijkstra).

Constraints

1 <= m, n <= 250 (typical interview bound)
Each cell is -1 (wall), 0 (exit), or 2147483647 (empty room).
The grid may contain zero exits (then every room stays 2147483647).
Distances use 4-directional (up/down/left/right) Manhattan-style moves; you cannot pass through walls.

Examples

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

Expected Output: [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]

Explanation: Canonical Walls-and-Gates example. Multi-source BFS from the two exits (row0 col2 and row3 col0) fills every reachable room with its shortest 4-directional distance.

Input: ([[0]],)

Expected Output: [[0]]

Explanation: Single cell that is already an exit — nothing to fill.

Hints

A separate BFS from every room is O((m*n)^2). Invert the problem: BFS outward from the exits instead.
Seed a single queue with the coordinates of ALL exits (cells equal to 0) before starting BFS — this is multi-source BFS.
When you pop a cell, push each neighbor that still equals the sentinel 2147483647 and set its value to current + 1. Because BFS expands in layers of increasing distance, the first time you reach a room is its shortest distance, so no revisits and no explicit visited set are required.
Walls (-1) and already-filled rooms are simply never enqueued because their value is not the sentinel.
Follow-up (3D): use 6 neighbor offsets and (floor, row, col) tuples. Follow-up (weighted moves): replace the FIFO queue with a min-heap (Dijkstra) keyed by accumulated cost.