Find longest common ordered restaurant list
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You have two delivery drivers who each have a pickup plan represented as a list of restaurant IDs (strings).
Because there is only **one car**, the combined route can only visit restaurants that **both drivers need to pick up from**. The route must also respect the **original order** of restaurants for each driver (i.e., once you move forward in a driver’s list, you cannot go back).
Your task is to compute the **longest possible list of restaurants** that can be visited under these constraints.
Formally, given two sequences `driver1` and `driver2`, return a sequence that is the **longest common subsequence (LCS)** of the two lists.
### Input
- `driver1`: list of strings, length `n`
- `driver2`: list of strings, length `m`
### Output
- A list of strings representing one longest common ordered restaurant list.
### Notes
- The relative order must be preserved in both lists.
- If there are multiple valid longest answers, returning any one is acceptable (unless specified otherwise).
### Example
- `driver1 = ["A","B","C","D"]`
- `driver2 = ["B","C","E"]`
A valid output is `["B","C"]`.
### Constraints (reasonable interview assumptions)
- `0 <= n, m <= 2000` (adjust if needed)
- Restaurant IDs are case-sensitive strings
### Follow-ups (optional)
- What is the time and space complexity of your approach?
- Can you optimize space if only the length is needed vs. reconstructing the sequence?
Quick Answer: This question evaluates a candidate's understanding of sequence algorithms, dynamic programming, and string/list manipulation by requiring computation of the longest common subsequence between two ordered lists of restaurant IDs.
Two delivery drivers each have a pickup plan represented as a list of restaurant IDs (strings). Because there is only **one car**, the combined route can only visit restaurants that **both drivers** need to pick up from, and the route must respect the **original order** of restaurants for each driver — once you move forward in a driver's list, you cannot go back.
Given two sequences `driver1` and `driver2`, return one **longest common subsequence (LCS)** of the two lists: the longest list of restaurant IDs that appears in both, in the same relative order.
**Example**
- `driver1 = ["A", "B", "C", "D"]`
- `driver2 = ["B", "C", "E"]`
- A valid output is `["B", "C"]`.
**Notes**
- The relative order must be preserved in both lists.
- If there are multiple valid longest answers, returning any one is acceptable.
- Restaurant IDs are case-sensitive strings.
Constraints
- 0 <= n, m <= 2000
- Restaurant IDs are case-sensitive strings
- The relative order of picked restaurants must be preserved in both lists
- If multiple longest answers exist, any one valid LCS is acceptable
Examples
Input: (["A","B","C","D"], ["B","C","E"])
Expected Output: ["B", "C"]
Explanation: B then C appear in order in both lists; E and the rest cannot extend it, so the longest common ordered list has length 2.
Input: (["A","B","C","B","D","A","B"], ["B","D","C","A","B","A"])
Expected Output: ["B", "D", "A", "B"]
Explanation: The classic LCS case: a length-4 common subsequence. ['B','C','A','B'] is also valid and equally long; any one optimal answer is accepted.
Hints
- This is the classic Longest Common Subsequence problem — think of each driver's list as a sequence and find the longest ordered overlap.
- Let dp[i][j] be the LCS length of driver1[i:] and driver2[j:]. If driver1[i] == driver2[j], then dp[i][j] = 1 + dp[i+1][j+1]; otherwise dp[i][j] = max(dp[i+1][j], dp[i][j+1]).
- After filling the table, reconstruct one actual subsequence by walking from (0, 0): on a match, take the element and advance both pointers; otherwise advance toward the larger dp value.