Amazon AI Engineer Interview Preparation Guide - Entry Level

Direct answer

Under a fixed compute budget, tune the hyperparameters with the biggest expected impact first (n_estimators, max_features, max_depth or min_samples_leaf), search with a random or Bayesian strategy rather than exhaustive grid search since it covers the space more efficiently per trial, and evaluate with OOB error during the search (it's essentially free) before confirming the shortlisted top configurations with k-fold cross-validation.

Structured elaboration

Which hyperparameters to prioritize. Not all random forest hyperparameters matter equally:

• max_features (features considered per split) has the largest effect on the bias-variance trade-off discussed elsewhere in this topic; it directly controls how correlated the trees are with each other, which is the main lever on ensemble variance.
• n_estimators (number of trees) mostly trades compute for variance reduction with diminishing returns past a point; cheap to sweep since more trees just means more (parallelizable) work, not a different model shape.
• max_depth / min_samples_leaf control each tree's own bias-variance trade-off; too deep and individual trees overfit, too shallow and the ensemble underfits regardless of how many trees you add.
• class_weight matters specifically when the target is imbalanced; otherwise low priority.

Given limited trials, spend the early budget on max_features and max_depth/min_samples_leaf, since these change what each tree can represent; treat n_estimators as something you can increase for the finalists almost for free once the other hyperparameters are set, since it's the cheapest one to scale up after the fact.

Search strategy. Grid search wastes budget on combinations that share a bad value along one axis; random search covers each hyperparameter's marginal range more efficiently for the same trial count, and is the reasonable default under a hard compute ceiling, and the right first choice for most searches. If the budget allows more than a couple dozen trials, an optional upgrade beyond that baseline is Bayesian optimization: instead of picking each trial randomly, it fits a cheap probabilistic model of which hyperparameter values tend to score well, based on the trials run so far (for example a Gaussian process or a tree-structured Parzen estimator), and uses that model to choose where to try next, so it typically needs fewer total trials than random search to reach a comparable score. This is depth beyond what most interviews require as a first answer, worth naming as an available option rather than leading with it. A practical middle ground: an initial batch of random trials to map the space broadly, then switch to Bayesian optimization for the remaining budget.

OOB vs. cross-validation for evaluation. OOB error comes for free from the bootstrap mechanism (no extra retraining), which makes it the natural choice for the exploratory phase of the search, when you want to screen many configurations cheaply. For the final handful of candidate configurations, confirm with stratified k-fold CV (or a genuine held-out test set); OOB and CV are both estimates of generalization error but computed via different resampling mechanics, and CV's fold-based averaging is the more standard, better-understood number to report as the final generalization estimate.

Worked example

Suppose the budget allows 40 total training runs (a stand-in for "compute budget," expressed in trial count rather than wall-clock time so it stays portable across hardware). Work the budget backward from the confirmation step: the final check runs 5-fold stratified CV on the top 3 finalist configurations, and a 5-fold CV run on one configuration costs about as much as 5 single-fold trials, so confirming 3 finalists costs $3 \times 5 = 15$ trial-equivalents. That leaves $40 - 15 = 25$ trials for the search phase itself: 18 trials of random search over max_features (uniform over {sqrt, log2, 0.3, 0.5, 0.8}), max_depth (uniform over {5, 10, 20, None}), and min_samples_leaf (log-uniform over [1, 50]), each evaluated by OOB error; then 7 trials of Bayesian optimization refining around the best region those random trials found. n_estimators is fixed at a moderate value (say 200) during the search phase to keep trials cheap, then increased (say to 500-800) for the final chosen configuration, since increasing tree count essentially never hurts and mostly costs compute, not risk. Total accounted-for cost: $18 + 7 + 15 = 40$, exactly the stated budget.

Trade-offs & pitfalls

• OOB error can diverge from true generalization error on small or imbalanced datasets (see the OOB tradeoffs discussed for out-of-bag error more generally); if the dataset is small, spend more of the budget on CV directly rather than relying heavily on OOB during search.
• Random and Bayesian search both still require you to define sensible ranges up front; a poorly chosen range (e.g., max_depth capped too low) will make the whole search converge to a mediocre optimum regardless of search strategy.
• Treating n_estimators as "always increase for the finalist" assumes you have leftover compute budget at the end reserved for that; if the budget is truly exhausted after the search phase, this step gets skipped and you ship with the tree count used during search.
• A common mistake is to search all hyperparameters jointly with equal trial allocation regardless of expected impact; under a genuinely tight budget, deliberately weighting the search toward max_features and max_depth/min_samples_leaf first gets more signal per trial than treating every hyperparameter as equally worth exploring.

Early stopping: monitor validation metric during training and stop when it stops improving to prevent overfitting. It acts as implicit regularization by limiting training time, preventing the model from fitting noise.
Implementation with noisy validation:

• Use a patience parameter: require N consecutive non-improving evaluations before stopping.
• Smooth metrics using rolling average or exponential moving average to reduce noise-driven stops.
• Use relative improvement threshold (delta) so tiny fluctuations don’t count as improvement.
• Check multiple metrics (validation loss + primary metric) and stop only when both plateau.
• For production training jobs: checkpoint the best model and continue training but keep periodic evaluation on larger/cleaner holdout to confirm improvements.
• Optionally employ ensemble of top-K checkpoints instead of single best.
  Example config: patience=10 evals, delta=0.001, EMA smoothing with alpha=0.2, checkpoint best model. This prevents premature stopping while still constraining overfitting.

The idea

Edit distance (also called Levenshtein distance) is the fewest single-character edits that turn one string into another, where an edit is an insertion, a deletion or a substitution. Look only at the last characters of the two strings. If they are equal, they cost nothing and the problem shrinks to the two shorter prefixes. If they differ, the last edit must be one of three things: delete the last character of the first string, insert the last character of the second, or replace one with the other. Take the cheapest of the three, plus one.

The five things to state

1. What one cell means. dp[i][j] is the fewest edits that turn the first i characters of a into the first j characters of b.
2. The transition. If a[i-1] == b[j-1], dp[i][j] = dp[i-1][j-1]. Otherwise dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), which are delete, insert and substitute in that order. Taking the diagonal on a match is safe, for this reason. Two neighbouring cells never differ by more than 1: from any set of edits for one cell you get a set for its neighbour by adding or removing one more insertion, deletion or substitution. Now suppose the last characters match. The delete option costs dp[i-1][j] + 1, and dp[i-1][j] is a neighbour of dp[i-1][j-1], so it is at least dp[i-1][j-1] - 1; the delete option is therefore at least dp[i-1][j-1]. The insert option is bounded the same way. The diagonal option costs exactly dp[i-1][j-1], so no other move can beat the free match. The run checks the neighbour property on every cell of the 300 random tables.
3. Base cases. dp[i][0] = i (delete all i characters) and dp[0][j] = j (insert all j characters).
4. Fill order. Row by row, left to right, so the cell above, the cell to the left and the diagonal are already filled.
5. Where the answer is. dp[len(a)][len(b)], the bottom-right cell.

