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

What role is this question designed for?

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

Solve BFS grid delivery routing | DoorDash Coding Question

Quick Overview

This question evaluates proficiency in grid-based graph traversal and shortest-path computation, along with complexity analysis and handling dynamic changes, assessing skills in algorithm design, graph algorithms, and data structures within the Coding & Algorithms domain.

Solve BFS grid delivery routing

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given an m×n grid representing a city: 'S' are DashMart stores, 'H' are homes, '.' are roads, and '#' are obstacles. Movement is allowed in four directions on roads only. For each home cell, compute the length of the shortest path to any store; if unreachable, return -1 for that home. Output an array of distances aligned to the list of homes. Provide the algorithm, complexity, and code. Follow-up: if new obstacles are added frequently between queries, explain how you would update distances efficiently without recomputing everything from scratch.

Quick Answer: This question evaluates proficiency in grid-based graph traversal and shortest-path computation, along with complexity analysis and handling dynamic changes, assessing skills in algorithm design, graph algorithms, and data structures within the Coding & Algorithms domain.

You are given an m×n grid representing a city. Each cell is one of: - `'S'` — a DashMart store - `'H'` — a home - `'.'` — a road - `'#'` — an obstacle (impassable) From any cell you may move up, down, left, or right into a neighboring cell, as long as that neighbor is not an obstacle (`'#'`). Stores, homes, and roads are all traversable. For every home cell `'H'`, compute the length of the shortest path (number of steps) to the **nearest** DashMart store `'S'`. If a home cannot reach any store, its distance is `-1`. Return an array of distances, one per home, ordered by the homes' positions in row-major order (top-to-bottom, then left-to-right within each row). **Approach:** Run a single multi-source BFS seeded from every store cell at distance 0 simultaneously. Because BFS explores cells in non-decreasing distance order, the first time BFS reaches any cell, it has found that cell's shortest distance to the closest store. After the BFS fills in distances for the whole reachable region, scan the grid in row-major order and collect the distance of each home. **Follow-up (discuss, not coded):** If obstacles are added frequently between queries, recomputing the full BFS each time is wasteful. Options: (1) Adding an obstacle can only *increase* distances, so re-run BFS only from the affected frontier — invalidate the subtree of cells whose shortest path passed through the newly blocked cell and re-relax their neighbors (incremental/dynamic BFS, e.g. the D*-Lite family). (2) Precompute and cache the distance field; on an obstacle insertion, mark the blocked cell and lazily recompute only dirty regions. (3) For bursty edits, batch the obstacle additions and recompute once per batch instead of per edit.

Constraints

1 <= m, n (the grid may be empty; an empty grid returns []).
Each cell is one of 'S', 'H', '.', '#'.
There may be zero or more stores and zero or more homes.
Movement is 4-directional (up/down/left/right); diagonal moves are not allowed.
'#' cells are impassable; 'S', 'H', and '.' cells are all traversable.
Distances are returned in row-major order of the home cells.

Examples

Input: ([['S', '.', 'H'], ['#', '.', '#'], ['H', '.', '.']],)

Expected Output: [2, 4]

Explanation: Home at (0,2) reaches store (0,0) via (0,0)->(0,1)->(0,2) = 2 steps. Home at (2,0) must go (2,0)->(2,1)->(1,1)->(0,1)->(0,0) = 4 steps (the obstacles at (1,0) and (1,2) block the shorter routes).

Input: ([['S', 'H']],)

Expected Output: [1]

Explanation: The home is directly adjacent to the store, so distance 1.

Input: ([['H', '#', 'S']],)

Expected Output: [-1]

Explanation: The obstacle at (0,1) walls the home off from the store, so it is unreachable: -1.

Input: ([['S', '.', '.', 'H'], ['#', '#', '#', '.'], ['H', '.', '.', '.']],)

Expected Output: [3, 8]

Explanation: Home (0,3) is 3 steps along the top row. Home (2,0) is sealed off from the top except through column 3: (0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(2,2)->(2,1)->(2,0) = 8 steps.

Input: ([['H']],)

Expected Output: [-1]

Explanation: A lone home with no store anywhere in the grid: unreachable, -1.

Input: ([],)

Expected Output: []

Explanation: Empty grid has no homes, so the answer is an empty array.

Input: ([['S', 'S', 'H'], ['H', '.', '.']],)

Expected Output: [1, 1]

Explanation: Multi-source BFS from both stores: home (0,2) is adjacent to store (0,1) = 1, and home (1,0) is adjacent to store (0,0) = 1. Homes are listed in row-major order: (0,2) then (1,0).

Hints

Instead of running a separate BFS from each home, run ONE multi-source BFS seeded from all store cells at distance 0 at once. The first time BFS reaches a cell, that is its shortest distance to the closest store.
Use a distance matrix initialized to -1 to double as the 'visited' marker: a cell with dist == -1 has not been reached yet, so unreachable homes naturally keep -1.
After BFS fills the reachable region, scan the grid in row-major order (row by row, left to right) and append dist[i][j] for every 'H' cell to build the answer in the required order.

Quick Overview