Utoljára aktív 5 days ago

Interview prep notes

linkjobai gist felülvizsgálása 5 days ago. Revízióhoz ugrás

1 file changed, 42 insertions

editdist.md(fájl létrehozva)

@@ -0,0 +1,42 @@
1 + # Edit Distance: A Dynamic Programming Walkthrough
2 +
3 + **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.
4 +
5 + ## Define the state
6 +
7 + `dp[i][j]` = minimum edits to turn the first `i` characters of `a` into the first `j` characters of `b`.
8 +
9 + - If `a[i-1] == b[j-1]`: `dp[i][j] = dp[i-1][j-1]`.
10 + - Otherwise: `1 + min(dp[i-1][j]` (delete), `dp[i][j-1]` (insert), `dp[i-1][j-1]` (replace)`)`.
11 + - Base cases: `dp[i][0] = i`, `dp[0][j] = j`.
12 +
13 + ```python
14 + def min_distance(a, b):
15 + prev = list(range(len(b) + 1))
16 + for i in range(1, len(a) + 1):
17 + cur = [i] + [0] * len(b)
18 + for j in range(1, len(b) + 1):
19 + if a[i-1] == b[j-1]:
20 + cur[j] = prev[j-1]
21 + else:
22 + cur[j] = 1 + min(prev[j], cur[j-1], prev[j-1])
23 + prev = cur
24 + return prev[-1]
25 + ```
26 +
27 + Time O(mn); space O(n) with the rolling row.
28 +
29 + ## How to present it
30 +
31 + 1. Start from recursion: "compare the last characters; three choices if they differ."
32 + 2. Point out the overlapping subproblems and add memoisation.
33 + 3. Convert to the bottom-up table, then compress to one row.
34 +
35 + Walking through those steps out loud is exactly what interviewers mean by "show your thought process."
36 +
37 + ## Same template, other problems
38 +
39 + Longest Common Subsequence (1143), Delete Operation for Two Strings (583), and One Edit Distance (161), which has an O(n) shortcut.
40 +
41 + ---
42 + *Disclosure: I help build [Linkjob AI](https://www.linkjob.ai/), an AI interview helper.*
Újabb Régebbi