Brute force first

edit_brute is the recurrence written as recursion. On strings with no letter in common it makes three calls per cell until a prefix is empty, so the call count follows its own recurrence: C(i, j) = 1 + C(i-1, j) + C(i, j-1) + C(i-1, j-1), with 1 on the edges. The first lines of the output check it, root call included: 1 call at n = m = 0, 4 at n = m = 1, 19 at n = m = 2, and 398,593 at n = m = 8. For kitten to sitting the brute force makes 3,032 calls (matches shrink the tree, but not enough), while a dict cache (memoization: remember each result the first time it is computed) makes 98 calls, at most 1 + 3nm, and the table loops compute 42 cells (6 x 7; the printed table has 7 x 8 = 56 entries, the other 14 being the base row and column).

The code

import random
from functools import lru_cache

calls = 0


def edit_brute(a, b, i, j):
    """Edit distance of a[:i] and b[:j] by plain recursion."""
    global calls
    calls += 1
    if i == 0:
        return j                          # insert the j remaining characters
    if j == 0:
        return i                          # delete the i remaining characters
    if a[i - 1] == b[j - 1]:
        return edit_brute(a, b, i - 1, j - 1)
    return 1 + min(edit_brute(a, b, i - 1, j),        # delete a[i-1]
                   edit_brute(a, b, i, j - 1),        # insert b[j-1]
                   edit_brute(a, b, i - 1, j - 1))    # substitute


def edit_memo_calls(a, b):
    """Same recursion with a dict; returns (distance, number of calls)."""
    memo, count = {}, [0]

    def go(i, j):
        count[0] += 1
        if i == 0:
            return j
        if j == 0:
            return i
        if (i, j) not in memo:
            if a[i - 1] == b[j - 1]:
                memo[(i, j)] = go(i - 1, j - 1)
            else:
                memo[(i, j)] = 1 + min(go(i - 1, j), go(i, j - 1), go(i - 1, j - 1))
        return memo[(i, j)]

    return go(len(a), len(b)), count[0]


def edit_table(a, b):
    """dp[i][j] = fewest edits turning a[:i] into b[:j]."""
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        dp[i][0] = i
    for j in range(len(b) + 1):
        dp[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp


def edit_script(a, b, dp):
    """Walk back from the corner and list the edits, first to last."""
    i, j, ops = len(a), len(b), []
    while i > 0 or j > 0:
        if i > 0 and j > 0 and a[i - 1] == b[j - 1] and dp[i][j] == dp[i - 1][j - 1]:
            i, j = i - 1, j - 1
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            ops.append(("replace", i - 1, a[i - 1], b[j - 1]))
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(("delete", i - 1, a[i - 1], None))
            i -= 1
        else:
            ops.append(("insert", i, None, b[j - 1]))
            j -= 1
    return ops[::-1]


def apply_script(a, ops):
    """Apply edits right to left so earlier positions stay valid."""
    s = list(a)
    for kind, pos, _, new in reversed(ops):
        if kind == "replace":
            s[pos] = new
        elif kind == "delete":
            del s[pos]
        else:
            s.insert(pos, new)
    return "".join(s)


def edit_two_rows(a, b):
    """Keep one previous row. Rows have min(len(a), len(b)) + 1 entries."""
    if len(b) > len(a):
        a, b = b, a                       # edit distance is symmetric
    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]


def edit_one_row(a, b):
    """One row, with the diagonal value saved before it is overwritten."""
    if len(b) > len(a):
        a, b = b, a
    row = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        diag, row[0] = row[0], i          # diag = dp[i-1][0]
        for j in range(1, len(b) + 1):
            up = row[j]                   # dp[i-1][j]
            if a[i - 1] == b[j - 1]:
                row[j] = diag
            else:
                row[j] = 1 + min(up, row[j - 1], diag)
            diag = up
    return row[-1]


def wrong_ascending(a, b):
    row = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        row[0] = i
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                row[j] = row[j - 1]       # row[j-1] is already this row's value
            else:
                row[j] = 1 + min(row[j], row[j - 1], row[j - 1])  # diagonal read from overwritten cell
    return row[-1]


def wrong_descending(a, b):
    row = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        for j in range(len(b), 0, -1):
            if a[i - 1] == b[j - 1]:
                row[j] = row[j - 1]       # still last row's value: correct
            else:
                row[j] = 1 + min(row[j], row[j - 1], row[j - 1])  # left not computed yet
        row[0] = i
    return row[-1]


band_cells = 0


def edit_bounded(a, b, k):
    """Exact distance if it is at most k, else None. Only cells with |i-j| <= k."""
    global band_cells
    n, m = len(a), len(b)
    if abs(n - m) > k:
        return None
    if n == 0 or m == 0:
        return max(n, m)                  # only inserts or only deletes
    big = k + 1                           # any value above k means "too far"
    prev = [j if j <= k else big for j in range(m + 1)]
    for i in range(1, n + 1):
        cur = [big] * (m + 1)
        if i <= k:
            cur[0] = i
        lo, hi = max(1, i - k), min(m, i + k)
        for j in range(lo, hi + 1):
            band_cells += 1
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = min(big, 1 + min(prev[j], cur[j - 1], prev[j - 1]))
        if min(cur[lo:hi + 1]) > k:
            return None                   # every path already costs more than k
        prev = cur
    return prev[m] if prev[m] <= k else None


