How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Find longest common ordered restaurant list

Q: Find longest common ordered restaurant list

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.

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.

Input: ([], ["X","Y"])

Expected Output: []

Explanation: Edge case: driver1 is empty, so there is no common restaurant and the result is empty.

Input: (["R1","R2","R3"], [])

Expected Output: []

Explanation: Edge case: driver2 is empty, so the result is empty.

Input: (["A","B","C"], ["D","E","F"])

Expected Output: []

Explanation: No restaurant is shared between the two drivers, so the longest common list is empty.

Input: (["P","Q","R"], ["P","Q","R"])

Expected Output: ["P", "Q", "R"]

Explanation: Both lists are identical, so the entire sequence is the longest common ordered list.

Input: (["X"], ["X"])

Expected Output: ["X"]

Explanation: Single shared restaurant in both lists.

Input: (["a","A","a"], ["A","a","A"])

Expected Output: ["A", "a"]

Explanation: Restaurant IDs are case-sensitive: 'a' and 'A' are distinct. The longest ordered overlap is ['A','a'].

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.

Quick Overview

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.