Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Google SWE coding round with a sequences problem that looks deceptively simple but has a neat theoretical underpinning. One question, pretty algorithmic, classic DP territory.

Questions Asked (1)

Given two finite sequences and an integer L, determine whether there exists a sequence of length at most L that contains both input sequences as subsequences. Return true or false.

Algorithms & Data Structures

Author's notes

The key insight I kept circling around was connecting this to shortest common supersequence length.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding the shortest common supersequence (SCS) of the two sequences and check if its length is ≤ L. Use dynamic programming to compute the SCS length, which is |A| + |B| - LCS(A, B), where LCS is the longest common subsequence. Alternatively, use a two-pointer greedy approach to merge the sequences optimally, but DP is more straightforward for correctness.

Pro tip: Clarify that the problem reduces to the shortest common supersequence, and mention that while DP gives the exact length, a greedy merge can also work if you always take the next character from the sequence that allows the other to catch up. This shows you understand both the theory and practical optimizations.

1. Understand the problem

Restate the problem: given sequences A and B, and integer L, determine if there exists a sequence S of length ≤ L such that both A and B are subsequences of S. This is equivalent to checking if the length of the shortest common supersequence (SCS) of A and B is ≤ L.

2. Relate to LCS

Recall that the length of the SCS of A and B is |A| + |B| - |LCS(A, B)|, where LCS is the longest common subsequence. So the problem reduces to computing the LCS length of A and B.

3. Compute LCS length

Use dynamic programming to compute the LCS length. Create a 2D table dp[i][j] representing the LCS length of prefixes A[0..i-1] and B[0..j-1]. Fill the table using the 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]).

4. Check against L

Compute SCS length as |A| + |B| - dp[|A|][|B|]. If this length is ≤ L, return true; otherwise, return false.

5. Discuss optimizations

Mention that space can be optimized to O(min(|A|, |B|)) using a 1D DP array. Also note that if L is very large, the answer is trivially true; if L is less than max(|A|, |B|), it's false.

Key Points to Mention

Shortest common supersequence (SCS) concept and its relation to the problem.
Formula: SCS length = |A| + |B| - LCS(A, B).
Dynamic programming approach for LCS with time complexity O(|A|*|B|).
Space optimization for LCS DP to O(min(|A|, |B|)).
Edge cases: L < max(|A|, |B|) => false; L ≥ |A| + |B| => true.
Alternative greedy merge approach and its correctness conditions.

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