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