DoorDash·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

DoorDash coding round, grid problem that looked straightforward until I realized brute force BFS per cell was going to be way too slow. The multi-source angle was the whole point and I almost missed it.

Questions Asked (1)

Given an m by n grid where some cells are stores, some are walls, and the rest are open, find the shortest distance from every walkable cell to its nearest store. How do you approach this efficiently?

Algorithms & Data Structures

Author's notes

My first instinct was to BFS from each walkable cell separately, which works but is obviously O((m*n)^2) in the worst case and they were not happy with that.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use multi-source BFS starting from all store cells simultaneously, treating the grid as an unweighted graph. Initialize a distance matrix with 0 for stores and infinity for others, then propagate distances level by level to all walkable neighbors.

Pro tip: Mention that multi-source BFS is optimal because it computes distances in O(mn) time, and highlight how it naturally handles multiple stores without redundant work. Also, discuss edge cases like no stores or unreachable cells to show thoroughness.

1. Clarify problem and constraints

Confirm grid dimensions, movement directions (4-way or 8-way), and what constitutes a walkable cell. Ask about input format and expected output.

2. Choose algorithm

Select multi-source BFS over alternatives like running BFS from each store (O(S*mn)) or Dijkstra (unnecessary for unweighted). Explain why BFS is optimal.

3. Initialize data structures

Create a distance matrix initialized to infinity, and a queue. Enqueue all store cells with distance 0.

4. Run BFS

While queue not empty, dequeue a cell, explore its walkable neighbors. If a neighbor's distance is infinity, set it to current distance + 1 and enqueue.

5. Return result and discuss complexity

Return the distance matrix. Analyze time and space complexity as O(mn). Mention handling of unreachable cells (remain infinity).

Key Points to Mention

Multi-source BFS treats all stores as sources at distance 0, propagating simultaneously.
Time complexity O(mn) and space O(mn) for the distance matrix and queue.
Walls are impassable and should be skipped; stores are walkable but have distance 0.
Unreachable walkable cells remain at infinity (or -1) in the output.
Alternative approaches like BFS from each store are less efficient (O(S*mn)).
Use a queue for BFS and a 2D array for distances; avoid recursion to prevent stack overflow.

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