def edit_auto(a, b):
    """Try k = 1, 2, 4, ... until the bounded version succeeds."""
    k = 1
    while True:
        d = edit_bounded(a, b, k)
        if d is not None:
            return d, k
        k *= 2


def weighted(a, b, ins=1, dele=1, sub=1):
    """Same table with a separate price for each operation."""
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        dp[i][0] = i * dele
    for j in range(1, len(b) + 1):
        dp[0][j] = j * ins
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            swap = 0 if a[i - 1] == b[j - 1] else sub
            dp[i][j] = min(dp[i - 1][j] + dele, dp[i][j - 1] + ins, dp[i - 1][j - 1] + swap)
    return dp[-1][-1]


def lcs_len(a, b):
    """Longest common subsequence length, used only to check the sub=2 identity."""
    row = [0] * (len(b) + 1)
    for ch in a:
        diag = 0
        for j in range(1, len(b) + 1):
            up = row[j]
            row[j] = diag + 1 if ch == b[j - 1] else max(up, row[j - 1])
            diag = up
    return row[-1]


def with_swaps(a, b):
    """Adds 'swap two neighbours' as one edit (the restricted, or OSA, version).
    The swap option is part of the min inside the fill, so every later cell sees it."""
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        dp[i][0] = i
    for j in range(len(b) + 1):
        dp[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost)
            if i > 1 and j > 1 and a[i - 1] == b[j - 2] and a[i - 2] == b[j - 1]:
                dp[i][j] = min(dp[i][j], dp[i - 2][j - 2] + 1)
    return dp[-1][-1]


def swaps_memo(a, b):
    """Independent check: the same four-way recurrence written as a cached recursion."""
    @lru_cache(maxsize=None)
    def go(i, j):
        if i == 0 or j == 0:
            return i + j
        best = min(go(i - 1, j) + 1, go(i, j - 1) + 1, go(i - 1, j - 1) + (a[i - 1] != b[j - 1]))
        if i > 1 and j > 1 and a[i - 1] == b[j - 2] and a[i - 2] == b[j - 1]:
            best = min(best, go(i - 2, j - 2) + 1)
        return best
    return go(len(a), len(b))


