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.

Compute delivery times on a grid | DoorDash Coding Question

Compute delivery times on a grid

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given a 2D grid with cells marked as 'M' (warehouses), 'C' (customers), 'X' (obstacles), and '.' (roads). You can move up, down, left, or right with cost 1 per step. For each customer cell, compute the minimum number of steps from any warehouse; return -1 if unreachable. Define the input/output format and justify your data structures. Follow-ups: handle millions of cells efficiently (memory/time); support non-uniform road costs (convert to Dijkstra); and return actual paths for a subset of customers.

Quick Answer: This question evaluates understanding of graph traversal and shortest-path algorithms, grid-based pathfinding, and data structure selection for representing sparse or large grids within the Coding & Algorithms domain.

You are given a 2D grid (list of rows of single-character strings) where each cell is one of: - `'M'` — a warehouse (delivery source) - `'C'` — a customer - `'X'` — an obstacle (cannot be entered) - `'.'` — an open road From any cell you may move up, down, left, or right to an adjacent in-bounds, non-obstacle cell at a cost of 1 step. For **every** customer cell, compute the minimum number of steps from the *nearest* warehouse. If a customer is unreachable from all warehouses, its distance is `-1`. Return a list of `[row, col, distance]` triples, one per customer cell, in row-major order (scan top-to-bottom, left-to-right). **Why multi-source BFS:** Because every move costs exactly 1, distances form a uniform-cost shortest-path problem. Seeding a single queue with *all* warehouses at distance 0 and running one BFS computes, for each reachable cell, its distance to the closest warehouse in a single O(R·C) sweep — far cheaper than running a separate BFS per warehouse or per customer. **Follow-ups (discussion):** (1) For millions of cells, use a flat 1-D distance array indexed by `r*cols + c` to cut Python/object overhead, and process the grid as a stream; the BFS is already O(R·C) time and space. (2) For non-uniform road costs, replace the plain BFS queue with a min-heap and run multi-source Dijkstra. (3) To recover actual paths for a subset of customers, store a parent pointer (or the direction stepped from) when first relaxing each cell, then walk parents back to a warehouse.

Constraints

1 <= rows, cols (the grid is non-empty in tests; an empty grid returns []).
Each cell is exactly one of 'M', 'C', 'X', '.'.
There may be zero or more warehouses ('M') and zero or more customers ('C').
Movement is 4-directional (no diagonals); 'X' cells are never entered.
If a customer cannot be reached from any warehouse, its distance is -1.

Examples

Input: [['M', '.', 'C'], ['.', 'X', '.'], ['.', '.', 'C']]

Expected Output: [[0, 2, 2], [2, 2, 4]]

Explanation: Customer at (0,2) is reached via (0,0)->(0,1)->(0,2) in 2 steps. Customer at (2,2) must detour around the obstacle at (1,1): (0,0)->(1,0)->(2,0)->(2,1)->(2,2), 4 steps.

Input: [['M', 'C']]

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

Explanation: The customer sits directly next to the warehouse: 1 step.

Input: [['M', 'X', 'C']]

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

Explanation: The obstacle at (0,1) fully separates the customer from the warehouse, so it is unreachable: -1.

Input: [['C', '.', 'M', '.', 'C']]

Expected Output: [[0, 0, 2], [0, 4, 2]]

Explanation: A single central warehouse serves both customers; each is 2 steps away. Demonstrates a single source reaching multiple customers.

Input: [['M', 'M'], ['C', '.']]

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

Explanation: Two warehouses; the customer at (1,0) is adjacent to the warehouse at (0,0), giving distance 1 (nearest-source semantics of multi-source BFS).

Input: [['.', '.'], ['.', '.']]

Expected Output: []

Explanation: No customers present, so the result is an empty list.

Input: [['X', 'C'], ['M', 'X']]

Expected Output: [[0, 1, -1]]

Explanation: The customer at (0,1) is walled off by obstacles at (0,0) and (1,1) and cannot reach the warehouse at (1,0): -1.

Hints

Run ONE breadth-first search seeded with all warehouse cells at distance 0, instead of a separate search per warehouse — this directly yields the distance to the nearest warehouse for every cell.
Use a visited/distance grid initialized to -1; a cell is unreachable exactly when its distance stays -1 after the BFS completes.
Treat 'X' cells as walls (never enqueue them). 'M', 'C', and '.' are all traversable.
After the BFS, scan the grid in row-major order and emit [row, col, dist] for every 'C' cell.
Follow-up: swap the FIFO queue for a min-heap to handle non-uniform (weighted) road costs — that turns multi-source BFS into multi-source Dijkstra.

Quick Overview

This question evaluates understanding of graph traversal and shortest-path algorithms, grid-based pathfinding, and data structure selection for representing sparse or large grids within the Coding & Algorithms domain.