DoorDash·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026Remote

Summary

DoorDash coding round focused entirely on a grid BFS problem with a DoorDash-flavored skin on it. One question, pretty involved, and they pushed hard on scaling and edge cases.

Questions Asked (1)

Given an m x n grid where cells are either walls, stores, or empty rooms, and a list of query coordinates each pointing to an empty room, return the shortest distance from each queried cell to the nearest store. Return -1 if unreachable. Your solution should scale efficiently when the query list is large, and you need to handle edge cases like duplicate queries, isolated rooms, empty query lists, and grids with no stores at all.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to run BFS from each query point separately, which works fine for small inputs but falls apart when k is large.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use multi-source BFS from all stores simultaneously to compute the shortest distance to the nearest store for every cell in O(m*n) time. Then answer each query in O(1) by looking up the precomputed distance, handling duplicates and unreachable cases. This approach scales efficiently for large query lists.

Pro tip: Mention that you can optimize memory by storing distances in a 2D array and reusing it for all queries, and that you can early-exit BFS if all reachable cells are covered. Also, discuss how to handle duplicate queries by caching results to avoid redundant lookups.

1. Clarify requirements and edge cases

Confirm grid dimensions, cell types (walls, stores, empty), and query format. Discuss edge cases: no stores, empty query list, duplicate queries, isolated rooms, and unreachable cells.

2. Choose multi-source BFS

Explain that multi-source BFS from all stores computes shortest distances to the nearest store for all cells in one pass, which is more efficient than running BFS per query.

3. Implement BFS and distance matrix

Initialize a queue with all store coordinates, set their distance to 0, and perform BFS to fill a 2D distance array. Mark unreachable cells as -1.

4. Answer queries efficiently

For each query, return the precomputed distance from the distance matrix. Handle duplicates by caching results or simply returning the same value.

5. Analyze complexity and trade-offs

State time complexity O(m*n + q) and space O(m*n). Discuss trade-offs: precomputation cost vs. per-query cost, and suitability for large query lists.

Key Points to Mention

Multi-source BFS from all stores simultaneously
Precomputing distances for all cells to answer queries in O(1)
Handling edge cases: no stores, empty queries, duplicates, unreachable cells
Time and space complexity: O(m*n) preprocessing, O(1) per query
Trade-off: precomputation vs. per-query BFS for large query lists
Using a queue for BFS and a 2D array for distances

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