DoorDash·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

DoorDash coding round, one algorithmic problem about scheduling deliveries for maximum profit. Pretty much a classic DP problem dressed up in DoorDash-flavored context, which I thought was a nice touch even if the underlying idea wasn't new.

Questions Asked (1)

Given a dasher's shift window defined by a start and end time, and a list of candidate deliveries each with their own start time, end time, and payout, find the subset of non-overlapping deliveries that fits within the shift and maximizes total profit.

Algorithms & Data Structures

Author's notes

I recognized the weighted job scheduling shape pretty quickly, which felt good.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a weighted interval scheduling problem, solvable with dynamic programming after sorting deliveries by end time. Filter out deliveries that don't fit entirely within the shift window, then compute the maximum profit using binary search to find the latest non-overlapping delivery.

Pro tip: Clarify edge cases upfront, such as deliveries that start before the shift or end after it, and whether partial overlaps are allowed. Also, mention that if the number of deliveries is small, a simpler O(n^2) DP is acceptable, but for large n, the O(n log n) approach is preferred.

1. Clarify the problem and constraints

Ask about the input size, whether deliveries must fit entirely within the shift, and if overlapping is strictly prohibited. Confirm that the goal is to maximize total payout.

2. Filter and sort deliveries

Remove any delivery that starts before the shift start or ends after the shift end. Sort the remaining deliveries by their end times.

3. Define DP state and recurrence

Let dp[i] be the maximum profit using deliveries up to index i (sorted by end time). For each delivery i, find the latest non-overlapping delivery j using binary search, then dp[i] = max(dp[i-1], payout[i] + dp[j]).

4. Implement and optimize

Implement the DP with binary search for O(n log n) time. If n is small, a simpler O(n^2) approach is fine. Handle base cases and return dp[n].

5. Test and discuss trade-offs

Walk through a small example to verify correctness. Discuss time and space complexity, and mention alternative approaches like greedy (which fails) or graph-based methods.

Key Points to Mention

Weighted interval scheduling is the underlying algorithmic pattern.
Sorting by end time enables efficient binary search for non-overlapping intervals.
Dynamic programming recurrence: dp[i] = max(dp[i-1], profit[i] + dp[prev(i)]).
Time complexity: O(n log n) with binary search, O(n^2) without.
Edge cases: deliveries outside shift window, zero deliveries, all overlapping.
Space complexity can be optimized to O(n) or even O(1) with careful implementation.

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