# 1. Call counts for strings with no letter in common (the worst case).
def predicted(n, m):
    c = [[1] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            c[i][j] = 1 + c[i - 1][j] + c[i][j - 1] + c[i - 1][j - 1]
    return c[n][m]


print("n m  brute  predicted  memo  memo_bound")
for n, m in [(0, 0), (0, 3), (1, 1), (2, 2), (5, 5), (8, 8)]:
    calls = 0
    edit_brute("a" * n, "b" * m, n, m)
    _, memo_calls = edit_memo_calls("a" * n, "b" * m)
    assert calls == predicted(n, m) and memo_calls <= 1 + 3 * n * m
    print(f"{n:<2} {m:<2} {calls:<6} {predicted(n, m):<10} {memo_calls:<5} {1 + 3 * n * m}")
calls = 0
edit_brute("kitten", "sitting", 6, 7)
ks_table = edit_table("kitten", "sitting")
entries = len(ks_table) * len(ks_table[0])
computed = (len(ks_table) - 1) * (len(ks_table[0]) - 1)
print("kitten -> sitting brute calls:", calls,
      "| memo calls:", edit_memo_calls("kitten", "sitting")[1],
      f"| table entries: {entries}, computed by the loops: {computed} (the rest are the base row and column)")

# 2. The filled table and one optimal edit script.
a, b = "kitten", "sitting"
dp = edit_table(a, b)
print("\n       " + "  ".join(["-"] + list(b)))
for i, row in enumerate(dp):
    print(f"{'-' if i == 0 else a[i - 1]}    " + "  ".join(str(v) for v in row))
ops = edit_script(a, b, dp)
print("distance:", dp[-1][-1], "| edits:", ops)
print("apply edits:", apply_script(a, ops))

# 3. Every version agrees with the brute force on seeded random inputs.
rng = random.Random(3)
bad_asc = bad_desc = shown = none_seen = pairs_checked = too_far = 0
for _ in range(300):
    x = "".join(rng.choice("abc") for _ in range(rng.randint(0, 7)))
    y = "".join(rng.choice("abc") for _ in range(rng.randint(0, 7)))
    calls = 0
    want = edit_brute(x, y, len(x), len(y))
    table = edit_table(x, y)
    assert want == edit_memo_calls(x, y)[0] == table[-1][-1]
    assert want == edit_two_rows(x, y) == edit_one_row(x, y) == weighted(x, y)
    assert weighted(x, y, 1, 1, 2) == len(x) + len(y) - 2 * lcs_len(x, y)
    for i in range(len(table)):
        for j in range(len(table[0])):
            for di, dj in ((0, 1), (1, 0), (1, 1)):
                if i + di < len(table) and j + dj < len(table[0]):
                    too_far += abs(table[i + di][j + dj] - table[i][j]) > 1
                    pairs_checked += 1
    script = edit_script(x, y, table)
    assert len(script) == want and apply_script(x, script) == y
    for k in range(7):
        got = edit_bounded(x, y, k)
        assert got == (want if want <= k else None)
        none_seen += got is None
    assert edit_auto(x, y)[0] == want
    asc, desc = wrong_ascending(x, y), wrong_descending(x, y)
    bad_asc += asc != want
    bad_desc += desc != want
    if not shown and asc != want and desc != want:
        shown = 1
        print(f"\nExample {x!r} -> {y!r}: correct {want}, "
              f"ascending-wrong {asc}, descending-wrong {desc}")
print("300 random pairs: all versions match; "
      f"wrong ascending: {bad_asc}, wrong descending: {bad_desc}, "
      f"bounded runs that returned None: {none_seen}")

print("neighbouring cells (right, below, diagonal) checked:", pairs_checked, "| pairs differing by more than 1:", too_far)

# 4. Banded version on two length-2000 strings that differ by a few edits.
rng = random.Random(99)
s = [rng.choice("ACGT") for _ in range(2000)]
t = s[:]
for pos in sorted(rng.sample(range(2000), 7), reverse=True):
    kind = rng.choice(["sub", "ins", "del"])
    if kind == "sub":
        t[pos] = "T" if t[pos] != "T" else "A"
    elif kind == "ins":
        t.insert(pos, "G")
    else:
        del t[pos]
s, t = "".join(s), "".join(t)
exact = edit_one_row(s, t)
band_cells = 0
d, k = edit_auto(s, t)
print(f"\nlengths {len(s)} and {len(t)}: exact distance {exact}")
print(f"doubling search: distance {d} found with k = {k}, "
      f"cells evaluated {band_cells} versus {len(s) * len(t)} for the full table")
assert d == exact
try:
    edit_memo_calls("a" * 600, "b" * 600)
    print("memoized recursion on two strings of length 600: finished")
except RecursionError:
    print("memoized recursion on two strings of length 600: RecursionError (default limit 1000)")

# 5. Different prices and adjacent swaps.
print("\nsub cost 2 equals insert+delete only:", weighted("kitten", "sitting", 1, 1, 2),
      "| len(a)+len(b)-2*LCS =",
      len(a) + len(b) - 2 * lcs_len(a, b))
for p, q in (("ab", "ba"), ("abc", "bac")):
    print(f"{p!r} -> {q!r}: plain", edit_table(p, q)[-1][-1], "| with swap", with_swaps(p, q))
rng = random.Random(5)
helped = 0
for _ in range(300):
    x = "".join(rng.choice("abc") for _ in range(rng.randint(0, 7)))
    y = "".join(rng.choice("abc") for _ in range(rng.randint(0, 7)))
    assert with_swaps(x, y) == swaps_memo(x, y)
    helped += with_swaps(x, y) < edit_table(x, y)[-1][-1]
print("300 random pairs: with_swaps matches the cached recursion; pairs where a swap lowered the distance:", helped)

Output

n m  brute  predicted  memo  memo_bound
0  0  1      1          1     1
0  3  1      1          1     1
1  1  4      4          4     4
2  2  19     19         13    13
5  5  2524   2524       76    76
8  8  398593 398593     193   193
kitten -> sitting brute calls: 3032 | memo calls: 98 | table entries: 56, computed by the loops: 42 (the rest are the base row and column)

       -  s  i  t  t  i  n  g
-    0  1  2  3  4  5  6  7
k    1  1  2  3  4  5  6  7
i    2  2  1  2  3  4  5  6
t    3  3  2  1  2  3  4  5
t    4  4  3  2  1  2  3  4
e    5  5  4  3  2  2  3  4
n    6  6  5  4  3  3  2  3
distance: 3 | edits: [('replace', 0, 'k', 's'), ('replace', 4, 'e', 'i'), ('insert', 6, None, 'g')]
apply edits: sitting

Example 'cbcb' -> 'cbcbcc': correct 2, ascending-wrong 5, descending-wrong 3
300 random pairs: all versions match; wrong ascending: 227, wrong descending: 58, bounded runs that returned None: 1060
neighbouring cells (right, below, diagonal) checked: 13935 | pairs differing by more than 1: 0

lengths 2000 and 1999: exact distance 7
doubling search: distance 7 found with k = 8, cells evaluated 54673 versus 3998000 for the full table
memoized recursion on two strings of length 600: RecursionError (default limit 1000)

sub cost 2 equals insert+delete only: 5 | len(a)+len(b)-2*LCS = 5
'ab' -> 'ba': plain 2 | with swap 1
'abc' -> 'bac': plain 2 | with swap 1
300 random pairs: with_swaps matches the cached recursion; pairs where a swap lowered the distance: 6

Reading the table

In the kitten to sitting table the bottom-right cell is 3: replace k with s, replace e with i, insert g. The diagonal 1, 1, 1, 1 carries the first replacement across the free matches of i, t and t. edit_script recovers the edits by walking back from the corner, checking at each cell which neighbour could have produced its value (a match going diagonally for free, otherwise a replace, a delete or an insert). The printed edits, applied by apply_script, rebuild sitting from kitten. The walk back needs the whole table, so it is the part that conflicts with the space reduction below.

Reducing the space

Row i depends only on row i-1 and on cells already filled in row i. edit_two_rows keeps just those two rows and edit_one_row keeps one, saving the diagonal value in a variable before overwriting it. Rows are sized by the shorter string (edit distance is symmetric, so swapping is safe), giving O(min(n, m)) memory.

Direction matters, and the run shows it. wrong_ascending fills left to right with no saved diagonal, so the "diagonal" it reads is the left neighbour that has just been rewritten; on cbcb to cbcbcc it returns 5 where the answer is 2, and over 300 seeded random pairs it is wrong 227 times. wrong_descending fills right to left, which keeps the diagonal intact but reads a left neighbour that has not been computed yet; it returns 3 on the same pair and is wrong 58 times. The saved-diagonal one-row version and the two-row version match the brute force on all 300.

Complexity

• Time: (n+1)(m+1) states, each O(1) (three lookups and a comparison), so O(nm).
• Space: table O(nm); two rows or one row O(min(n, m)). The memoized version also holds O(nm) dict entries and recurses to depth n + m, which can exceed Python's default limit of 1000 frames once the two lengths add up to about 1000, so tabulate for large inputs; the run shows the memoized version raising RecursionError on two strings of length 600.
• Cost of the space saving: the length survives and the edit script does not. To keep both, run the same divide-and-conquer idea as Hirschberg's algorithm for LCS: split one string in half, compute the last row of the table for each half (one forward, one on the reversed halves), choose the split of the other string with the best total, and solve the two halves separately. That is still O(nm) time (roughly twice the table work) and linear extra space.

Bounded edit distance when only small distances matter

A typical interview asks for the table, the base cases, the complexity and the one- or two-row space reduction, and sometimes for the list of edits. The band, the doubling search, the different prices and the swap variant below are deeper material for follow-ups.

If the true distance d is small, an alignment can never stray far from the main diagonal: reaching cell (i, j) already costs at least |i - j| (the length gap has to be filled by inserts or deletes). So when you only care whether the distance is at most k, compute just the band of cells with |i - j| <= k and treat everything outside as "more than k". The strip of cells with |i - j| <= k is called the band, and restricting the table to it is the usual name for this idea (Ukkonen's band). edit_bounded does it: at most n * (2k + 1) cells, so O(kn) time, returns None when the distance exceeds k, and stops early if a whole row is above k. The check at 300 random pairs and k from 0 to 6 saw None 1,060 times and agreed with the full table every time.

When k is unknown, edit_auto tries k = 1, 2, 4, 8 and so on until one succeeds; the total work is a geometric series (each term is twice the one before, so the whole sum is less than twice the last term: the band widths 1, 2, 4, 8 add up to 15, under 2 x 8), still O(dn) where d is the true distance. On two strings of lengths 2000 and 1999 that differ by 7 edits it succeeded at k = 8 after evaluating 54,673 cells in all, against 3,998,000 for the full table. The rows in this code are still length m + 1, so memory stays O(m); a version that stores only the band would need O(k).

Other costs and transpositions

The same table handles unequal prices: replace the three + 1 terms with insert, delete and substitute costs (weighted). With a substitution cost of 2, a substitution is never better than a delete plus an insert, and the distance equals len(a) + len(b) - 2 * LCS (LCS is the longest common subsequence: the longest run of characters that appear in both strings in the same order, not necessarily next to each other), which the run checks (5 on kitten and sitting, and on every random pair). Counting an adjacent swap (ab to ba) as one edit adds one more transition, dp[i-2][j-2] + 1 when the last two characters of each string are swapped copies of each other. with_swaps does that inside the fill, so every later cell sees the cheaper value, and returns 1 for ab to ba and 1 for abc to bac, against 2 for plain edit distance in both cases. On 300 seeded random pairs it matches an independently written cached recursion of the same four-way rule (swaps_memo); a swap lowered the distance on 6 of those pairs. This version, the restricted (optimal string alignment) distance, does not allow editing a stretch of characters that has already been swapped. The full Damerau-Levenshtein distance does allow further edits between swapped characters, so the two can give different answers on some pairs.

Edge cases and common mistakes

• An empty string on either side: the base row or column gives the other string's length with no special code.
• Identical strings give 0; strings of different lengths give at least the length difference.
• Writing min(...) without the + 1 on the mismatch branch, or adding 1 on a match.
• Swapping which index belongs to which string (a[i-1] pairs with dp[i], b[j-1] with dp[.][j]).
• The algorithm does not depend on the language. In Java the rows would be int[] and the loops would be the same, so the Python above carries over line by line.

Running the code

Save the listing as edit_distance.py and run python edit_distance.py (Python 3.12, standard library only).

Product Quantization (PQ) is a vector compression and approximate nearest-neighbor (ANN) technique that generalizes scalar quantization to high-dimensional vectors by exploiting K‑Means in low-dimensional subspaces.

Definition & relation to K‑Means

• PQ splits a d‑dimensional vector x into m disjoint sub-vectors x = [x1, x2, …, xm], each of dimension d/m.
• For each subspace j, PQ trains a separate K‑Means model with K centroids (codebook Cj = {cj,1 … cj,K}). Training is simply running K‑Means independently on the set of sub-vectors for that subspace.
• Each sub-vector xi is encoded by the index of its nearest centroid: idxj = argmin_k ||xi − cj,k||. The full compressed representation is the concatenation of m centroid indices.

Why this helps

• Storage: instead of storing full float32 vectors, store m bytes (if K ≤ 256) per vector — huge compression (e.g., d=128, m=8 → 8 bytes vs 512 bytes).
• Search speed: use Asymmetric Distance Computation (ADC). Precompute a distance table between a query's sub-vectors and each subspace centroid (m × K distances). To compute distance between query q and an encoded database vector, sum the m lookups: dist(q, x) ≈ Σ_j dist(qj, Cj[idxj]). This replaces expensive dot products with m table lookups and additions, enabling very fast scan over millions of vectors.
• Accuracy vs. compression trade-off: larger K or more subspaces (smaller subspace dim) improves fidelity but increases memory/compute for tables and training cost.

Practical considerations

• Choice of m and K: commonly m divides d. Typical settings: d=128, m=8, K=256 (8 bytes per vector).
• Training: K‑Means per subspace is independent—parallelizable—but care with initialization and sufficient samples per subspace.
• Extensions: Optimized PQ (OPQ) applies a rotation to reduce quantization error before splitting; residual quantization stacks PQ stages for better accuracy.

In short, PQ leverages repeated K‑Means in partitioned subspaces to encode vectors as compact index sequences; ADC and small lookup tables enable very fast, memory-efficient approximate nearest-neighbor search with tunable accuracy/compression trade-offs.

Direct answer

A memoization decorator caches a function's return value keyed by its arguments, so a repeated call
with the SAME arguments returns the cached result instantly instead of recomputing; the key challenge
is building a hashable cache key from arbitrary positional and keyword arguments, and handling the
case where an argument itself isn't hashable (like a list).

Structured elaboration

Forming the key. The natural key is (args, sorted(kwargs.items())), args is already a tuple
(hashable if every element inside it is), and sorting kwargs by name before turning them into a tuple
ensures f(x=1, y=2) and f(y=2, x=1) produce the IDENTICAL cache key despite being written in a
different keyword order.

Handling unhashable arguments. If any argument is itself unhashable (a list, a dict), attempting
to hash the natural tuple key raises TypeError. Two common fixes: (1) convert to a canonical
hashable form first (e.g. a list becomes a tuple, a dict becomes a sorted tuple of items) if you can
guarantee the caller won't mutate it afterward, or (2) fall back to a string-based key built from
repr() of the arguments, slower to construct and technically riskier (two DIFFERENT objects could
share a repr in unusual cases) but robust to genuinely arbitrary, deeply-nested unhashable inputs
where building a fully canonical hashable form isn't practical.

Worked example

import functools

def memoize(func):
    cache = {}
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        try:
            key = (args, tuple(sorted(kwargs.items())))
            hash(key)
        except TypeError:
            key = (repr(args), repr(sorted(kwargs.items(), key=str)))
        if key not in cache:
            cache[key] = func(*args, **kwargs)
            wrapper.misses += 1
        else:
            wrapper.hits += 1
        return cache[key]
    wrapper.hits = 0
    wrapper.misses = 0
    return wrapper

calls = []

@memoize
def slow_square(x):
    calls.append(x)
    return x * x

@memoize
def slow_join(items):        # items will be an unhashable list -> falls back to the repr-key path
    calls.append(items)
    return "-".join(items)

print(slow_square(5), slow_square(5), slow_square(6))
print("calls actually executed:", calls)
print("hits:", slow_square.hits, "misses:", slow_square.misses)

print(slow_join(["a", "b"]), slow_join(["a", "b"]))
print("join calls executed:", len(calls) - 2)

Running this prints 25 25 36 (both calls to slow_square(5) return the same cached value, the
second one without recomputing), then calls actually executed: [5, 6] (proving the underlying
function body only actually RAN twice, once per distinct input, not three times), then hits: 1 misses: 2 (the counters agree exactly with that call pattern). The unhashable-argument case then
prints a-b a-b (correct result both times) and join calls executed: 1 (confirming the fallback
repr-based key path correctly recognized the second slow_join(["a","b"]) call as a cache hit
despite ["a","b"] itself being unhashable, rather than silently failing to cache it or raising).

Trade-offs and pitfalls

The repr-based fallback trades safety for generality: if two DIFFERENT unhashable objects happened to
produce an IDENTICAL repr string (rare, but not impossible for custom classes with a poorly-written
__repr__), they would incorrectly share a cache entry, a subtle correctness risk worth naming
explicitly rather than presenting the fallback as a strictly equivalent substitute for real hashing.
An unbounded cache is the other standing risk in any long-running process, this decorator has no
eviction policy at all, memory grows with the number of distinct argument combinations ever seen;
adding a capacity limit (an LRU-style, least-recently-used eviction bound) is the standard production fix.

Direct answer

Perplexity is a standard intrinsic measure of how well a language model predicts a sequence of text: it is the exponentiated average negative log-likelihood the model assigns to the correct tokens, so lower perplexity means the model was, on average, less "surprised" by the actual text. As an evaluation metric it has real limitations for open-ended generation, since a model can achieve low perplexity while still producing outputs that are repetitive, factually wrong, or simply not what a person actually wants.

Structured elaboration

The relationship to negative log-likelihood. For a sequence of $N$ tokens, the average negative log-likelihood (NLL) per token is $\text{NLL} = -\frac{1}{N}\sum_{i=1}^{N} \log P(x_i \mid x_{<i})$, the average of the log-probability the model assigned to each actual next token, negated so that a confidently correct prediction contributes a small (near-zero) value and a confidently wrong prediction contributes a large value. Perplexity is simply $\text{Perplexity} = e^{\text{NLL}}$ (exponentiating the average NLL), which converts the metric back onto a more intuitive scale: a perplexity of $k$ can be read as "the model was, on average, about as uncertain as if it were choosing uniformly among $k$ equally likely options at each step."

Limitations as an evaluation metric for open-ended generation. Perplexity only measures how well the model predicts a GIVEN reference text; it says nothing about the quality, correctness, or diversity of text the model would actually GENERATE on its own, since open-ended generation has no single correct continuation. A model can achieve excellent perplexity on held-out text while still being prone to hallucination, repetition, or dull generic phrasing at generation time, none of which perplexity directly penalizes. Perplexity is also sensitive to tokenization and vocabulary choices, so raw perplexity scores are not directly comparable across models that use different tokenizers.

Complementary metrics and human evaluation. Because perplexity says nothing about generation-time behavior, it is typically paired with task-specific automatic metrics (exact-match or F1 for question answering, BLEU or ROUGE for summarization or translation, which compare generated text against a reference) and, for genuinely open-ended tasks with no single correct answer, human evaluation is often essential, since no automatic metric fully captures qualities like helpfulness, coherence, or factual correctness that people actually care about.

Worked example

I verified the perplexity relationship in a sandbox with three constructed cases against known-expected outputs.

• A "perfect" model that puts overwhelming probability mass on the correct target token at every position of a 4-token sequence: the computed negative log-likelihood was 0 and perplexity was exactly 1.0, matching the definition, since a model that is always certain and always correct has, by construction, zero average surprise.
• A uniform model over a vocabulary of 8 tokens (softmax of all-zero logits, so every token is equally likely): perplexity of a uniform distribution over $V$ outcomes should analytically be exactly $V$. The computed perplexity was exactly 8.0 for both sequences in the batch, matching the analytical value exactly.
• A masking test: a padded position was deliberately given a badly WRONG prediction (a huge logit on the wrong token), but the position was excluded via the mask; the computed perplexity ignored it entirely and returned 1.0, matching only the two correctly-predicted, unmasked positions, while the SAME batch computed WITHOUT masking blew up to an enormous perplexity (roughly $9\times10^{28}$), confirming the masking logic is actually load-bearing and not a no-op.

import numpy as np

def sequence_perplexity(logits, target_ids, mask=None):
    B, T, V = logits.shape
    if mask is None:
        mask = np.ones((B, T), dtype=np.float64)
    mask = mask.astype(np.float64)
    shifted = logits - logits.max(axis=-1, keepdims=True)
    logsumexp = np.log(np.exp(shifted).sum(axis=-1, keepdims=True))
    logprobs = shifted - logsumexp
    b_idx = np.arange(B)[:, None]; t_idx = np.arange(T)[None, :]
    target_logprobs = logprobs[b_idx, t_idx, target_ids] * mask
    nll_per_seq = -target_logprobs.sum(axis=1)
    token_counts = np.maximum(mask.sum(axis=1), 1e-9)
    avg_nll = nll_per_seq / token_counts
    return nll_per_seq, np.exp(avg_nll)

Trade-offs & pitfalls

A common mistake is treating perplexity as a general-purpose quality score and using it to compare two models that use different tokenizers; because perplexity is computed per TOKEN, and different tokenizers segment the same text into different numbers of tokens, the same underlying text quality can produce different perplexity numbers purely due to tokenization differences, not genuine quality differences. Perplexity remains genuinely useful as a fast, cheap, reference-free signal during pre-training and for comparing checkpoints of the SAME model family with the SAME tokenizer over training, which is exactly what it was designed for, but it should not be the sole metric used to judge or compare generation quality across different model families or against human expectations.

What I'd build

A Pareto frontier: the set of tested configurations where you cannot improve one metric, like cost or latency, without making another, like accuracy, worse. Quantization (running the model with lower-precision numbers, which shrinks it and speeds it up at some accuracy cost) and pruning (removing less-important connections from the model) each trade accuracy for speed and cost differently, so plotting every tested combination on one chart, accuracy on one axis and cost or latency on the other, turns a pile of configuration results into a single decision surface.

Worked example (illustrative numbers)

Baseline model: 200 milliseconds p99 latency (the response time for the slowest 1% of requests) and 94.0% accuracy. Say three tested configurations show: quantization alone at 120ms and 93.7% accuracy; quantization plus moderate pruning at 90ms and 93.1%; quantization plus aggressive pruning at 60ms and 91.5%. All three clear a 150ms latency budget, so the budget alone does not pick a winner here, accuracy and margin against the budget do. Quantization alone gives up the least accuracy, a 0.3-point drop, but only clears the budget by 30ms. Moderate pruning gives up more, a 0.9-point drop, but clears the budget by 60ms, twice the margin. I'd recommend moderate pruning only if that extra headroom is worth the extra 0.6 points of accuracy, for example because traffic is growing or a slower network path could erode the margin later; if the workload is stable and 30ms of headroom is already comfortable, quantization alone is the better pick since it wins on accuracy while still meeting the budget. The aggressive-pruning option, though fastest, gives up more accuracy than either of the other two for speed the business does not need, so it is dominated once the budget is already satisfied.

How I'd present it to a non-technical stakeholder

Skip the technical parameter names and present plain outcomes: for the moderate-pruning option, "this option cuts response time by 55%, from 200 milliseconds to 90, for a 0.9 percentage point drop in accuracy, and still leaves twice the safety margin against our latency ceiling as the next-fastest option that also meets budget." I would draw the frontier as a simple chart, mark the current baseline, mark my recommendation, and add one sentence explaining why: everything on the line is a real, already-tested trade-off; anything below the line is strictly worse in both directions and not worth considering.

If they want a choice that violates my latency budget

I would not silently ship it. I would make the invisible cost visible in their terms: for example, "this option takes our response time from 200ms to 650ms, which is well past the point research shows users start to perceive a product as slow and abandon it." Then I would offer a path forward rather than a flat no, such as restricting that option to a use case that is not latency-sensitive, or asking for an explicit sign-off that accepts the named risk, since overriding an engineering guardrail should be a visible decision, not something the model quietly absorbs.

Direct answer: Selecting from a huge candidate pool under a compute budget is a staged-filtering problem, not a single-algorithm problem: cheap, fast filters eliminate the bulk of obviously-useless candidates first, and progressively more expensive methods are only applied to the much smaller survivor set, so you never pay wrapper-level cost on the full candidate pool.

Structured elaboration:
A practical staged pipeline:

1. Free/near-free filters first: drop near-zero-variance or quasi-constant columns (a column where one value dominates almost every row carries almost no signal), and drop anything failing a basic missingness or schema sanity check. This alone often eliminates a large fraction of a huge automatically-generated candidate pool at negligible cost.
2. Cheap univariate scoring (mutual information, correlation, a fast statistical test) on what remains, run in parallel/distributed since it's embarrassingly parallel per feature.
3. Redundancy removal: cluster features by pairwise correlation and keep one representative per cluster, since two near-duplicate features waste selection budget without adding signal.
4. Sampled or lightweight model-based importance on the reduced set (a fast model on a data sample, not the full expensive model on full data) to get a final ranked shortlist.
5. Only at this much-reduced scale would a genuinely expensive wrapper search (or the production model itself) be used to make the final cut.

Preserving interpretability and reproducibility means logging which stage eliminated each candidate and why, so the final set can be explained and the pipeline re-run deterministically, not just treated as a black box that spits out a list.

Worked example: Consider a specific cost-constrained variant of the same problem: a model already meets its accuracy SLA (service-level agreement) but feature computation is too expensive. The search here is inverted: instead of maximizing accuracy under a feature-count budget, you're minimizing feature-computation cost subject to NOT breaking the accuracy SLA, using greedy ablation (drop the least-important feature, retrain, check the SLA still holds, repeat) or importance-based pruning from the bottom up, with a held-out set to make sure you're not overfitting the pruning search itself to one data split.

Trade-offs and pitfalls: The variance-threshold-style fast filters have a real failure mode worth knowing: a rare-but-highly-predictive one-hot column (present in only 0.1% of rows but perfectly separating a rare, high-value class) looks like "near-zero variance" to a naive threshold and gets dropped, even though it may be the single most valuable feature in the set. A blind variance cutoff should always be checked against target-correlation, not applied in isolation.

Direct answer

I'll walk through a churn-reduction project: the business wanted to reduce voluntary cancellations, and the real work was in defining what "at risk of churning" meant operationally before any model got built.

Structured elaboration

• Problem statement. Product wanted to reduce monthly cancellations; the vague ask became a concrete target: predict which active subscribers were likely to cancel in the next 30 days, early enough that a retention offer could plausibly change their mind.
• Success criteria. Business-level: a measurable reduction in the cancellation rate for the targeted cohort versus a held-out control group, not just a good offline precision number. Model-level: a recall target on true cancellers high enough to make the retention campaign worth running, balanced against a precision floor so the campaign's cost (support and discount budget) stayed reasonable.
• Stakeholders and constraints. Marketing owned the retention offer and its budget; support had to be looped in since flagged users sometimes called in with questions; the constraint that mattered most was that any intervention had to run at least two weeks before the typical cancellation date to have a chance of working, which shaped the prediction window.
• What I'd do differently now. The first version defined "at risk" using account age and usage frequency alone; a stronger version, built after seeing early results, added a signal for recent support-ticket sentiment, which turned out to be one of the strongest predictors and wasn't in the original feature set.

Worked example

The eventual A/B test showed the targeted retention offer reduced churn in the treatment group by a measurable amount relative to the untreated control, validated over a full billing cycle rather than a proxy metric, which is what made the project's success criteria hold up under scrutiny from finance.

Trade-offs and pitfalls

The biggest lesson was that the model's offline metrics looked good weeks before the business impact was provable, and resisting the temptation to declare success on offline numbers alone (waiting for the actual A/B result) was what made the eventual claim credible to stakeholders.

Direct answer

Robust PyTorch checkpoint save/restore code needs to save model.state_dict(), optimizer.state_dict(), the scheduler's state if present, and enough training-position metadata (epoch, step, best validation score) to resume correctly, and needs to load defensively (checking for missing keys, device mismatches, and version compatibility) rather than assuming the checkpoint always matches the current model exactly.

Structured elaboration

• What to save: model and optimizer state dicts (both required for a true resume, not just model weights alone), scheduler state dict if a learning-rate schedule is in use, current epoch/step counters, and the best validation metric seen so far (useful for resuming early-stopping or best-checkpoint-retention logic correctly rather than restarting the "best so far" tracking from scratch).
• Save atomically: write to a temporary file and rename (an atomic filesystem operation on most systems) rather than writing directly to the final checkpoint path, so a crash mid-write never leaves a corrupted, partially-written checkpoint at the path a resume would try to load.
• Device-agnostic loading: load with map_location set appropriately (e.g. to CPU first, then move to the target device) so a checkpoint saved on a GPU-equipped machine can still be loaded correctly on a machine with a different GPU configuration or even no GPU (for inspection/debugging).
• Defensive restore: check that the loaded state dict's keys match the current model's expected keys before assuming success (using strict=False deliberately and inspecting missing_keys/unexpected_keys when doing a partial load, e.g. fine-tuning from a checkpoint that lacks a newly-added layer's parameters entirely), rather than letting a silent key mismatch produce an incorrectly-initialized model. strict=False only suppresses the error for keys that are genuinely absent on one side; a key present in BOTH the checkpoint and the model but with a different tensor SHAPE (e.g. a resized final layer) still raises RuntimeError regardless of strict, confirmed by direct execution, so a changed-layer-size scenario needs the mismatched parameter's key explicitly excluded from the state dict before loading, not just strict=False.

Worked example

import torch, os, tempfile

def save_checkpoint(model, optimizer, scheduler, epoch, step, best_metric, path):
    state = {
        "model_state_dict": model.state_dict(),
        "optimizer_state_dict": optimizer.state_dict(),
        "scheduler_state_dict": scheduler.state_dict() if scheduler is not None else None,
        "epoch": epoch,
        "step": step,
        "best_metric": best_metric,
    }
    dir_name = os.path.dirname(path) or "."
    with tempfile.NamedTemporaryFile(dir=dir_name, delete=False) as tmp:
        torch.save(state, tmp.name)
        tmp_path = tmp.name
    os.replace(tmp_path, path)  # atomic on POSIX filesystems

def load_checkpoint(model, optimizer, scheduler, path, map_location="cpu"):
    ckpt = torch.load(path, map_location=map_location)
    missing, unexpected = model.load_state_dict(ckpt["model_state_dict"], strict=False)
    if missing or unexpected:
        print(f"WARNING: missing={missing}, unexpected={unexpected}")
    optimizer.load_state_dict(ckpt["optimizer_state_dict"])
    if scheduler is not None and ckpt.get("scheduler_state_dict") is not None:
        scheduler.load_state_dict(ckpt["scheduler_state_dict"])
    return ckpt["epoch"], ckpt["step"], ckpt["best_metric"]

Tested two distinct scenarios directly: (1) a model with a genuinely NEW layer absent from the checkpoint: load_state_dict(..., strict=False) correctly reports it in missing_keys without raising, confirming the warning path fires as intended; (2) a model whose final layer has a DIFFERENT output size than the checkpoint's (same key name, different shape): this raises RuntimeError even with strict=False, contradicting an earlier draft of this answer that assumed strict=False would gracefully handle a resized layer the same way it handles a missing one. The fix for scenario (2) is to filter the mismatched key out of the loaded state dict before calling load_state_dict, not to rely on strict=False alone.

Trade-offs & pitfalls

Using strict=True (the default) is safer for exact-resume scenarios (where any mismatch is genuinely an error you want to know about immediately) but breaks intentional partial loads (e.g. fine-tuning with a new head); choosing strict=False everywhere by default risks silently ignoring a real mismatch that should have failed loudly, so the right default depends on whether the checkpoint is expected to match the current model exactly or not. Either way, strict=False is not a universal escape hatch: it resolves missing/unexpected KEYS, not SHAPE mismatches on a shared key, which is a distinction worth stating explicitly to anyone relying on it for a resized-layer fine-tune.