Longest Common Subsequence (LCS)
As a Senior engineer, explain Longest Common Subsequence (LCS). What problem does it solve and how would you describe it in an interview?
Answers use simple, clear English.
Quick interview answer
At Senior depth: start with the problem, then mechanism, then a short example. Classic 2D DP: if s[i]==t[j], dp[i][j]=dp[i-1][j-1]+1 else max(dp[i-1][j], dp[i][j-1]).
Detailed answer
At Senior depth: start with the problem, then mechanism, then a short example. Classic 2D DP: if s[i]==t[j], dp[i][j]=dp[i-1][j-1]+1 else max(dp[i-1][j], dp[i][j-1]). Subsequence allows gaps; not substring. Core: Classic 2D DP: if s[i]==t[j], dp[i][j]=dp[i-1][j-1]+1 else max(dp[i-1][j], dp[i][j-1]). Subsequence allows gaps; not substring. Real-time example: Git diff: LCS of two file lines gives minimal edit script baseline for diff algorithms. Pros: Foundation for edit distance, diff tools, bioinformatics alignment. Cons: O(mn) time and space; Hirschberg or rolling array for space optimization. Common mistakes: Confusing subsequence with substring (contiguous); off-by-one on empty base row/col. Best practices: Fill dp table with 0-indexed strings + sentinel row/col; trace back for reconstruction. Audience level: Senior.
Full explanation
Classic 2D DP: if s[i]==t[j], dp[i][j]=dp[i-1][j-1]+1 else max(dp[i-1][j], dp[i][j-1]). Subsequence allows gaps; not substring.
Real example & use case
Git diff: LCS of two file lines gives minimal edit script baseline for diff algorithms.
Pros & cons
Pros: Foundation for edit distance, diff tools, bioinformatics alignment. Cons: O(mn) time and space; Hirschberg or rolling array for space optimization.
Common mistakes
Confusing subsequence with substring (contiguous); off-by-one on empty base row/col.
Best practices
Fill dp table with 0-indexed strings + sentinel row/col; trace back for reconstruction.
Follow-up questions
- How would you test Longest Common Subsequence (LCS)?
- What metrics prove Longest Common Subsequence (LCS) is healthy in prod?
- How does Longest Common Subsequence (LCS) change at 10× traffic?