Coding questions · DoorDash

Compute nearest dashmart and busiest assignments

Compute nearest dashmart and busiest assignments 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 grid of characters where 'D' marks a dashmart, 'X' marks an impassable cell, and ' ' (space) marks a passable cell. Movement is allowed only in four directions (up, down, left, right) and cannot go outside the grid or into 'X'. You are also given a list of K query locations (row, col). Part A: For each query location, return the length (in steps) of the shortest path to any dashmart. If the starting cell is a dashmart, the distance is 0. If the starting cell is 'X' or no path to any dashmart exists, return -1. Implement a function nearestDistances(grid, queries) that handles multiple test cases and is bug-free. Part B (follow-up): Each dashmart at coordinates (r, c) has a non-negative base busy score B[r][c] (provided for all 'D' cells) and you are given an integer alpha ≥ 0. Define the effective busy of a dashmart for a location at grid distance d as max(0, B[r][c] - alpha * d). For each query location, among all reachable dashmarts, return the dashmart that maximizes effective busy; break ties by smaller distance d, then by smaller row, then by smaller column. If no dashmart is reachable, return (-1, - 1). Also return the chosen dashmart’s effective busy value for that location.

What a Strong Answer Covers

A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
A correctness argument that explains why the algorithm covers all required cases.
Time and space complexity, plus at least one alternative approach when relevant.
Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

How would the approach change if the input were streaming or too large for memory?
What invariants would you assert in production code?
Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Nearest Dashmart Distance (Part A)

You are given an m x n grid of characters where 'D' marks a dashmart, 'X' marks an impassable cell, and ' ' (a single space) marks a passable cell. Movement is allowed only in the four cardinal directions (up, down, left, right); you may not leave the grid or step onto an 'X'.

Given a list of query locations (row, col), return for each query the number of steps in the shortest path from that location to the nearest dashmart. If the starting cell is itself a dashmart the distance is 0. If the starting cell is 'X', is out of bounds, or has no path to any dashmart, return -1 for that query.

Implement nearestDistances(grid, queries) returning a list of integers, one per query, in the same order.

Constraints

1 <= m, n in the non-empty case; the grid may also be empty.
Each cell is one of 'D', 'X', or ' ' (single space).
Movement is 4-directional; no diagonal moves.
Queries may reference 'X' cells or out-of-bounds coordinates, which yield -1.
Multiple dashmarts may exist; the answer is the distance to whichever is nearest.

Examples

Example 1

Input: ([['D', ' ', ' '], [' ', 'X', ' '], [' ', ' ', 'D']], [[0, 0], [1, 0], [1, 2], [0, 2]])
Output: [0, 1, 1, 2]

Explanation: Query (0,0) is a dashmart -> 0. (1,0) is one step from the top-left 'D'. (1,2) is one step from the bottom-right 'D'. (0,2) routes around the wall: (0,2)->(0,1)->(0,0) costs 2 (the wall blocks a shorter path to the bottom 'D').

Example 2

Input: ([[' ', ' ', ' '], [' ', 'X', ' '], [' ', ' ', ' ']], [[0, 0], [2, 2]])
Output: [-1, -1]

Explanation: There are no dashmarts anywhere, so every query is unreachable and returns -1.

Hints

Instead of running a BFS from every query, seed a single BFS queue with ALL dashmart cells at distance 0 (multi-source BFS). The first time any cell is reached is its distance to the nearest dashmart.
Initialize every dashmart's distance to 0 and enqueue it before the BFS loop starts.
After the BFS fills the distance grid, each query is just a bounds + 'X' check followed by a lookup; an unreached passable cell stays at infinity and maps to -1.

Busiest Reachable Dashmart Assignment (Part B follow-up)

Same grid model as Part A: 'D' is a dashmart, 'X' is impassable, ' ' is passable, and movement is 4-directional. Now each dashmart at (r, c) has a non-negative base busy score given by busy[r][c] (entries for non-'D' cells are irrelevant and may be 0), and you are given an integer alpha >= 0.

For a query location, define the effective busy of a reachable dashmart at grid distance d as max(0, busy[r][c] - alpha * d). For each query, among all reachable dashmarts choose the one with the LARGEST effective busy. Break ties by smaller distance d, then by smaller row, then by smaller column. Return [row, col, effectiveBusy] for the chosen dashmart. If the query cell is 'X', out of bounds, or no dashmart is reachable, return [-1, -1, -1] for that query.

Implement busiestAssignments(grid, queries, busy, alpha) returning a list of [row, col, effectiveBusy] triples, one per query.

Constraints

alpha >= 0 (integer); busy scores are non-negative integers.
Effective busy is floored at 0: max(0, busy - alpha*d).
Part B needs the distance to EVERY reachable dashmart (not just the nearest), so a per-query BFS is used rather than the single multi-source BFS of Part A.
Tie-break order is strict: larger effective busy first, then smaller distance, then smaller row, then smaller column.
An 'X' or out-of-bounds query, or one with no reachable dashmart, yields [-1, -1, -1].

Examples

Example 1

Input: ([['D', ' ', 'D']], [[0, 1]], [[10, 0, 8]], 1)
Output: [[0, 0, 9]]

Explanation: From (0,1) both dashmarts are at distance 1. Effective busy: left = 10-1 = 9, right = 8-1 = 7. The left dashmart (0,0) wins with 9.

Example 2

Input: ([['D', ' ', 'D']], [[0, 1]], [[10, 0, 8]], 5)
Output: [[0, 0, 5]]

Explanation: With alpha=5: left = max(0, 10-5) = 5, right = max(0, 8-5) = 3. Left (0,0) wins with 5.

Hints

Part A's nearest-only multi-source BFS is insufficient here: a farther dashmart can still win on effective busy, so you need the distance to every reachable dashmart from each query.
Run one BFS per query from the query cell across passable cells, recording the distance to each dashmart you reach.
Encode the selection as a single comparable key: minimize (-effectiveBusy, d, row, col). The smallest such tuple is exactly 'max effective busy, then smallest d, then smallest row, then smallest col'.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Recommended Approach

Model the states explicitly and use BFS for unweighted shortest paths, Dijkstra for weighted non-negative paths, or topological DP for DAGs. Track visited states at the right granularity so cycles do not cause repeated work.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

BFS is O(V + E) time and O(V) space for a standard graph. Expanded-state problems multiply those bounds by the number of state dimensions.

Edge Cases and Tests

Disconnected graph, source equals target, cycles, duplicate edges, unreachable target, and whether the answer counts nodes, edges, moves, or transfers.