DoorDash·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

DoorDash technical phone screen for a software engineer role, basically one meaty grid traversal problem with a couple of follow-ups tacked on at the end. The core question wasn't too bad but the extensions pushed into territory I wasn't totally prepared for.

Questions Asked (3)

You're given a 2D grid where cells are either walls, exits, or empty rooms. Fill each empty room with its shortest distance (using 4-directional moves) to the nearest exit. If a room can't reach any exit, leave it unchanged. Walk through your approach and analyze the time and space complexity.

Algorithms & Data Structures

Author's notes

Went with multi-source BFS seeded from all exits simultaneously, which is the right call.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use multi-source BFS starting from all exits simultaneously, updating each empty room with its distance from the nearest exit. This ensures each cell is visited once, and unreachable rooms remain unchanged.

Pro tip: Mention that BFS from exits is more efficient than running BFS from each empty room, and clarify that the grid is modified in-place to save space.

1. Clarify problem and constraints

Confirm grid dimensions, movement directions, and what values represent walls, exits, and empty rooms. Ask if modifying the grid in-place is acceptable.

2. Initialize BFS queue

Scan the grid to enqueue all exit cells and mark them as visited (or use a separate visited set). Set their distance to 0.

3. Perform multi-source BFS

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

4. Handle unreachable rooms

After BFS, any empty room still holding its original value (e.g., INF) remains unchanged, as it cannot reach any exit.

5. Analyze complexity

Time complexity is O(m*n) since each cell is processed once. Space complexity is O(m*n) for the queue in the worst case.

Key Points to Mention

Multi-source BFS treats all exits as sources, ensuring shortest distances are found in one pass.
Using a queue for BFS guarantees level-order traversal, which naturally computes shortest paths in unweighted graphs.
In-place modification avoids extra space for a distance matrix, but a visited set may be needed if original values must be preserved.
Walls are skipped during neighbor exploration, and exits are not overwritten.
Unreachable rooms are left unchanged because they are never visited by BFS.
Time complexity is O(m*n) and space complexity is O(m*n) due to the queue, which is optimal for this problem.

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

How would you extend this solution to work across multiple floors, essentially a 3D grid?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Pretty straightforward extension once you see it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the original solution and its assumptions (e.g., 2D grid, movement rules). Then, generalize the state representation to include a floor coordinate and adapt the algorithm (e.g., BFS/DFS) to handle 3D neighbors. Finally, discuss trade-offs like memory, time complexity, and potential optimizations.

Pro tip: Mention that the core algorithm often remains the same, but the state space grows, so you should discuss how to handle increased complexity (e.g., using A* with a 3D heuristic). Also, consider practical constraints like elevator/staircase connectivity between floors.

1. Clarify the original solution

Restate the original problem and solution to ensure alignment, including the grid dimensions, movement rules, and algorithm used.

2. Generalize the state representation

Extend the state from (x, y) to (x, y, z) where z represents the floor. Update neighbor generation to include up/down movements if allowed.

3. Adapt the algorithm

Modify the algorithm to handle 3D states. For BFS/DFS, the logic remains similar; for A*, update the heuristic to be admissible in 3D (e.g., Manhattan distance in 3D).

4. Analyze trade-offs

Discuss time and space complexity changes: O(N^3) instead of O(N^2). Mention potential optimizations like bidirectional search or pruning.

5. Consider practical constraints

Address real-world constraints: connectivity between floors (elevators/stairs), obstacles, and whether movement between floors is uniform or restricted.

Key Points to Mention

State space expansion: from 2D to 3D coordinates
Neighbor generation: adding up/down movements
Algorithm adaptation: BFS/DFS/A* with 3D heuristic
Time and space complexity: O(N^3) vs O(N^2)
Connectivity constraints: elevators, stairs, or open spaces
Optimization techniques: bidirectional search, pruning, or hierarchical pathfinding

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

What if movement between cells had different costs instead of uniform steps? How would your approach change?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is where I got a little shaky.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify that the problem shifts from BFS to Dijkstra's algorithm or A* with a cost function, since uniform steps no longer apply. Then, discuss how to model the costs (e.g., weighted graph, cost matrix) and analyze the impact on time/space complexity and algorithm choice. Finally, mention trade-offs like using heuristics for A* or bidirectional search, and how to handle negative costs if they exist.

Pro tip: Emphasize that the core algorithmic pattern changes from BFS to Dijkstra, but also consider real-world constraints like memory and whether costs are static or dynamic. Showing awareness of DoorDash's logistics context (e.g., varying delivery times) can set you apart.

1. Clarify the problem

Confirm that movement costs are now non-uniform and ask if costs are positive, static, and known in advance. This determines if Dijkstra's or Bellman-Ford is appropriate.

2. Model the grid as a weighted graph

Represent each cell as a node and each possible move as a directed edge with a weight equal to the cost of entering the destination cell (or traversing the edge).

3. Choose the right algorithm

Replace BFS with Dijkstra's algorithm for non-negative weights, or A* if a heuristic is available. Discuss why BFS fails and how priority queues change the complexity.

4. Analyze complexity and trade-offs

Compare time/space complexity: Dijkstra O(E log V) vs BFS O(V+E). Mention optimizations like early termination, bidirectional search, or using a heuristic to reduce explored nodes.

5. Address edge cases and extensions

Consider negative costs (use Bellman-Ford), dynamic costs (recompute or use online algorithms), and memory constraints (e.g., implicit graph representation).

Key Points to Mention

BFS is insufficient because it assumes uniform edge weights; Dijkstra's algorithm handles non-uniform positive weights.
Modeling the grid as a weighted graph: nodes are cells, edges have costs based on movement rules.
Time complexity changes from O(V+E) to O(E log V) with a priority queue, and space complexity may increase.
A* search with an admissible heuristic can improve performance if a good heuristic exists (e.g., Manhattan distance scaled by minimum cost).
Handling negative costs requires Bellman-Ford, but typically movement costs are non-negative.
Real-world considerations: dynamic costs, memory limits, and potential for bidirectional search to reduce search space.

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