DoorDash·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

DoorDash SWE coding round, two parts to a single grid-based problem. The follow-up was a lot heavier than I expected and I don't think I fully nailed the tie-breaking logic under pressure.

Questions Asked (2)

Given an m x n character grid with dashmarts ('D'), impassable cells ('X'), and open cells, write a function that takes a list of query locations and returns the shortest distance from each location to the nearest dashmart. Return -1 if the cell is impassable or no dashmart is reachable.

Algorithms & Data Structures

Author's notes

Multi-source BFS from all dashmarts simultaneously, precompute distances, then answer queries in O(1).

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use multi-source BFS starting from all dashmarts simultaneously to compute the shortest distance to the nearest dashmart for every cell in one pass. Then answer each query in O(1) by looking up the precomputed distance, returning -1 for impassable cells or unreachable cells.

Pro tip: Mention that multi-source BFS is optimal because it explores each cell once, and clarify that you would handle edge cases like no dashmarts, queries on impassable cells, and large grids by using a queue and distance matrix.

1. Clarify and Validate Input

Confirm grid dimensions, cell types, and query format. Check for edge cases like empty grid or no dashmarts.

2. Initialize Multi-Source BFS

Create a distance matrix initialized to -1. Enqueue all dashmart coordinates with distance 0.

3. Run BFS to Compute Distances

Process queue, exploring 4-directional neighbors. Skip impassable cells and already visited cells. Update distances and enqueue.

4. Answer Queries

For each query, return the precomputed distance if the cell is open and reachable; otherwise return -1.

5. Analyze Complexity

State time complexity O(m*n + q) and space complexity O(m*n), where q is number of queries.

Key Points to Mention

Multi-source BFS treats all dashmarts as sources at distance 0, ensuring shortest paths.
Distance matrix stores shortest distance to nearest dashmart for each cell.
Impassable cells ('X') are never enqueued and their distance remains -1.
Queries are answered in O(1) time after precomputation.
Edge cases: no dashmarts, queries on impassable cells, unreachable open cells.
Time complexity O(m*n + q) and space complexity O(m*n).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Extend the previous grid problem: each dashmart has a base busy score, and its effective busy score for a query at distance d is max(0, base - alpha * d). For each query, find the reachable dashmart that maximizes this effective busy score, breaking ties by shortest distance, then by row, then by column. Return the dashmart coordinates and its effective busy value.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is where I started to sweat.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and define the scoring function precisely, then discuss algorithmic options like precomputing nearest dashmarts or using a priority queue for each query. Emphasize the tie-breaking rules and how to efficiently compute effective busy scores.

Pro tip: Mention that you would precompute the nearest dashmarts for each cell to avoid scanning all dashmarts per query, and use a heap to maintain the top candidates according to the tie-breaking order.

1. Clarify the problem

Ask about grid size, number of dashmarts, number of queries, and whether queries are online or offline. Confirm the distance metric (Manhattan or Euclidean) and the tie-breaking order.

2. Define the scoring function

Restate the effective busy score formula: max(0, base - alpha * d). Note that alpha may be given per query or globally, and that distance d is the shortest path distance from the query cell to the dashmart.

3. Choose an algorithm

Propose a multi-source BFS from all dashmarts to compute nearest dashmarts for each cell, or for each query, use a priority queue to explore reachable dashmarts in order of effective busy score. Discuss trade-offs between precomputation and per-query computation.

4. Handle tie-breaking

Explain how to compare candidates: first by effective busy score (descending), then by distance (ascending), then by row (ascending), then by column (ascending). Use a custom comparator or sort key.

5. Analyze complexity and optimize

State the time and space complexity of your approach. If needed, optimize by pruning dashmarts that cannot beat the current best due to distance or base score.

Key Points to Mention

Distance metric and how to compute it efficiently (e.g., BFS for unweighted grid).
The effective busy score formula and its implications (e.g., score becomes zero beyond a certain distance).
Tie-breaking rules and how to implement them correctly.
Trade-offs between precomputing nearest dashmarts for all cells vs. computing per query.
Use of a priority queue or sorting to select the best dashmart.
Edge cases: no reachable dashmart, multiple dashmarts with same score and distance, alpha = 0.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.