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 nearest dashmart and busiest assignments

Quick Overview

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.

Compute nearest dashmart and busiest assignments

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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.

Quick Answer: 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.

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

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

Expected 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').

Input: ([[' ', ' ', ' '], [' ', 'X', ' '], [' ', ' ', ' ']], [[0, 0], [2, 2]])

Expected Output: [-1, -1]

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

Input: ([['D']], [[0, 0]])

Expected Output: [0]

Explanation: Single-cell grid that is itself a dashmart; distance is 0.

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

Expected Output: [-1, 0]

Explanation: Query (0,0) is a wall -> -1. Query (0,1) is the dashmart -> 0.

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

Expected Output: [-1, 1, 2]

Explanation: (0,0) is boxed in by walls on both neighbors -> unreachable -> -1. (1,2) is adjacent to the top-right 'D' -> 1. (2,2) reaches the nearest 'D' in 2 steps (e.g. (2,2)->(2,1)->(2,0)).

Input: ([], [[0, 0]])

Expected Output: [-1]

Explanation: Empty grid edge case: no cells, so the query is unreachable -> -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

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

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

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

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

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

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

Explanation: Both have effective busy 5-1 = 4 (a tie on value and distance). Tie broken by smaller row then column -> (0,0).

Input: ([['D', ' ', 'D']], [[0, 1]], [[100, 0, 100]], 1000)

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

Explanation: alpha*d = 1000 swamps both base scores, so each effective busy floors to 0. The tie at value 0 is broken to the smaller (row, col) -> (0,0) with effective busy 0.

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

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

Explanation: From (0,2) the wall at (0,1) blocks the only path to the dashmart, so no dashmart is reachable -> [-1,-1,-1].

Input: ([['X']], [[0, 0]], [[0]], 0)

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

Explanation: The query cell itself is a wall -> [-1,-1,-1].

Input: ([['D', ' ', 'D'], [' ', ' ', ' '], ['D', ' ', 'D']], [[1, 1]], [[20, 0, 20], [0, 0, 0], [20, 0, 50]], 3)

Expected Output: [[2, 2, 44]]

Explanation: From the center (1,1) all four corner dashmarts are at distance 2. Effective busy: three corners give 20-6 = 14, but (2,2) gives 50-6 = 44, which is the max.

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

Quick Overview

Compute nearest dashmart and busiest assignments

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Nearest Dashmart Distance (Part A)

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

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

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

Input: ([[' ', ' ', ' '], [' ', 'X', ' '], [' ', ' ', ' ']], [[0, 0], [2, 2]])

Expected Output: [-1, -1]

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

Input: ([['D']], [[0, 0]])

Expected Output: [0]

Explanation: Single-cell grid that is itself a dashmart; distance is 0.

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

Expected Output: [-1, 0]

Explanation: Query (0,0) is a wall -> -1. Query (0,1) is the dashmart -> 0.

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

Expected Output: [-1, 1, 2]

Explanation: (0,0) is boxed in by walls on both neighbors -> unreachable -> -1. (1,2) is adjacent to the top-right 'D' -> 1. (2,2) reaches the nearest 'D' in 2 steps (e.g. (2,2)->(2,1)->(2,0)).

Input: ([], [[0, 0]])

Expected Output: [-1]

Explanation: Empty grid edge case: no cells, so the query is unreachable -> -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)

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

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

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

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

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

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

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

Explanation: Both have effective busy 5-1 = 4 (a tie on value and distance). Tie broken by smaller row then column -> (0,0).

Input: ([['D', ' ', 'D']], [[0, 1]], [[100, 0, 100]], 1000)

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

Explanation: alpha*d = 1000 swamps both base scores, so each effective busy floors to 0. The tie at value 0 is broken to the smaller (row, col) -> (0,0) with effective busy 0.

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

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

Explanation: From (0,2) the wall at (0,1) blocks the only path to the dashmart, so no dashmart is reachable -> [-1,-1,-1].

Input: ([['X']], [[0, 0]], [[0]], 0)

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

Explanation: The query cell itself is a wall -> [-1,-1,-1].

Input: ([['D', ' ', 'D'], [' ', ' ', ' '], ['D', ' ', 'D']], [[1, 1]], [[20, 0, 20], [0, 0, 0], [20, 0, 50]], 3)

Expected Output: [[2, 2, 44]]

Explanation: From the center (1,1) all four corner dashmarts are at distance 2. Effective busy: three corners give 20-6 = 14, but (2,2) gives 50-6 = 44, which is the max.

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