DoorDash·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

DoorDash coding interview with a grid traversal problem that looks deceptively straightforward until you realize brute force won't cut it.

Questions Asked (1)

You're given an n x n grid where each cell holds the earliest time you can enter it. Starting at the top-left corner, you can move in four directions but only into a cell when the current time is at least that cell's value. What's the minimum time needed to reach the bottom-right corner?

Algorithms & Data Structures

Author's notes

My first instinct was BFS and I started coding it before really thinking through the time constraint mechanics.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the grid as a graph where each cell's weight is its entry time, and the cost to enter a cell is max(current_time, cell_value). Use a modified Dijkstra's algorithm with a priority queue to always expand the cell with the smallest arrival time, updating neighbors accordingly. The answer is the time when the bottom-right cell is first popped.

Pro tip: Clarify that waiting is allowed and that the cost function is max(current_time, cell_value), not addition. Mention that this is a minimax path problem and can also be solved with binary search + BFS, but Dijkstra is more efficient.

1. Understand the problem

Restate the problem: find the minimum time to reach (n-1, n-1) from (0,0) where you can move in 4 directions and can only enter a cell if current time >= cell's value. Note that you can wait, so time never decreases.

2. Define state and cost

Define the state as (time, row, col). The cost to move from a cell with time t to a neighbor with value v is max(t, v). This is the earliest time you can be at the neighbor.

3. Choose algorithm

Use Dijkstra's algorithm because edge weights are non-negative and we want the minimum time to each cell. Initialize a min-heap with (grid[0][0], 0, 0) and a distance array with infinity.

4. Implement Dijkstra

While the heap is not empty, pop the cell with the smallest time. If it's the target, return the time. Otherwise, for each neighbor, compute new_time = max(current_time, grid[nr][nc]) and if it's less than the stored distance, update and push to heap.

5. Analyze complexity

Time complexity is O(n^2 log n) due to heap operations on up to n^2 nodes. Space complexity is O(n^2) for the distance array and heap.

Key Points to Mention

The cost to enter a cell is max(current_time, cell_value), not addition.
Dijkstra's algorithm is suitable because we want the minimum time and edge weights are non-negative.
You can wait, so time never decreases; this is a minimax path problem.
Alternative approach: binary search on the answer + BFS to check feasibility, but Dijkstra is more efficient.
Use a priority queue to always process the cell with the smallest arrival time.
Handle edge cases: n=1 (start is target), large grid values, and unreachable cells (though problem implies reachable).

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