~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

2-D dynamic programming

String DP (edit distance, LCS)

dp[i][j] over prefixes of two strings; palindromes by expanding or by length.

Visual guide Quiz (10) Spot the pattern
Notes

Recognise it when: there are two strings and you want an alignment (edit distance, LCS), or one string and you want palindromes or pattern matching.

# Edit distance: dp[i][j] = cost to turn a[:i] into b[:j]
dp[i][0] = i; dp[0][j] = j
dp[i][j] = dp[i-1][j-1] if a[i-1] == b[j-1] else 1 + min(
    dp[i-1][j],     # delete
    dp[i][j-1],     # insert
    dp[i-1][j-1])   # replace
  • LCS: match means 1 + dp[i-1][j-1], otherwise max(dp[i-1][j], dp[i][j-1]).
  • Longest palindromic substring: expand around 2n-1 centres, O(n^2) with O(1) memory.
  • Two rows are enough for O(min(n, m)) memory.

9 problems

Interview roadmap

2-D dynamic programming Grids, two strings, knapsacks, ranges.

String DP (edit distance, LCS) guide

esc