Остання активність 5 days ago

Interview prep notes

editdist.md Неформатований

Edit Distance: A Dynamic Programming Walkthrough

Edit Distance (LeetCode 72) asks for the minimum number of insertions, deletions and substitutions that turn one word into another. It's the textbook two-string DP and a good template for many others.

Define the state

dp[i][j] = minimum edits to turn the first i characters of a into the first j characters of b.

  • If a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1].
  • Otherwise: 1 + min(dp[i-1][j] (delete), dp[i][j-1] (insert), dp[i-1][j-1] (replace)).
  • Base cases: dp[i][0] = i, dp[0][j] = j.
def min_distance(a, b):
    prev = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        cur = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            if a[i-1] == b[j-1]:
                cur[j] = prev[j-1]
            else:
                cur[j] = 1 + min(prev[j], cur[j-1], prev[j-1])
        prev = cur
    return prev[-1]

Time O(mn); space O(n) with the rolling row.

How to present it

  1. Start from recursion: "compare the last characters; three choices if they differ."
  2. Point out the overlapping subproblems and add memoisation.
  3. Convert to the bottom-up table, then compress to one row.

Walking through those steps out loud is exactly what interviewers mean by "show your thought process."

Same template, other problems

Longest Common Subsequence (1143), Delete Operation for Two Strings (583), and One Edit Distance (161), which has an O(n) shortcut.


Disclosure: I help build Linkjob AI, an AI interview helper.