DoorDash·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

DoorDash software engineer round, one algorithmic problem the whole time. Pretty standard multi-source BFS setup but the edge case around empty grids tripped me up a bit.

Questions Asked (1)

Given a grid of 0s and 1s where 1s are source cells, return a same-sized matrix where each cell contains its shortest distance (4-directional) to the nearest source cell. Source cells have distance 0. If no source cells exist, every cell should return -1.

Algorithms & Data Structures

Author's notes

I knew it was BFS pretty fast, the multi-source part clicked quickly too.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use multi-source BFS: initialize a queue with all source cells (value 1) and set their distances to 0. Then perform BFS level by level, updating each unvisited neighbor's distance as current distance + 1. If no sources exist, return a matrix filled with -1.

Pro tip: Mention that multi-source BFS is optimal because it processes each cell once, achieving O(m*n) time and space. Also, clarify that you handle the no-source case upfront to avoid unnecessary BFS.

1. Understand the problem and edge cases

Confirm that distance is Manhattan (4-directional) and that source cells have distance 0. Identify the edge case where there are no source cells, requiring all cells to be -1.

2. Choose the right algorithm

Select multi-source BFS because it efficiently computes shortest distances from multiple sources simultaneously. Avoid naive BFS from each cell, which would be O((m*n)^2).

3. Initialize data structures

Create a distance matrix initialized to -1 (or a large number) and a queue. Enqueue all source cells and set their distance to 0.

4. Perform BFS

While the queue is not empty, dequeue a cell and explore its 4 neighbors. For each unvisited neighbor, set its distance to current distance + 1 and enqueue it.

5. Return the result

After BFS, the distance matrix contains the shortest distances for all reachable cells. If no sources were found, the matrix remains all -1, which is correct.

Key Points to Mention

Multi-source BFS treats all sources as starting points at distance 0, ensuring correct shortest distances.
Time complexity is O(m*n) because each cell is enqueued at most once.
Space complexity is O(m*n) for the queue and distance matrix in the worst case.
The no-source case is handled by initializing the distance matrix to -1 and only updating reachable cells.
4-directional movement means only up, down, left, right neighbors are considered.
BFS guarantees the shortest path in an unweighted grid.

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