DoorDash·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

DoorDash coding round with a deceptively clean problem that turns out to be LCS in disguise. The delivery driver framing was clever enough that I almost missed what they were actually asking.

Questions Asked (1)

Two delivery drivers each have an ordered list of restaurants to pick up from. They share one car and can only stop at restaurants that appear on both lists, and they must visit them in the same relative order as each driver's original list. Find the longest sequence of restaurants they can visit together.

Algorithms & Data Structures

Author's notes

Took me a minute to see past the story.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as the Longest Common Subsequence (LCS) problem and clearly state that the answer is the LCS of the two ordered lists. Explain that LCS preserves relative order while allowing skips, which matches the constraint that drivers can only stop at shared restaurants in the same relative order. Then outline a dynamic programming solution with O(m*n) time and space, and optionally mention space optimization.

Pro tip: After presenting the DP solution, mention that if the lists are large and the alphabet of restaurants is small, you can optimize using the Hunt–Szymanski algorithm or by mapping one list to indices and finding the Longest Increasing Subsequence (LIS) of the other, reducing time to O((r + n) log n) where r is the number of matching pairs. This shows you understand trade-offs and can scale solutions.

1. Clarify the problem

Restate the problem in your own words and confirm that the goal is to find the longest sequence of restaurants that appear in both lists in the same relative order. Ask clarifying questions about input size, whether duplicates are possible, and if the output should be the sequence or just its length.

2. Identify the algorithmic pattern

Explain that this is exactly the Longest Common Subsequence (LCS) problem because we need to preserve relative order and can skip elements. Mention that LCS is a classic dynamic programming problem.

3. Describe the DP approach

Define dp[i][j] as the length of LCS of the first i restaurants in list A and first j in list B. Recurrence: if A[i-1] == B[j-1], dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base cases: dp[0][j] = dp[i][0] = 0.

4. Analyze complexity and optimize

State that time and space are O(m*n). Mention that space can be reduced to O(min(m,n)) by keeping only two rows. For further optimization, discuss the Hunt–Szymanski or LIS-based approach when appropriate.

5. Reconstruct the sequence (if needed)

If the interviewer wants the actual sequence, explain how to backtrack through the DP table or store parent pointers. Alternatively, if only the length is needed, skip this step.

Key Points to Mention

Longest Common Subsequence (LCS) is the core algorithm.
Dynamic programming with a 2D table and recurrence relation.
Time complexity O(m*n) and space complexity O(m*n), with space optimization to O(min(m,n)).
Handling duplicates: LCS naturally handles duplicates by matching occurrences in order.
Alternative optimization: reduce to Longest Increasing Subsequence (LIS) by mapping one list to indices and finding LIS of the other, achieving O((r + n) log n) where r is the number of matching pairs.
Edge cases: empty lists, no common restaurants, all restaurants common.

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