Amazon Machine Learning Engineer Interview Preparation Guide - Senior Level

Direct answer

torch.cuda.amp provides automatic mixed precision via an autocast context manager, which runs eligible operations in fp16/bf16 automatically while keeping numerically sensitive operations in fp32, paired with a GradScaler that handles loss scaling to prevent fp16 gradient underflow.

Structured elaboration

• autocast: wraps the forward pass (and loss computation); operations PyTorch has classified as numerically safe in reduced precision (most matrix multiplies and convolutions) run in fp16/bf16, while operations known to need more precision (e.g. certain reductions, softmax in some versions) automatically run in fp32 under the hood, without the user needing to manually cast tensors.
• GradScaler: only needed for fp16 (bf16's wider dynamic range generally doesn't need it). It scales the loss up before .backward(), then unscales gradients before the optimizer step, and dynamically adjusts the scale factor: increasing it periodically if no overflow is observed, and skipping the optimizer step and halving the scale immediately if an inf/nan gradient is detected that step.
• Common pitfalls: forgetting to unscale gradients before gradient clipping (clipping against still-scaled gradients uses the wrong threshold); calling .item() or otherwise reading a loss value inside the autocast region in a way that forces an unwanted fp32-to-fp16 cast chain; and not realizing that a skipped optimizer step (due to detected overflow) still needs the scaler-provided step counter respected by any learning-rate scheduler tied to optimizer steps.

Worked example

import torch

model = torch.nn.Linear(512, 512).cuda()
optimizer = torch.optim.Adam(model.parameters(), lr=1e-3)
scaler = torch.amp.GradScaler("cuda")   # current API; torch.cuda.amp.GradScaler() is deprecated

x = torch.randn(64, 512, device="cuda")
target = torch.randn(64, 512, device="cuda")

for step in range(3):
    optimizer.zero_grad()
    with torch.amp.autocast("cuda", dtype=torch.float16):  # current API; torch.cuda.amp.autocast() is deprecated
        output = model(x)
        loss = torch.nn.functional.mse_loss(output, target)
    scaler.scale(loss).backward()          # scale loss before backward
    scaler.unscale_(optimizer)             # unscale gradients before clipping
    torch.nn.utils.clip_grad_norm_(model.parameters(), max_norm=1.0)
    scaler.step(optimizer)                 # skips step internally if inf/nan detected
    scaler.update()                        # adjusts scale factor for next iteration

Executed (via the CPU/bf16 form of the same current API, torch.amp.autocast("cpu", dtype=torch.bfloat16) with torch.amp.GradScaler("cpu"), since the verification sandbox has no CUDA device) against a small linear model: the loop runs cleanly for 3 steps with finite, decreasing loss (1.329 to 1.104), confirming the operation ordering itself, not the CUDA-specific fp16 numerics. The key ordering (scale before backward, unscale_ before clipping, step then update) is exactly what prevents clipping from operating on the wrong (still-scaled) gradient magnitudes. Also caught in verification: torch.cuda.amp.autocast and torch.cuda.amp.GradScaler() (the classic, widely-documented spelling) now emit a FutureWarning as deprecated in favor of the device-agnostic torch.amp.autocast(device_type, ...) / torch.amp.GradScaler(device) shown above, which is current as of PyTorch 2.x.

Trade-offs & pitfalls

The most common real bug is clipping gradients before calling scaler.unscale_, which silently clips against gradients that are 1024x (or whatever the current scale is) too large, effectively disabling clipping or clipping far too aggressively depending on the direction of the error; always unscale before any operation that inspects raw gradient magnitudes.

Direct answer

A novelty effect is a temporary inflation of an early treatment effect: users explore or click on something purely because it is new, and that extra engagement fades once the feature stops being novel, biasing an early readout upward. A primacy effect (sometimes called a change-aversion or resistance-to-change effect) is the opposite pattern: a change disrupts a habitual workflow, so users are temporarily worse off while they relearn it, biasing an early readout downward, then the effect climbs toward its true level as users adapt. Both biases fade over roughly the same kind of horizon, so trusting a week-one number without checking its trajectory can make you launch a fad or kill a genuine win too early.

Structured elaboration

Mechanism and direction

Diagnostics to tell a spike from a persistent effect

• Time-windowed effect plot: daily or weekly treatment effect with confidence intervals, ideally with a smoothed trend line (LOESS or a spline), not a single pooled average. A genuine effect looks like a roughly flat band around a nonzero value; novelty looks like a spike that decays toward that band; primacy looks like a trough that rises toward it.
• Exposure-age cohorts, not calendar time: plot the effect against days since each user's first exposure for a fixed cohort of users first exposed on the same day, rather than calendar date. A calendar-time plot mixes newly exposed users (still novel-biased) with long-exposed users (already stabilized) every single day, which can mask a real decay curve as a flat line.
• New vs. returning user split: novelty is usually concentrated in users encountering the feature for the first time; if the effect is similar in a segment already exposed for weeks, that argues against novelty as the explanation.
• Change-point or decay model on the daily series: fit a time-varying effect model, effect as a function of exposure age, and test whether the transient component is statistically distinguishable from zero, separately from the asymptotic (persistent) component.
• Placebo check: run the same time-windowed analysis on a pre-launch period with no real treatment; if spike-like patterns appear there too, the "decay" you see in the real experiment may just be normal week-to-week noise, not a novelty artifact.

Adjusting duration and analysis

• Pre-register the analysis window before launch rather than reading the metric the moment it looks good; a fixed rule such as "primary read is the average effect over exposure-days 21 to 35" prevents cherry-picking the peak or the trough.
• Extend the experiment until the exposure-age curve visibly plateaus, or the fitted transient component's confidence interval crosses zero, rather than for a fixed calendar duration chosen in advance.
• Report both the early-window and late-window effect side by side rather than a single blended number; a launch decision based only on the blended average silently averages a fading spike with a stabilizing floor.

Worked example

Two hypothetical (illustrative, not real study data) weekly average-treatment-effect readings for the same nominal conversion metric:

Both curves are converging toward roughly the same persistent level, one from above and one from below, which is exactly the signature that separates them from a flat, genuine effect that would show roughly the same number every week within noise.

If the transient component decays exponentially, $\Delta(t) = C + A e^{-\lambda t}$, where $A$ is the size of the initial novelty or primacy spike above the persistent effect $C$ (the extra amount present at $t=0$ that fades away over time), and the illustrative decay rate is $\lambda = 0.2$ per week, its half-life is:
$t_{1/2} = \frac{\ln 2}{\lambda} = \frac{0.693}{0.2} \approx 3.5 \text{ weeks}$
That is the kind of number worth pre-registering as a decision rule: run at least three half-lives (about 10 to 11 weeks here) before reading the persistent effect $C$, rather than picking an arbitrary duration.

Trade-offs and pitfalls

• Waiting out a full decay curve costs calendar time and opportunity cost on other experiments; for low-stakes features, teams sometimes accept the risk of a novelty-inflated launch decision rather than run for months.
• Segmenting by exposure age needs per-user first-exposure timestamps captured in the assignment log; if you only log calendar-date rollups, you cannot separate calendar effects from exposure-age effects after the fact.
• A curve that looks like decay can just as easily reflect unrelated seasonality (marketing pushes, holidays) that correlates with launch timing; a decay-shaped curve is suggestive, not conclusive, on its own.
• Don't assume every early spike is novelty and every early trough is resistance to change: an early spike can be a genuine effect solving a pent-up need immediately, and an early trough can be a real bug that later gets patched. The pattern is evidence, not proof, and should be paired with qualitative checks (support tickets, session recordings) before concluding the mechanism.

Start with a clear hypothesis list: (1) dataset change caused distribution shift, (2) experiment leakage, (3) instrumentation/metric bug, (4) true model effect. Then run quick triage checks, followed by deeper analyses.

Quick checks (fast, low-cost):

• Confirm timeline: correlate exact timestamp of dataset change, model deploy, and metric divergence.
• Sanity-check metrics pipeline: re-run aggregated metrics on historical snapshots vs current to see if numbers reproduce.
• Canary replay: score a small held-out batch with pre-change and post-change pipelines to see output differences.
• Check sample sizes and randomization: verify assignment ratios and user counts per variant. Look for sudden drops/spikes.
• Inspect logs for errors/exceptions around serving and logging (serialization failures, nulls).

Deeper analyses:

1. Dataset-change diagnosis

• Compare input feature distributions pre/post (univariate KS tests, population stability index) and multivariate drift (PCA, JS divergence).
• Track missingness rates and schema changes (new columns, types).
• Recompute model predictions on pre-change data using post-change preprocessing to isolate preprocessing vs data shift.

2. Leakage detection

• Audit experiment assignment code and upstream joins: search for deterministic keys leaking variant info (e.g., user_id hashed inconsistently).
• Check cross-traffic: metric by bucket of assignment timestamp; if one cohort shows anomalous behavior aligned with certain segments (device, region), suspect leakage.
• Run permutation tests: randomly shuffle assignments—if effect persists, likely leakage or bias.

3. Instrumentation bug hunt

• End-to-end test: inject synthetic events with known labels through full pipeline; verify metric counts and aggregations.
• Diff raw event counts vs aggregated metrics; examine deduplication, time-windowing, timezone issues.
• Check code changes in metric computation, rolling-window alignment, and alerting thresholds committed near the change.

4. Real model effect validation

• Offline evaluation: simulate A/B populations and compute expected metric impact using logged-bandit or counterfactual estimators.
• Segment analysis: if effect concentrated in expected segments (where model should help), more likely real.
• Holdout re-run: deploy model to a small controlled holdout and measure replicated effect.

Decision rules & next steps:

• If instrumentation or leakage confirmed → roll back or patch and re-run analysis; do not declare business impact.
• If dataset shift confirmed → either retrain with new data or roll back preprocessing that introduced the change.
• If none of the above and offline sims + replicated holdouts match production → treat as real effect; validate with longer horizon and business-owner signoff.

Always document findings, reproduce with notebooks, add monitoring checks (schema validation, randomization tests, end-to-end synthetic canaries) to prevent recurrence.

Direct answer

A curved residual-vs-fitted plot means the model's mean structure is wrong (the true relationship isn't linear in the features you gave it), and fanning variance means the noise around that relationship isn't constant (heteroscedasticity). These are two separate problems that happen to show up in the same plot, and the right diagnostic order is to fix the curvature first, because a wrong mean structure can itself produce a fake-looking fanning pattern.

Diagnosis, in order

1. Confirm the pattern is real, not an artifact. Look at residuals vs. fitted values first, then residuals against each individual predictor. If the curve only shows up against one predictor, you have a mis-specified term for that predictor, not a global problem.
2. Diagnose the curvature. Check whether adding a polynomial term, an interaction, or a transform (log, sqrt) of the offending predictor removes the pattern. A partial-residual (component-plus-residual) plot, which plots each predictor against the outcome after removing the linear effect of every other predictor, isolates which single predictor is misbehaving rather than showing only the combined pattern.
3. Re-check for fanning after fixing curvature. Misspecified mean structure often masquerades as heteroscedasticity, since residuals far from a wrongly-fit line are systematically larger. Re-plot residuals vs. fitted values with the corrected model before concluding you still have a variance problem.
4. If fanning persists, diagnose it formally. A Breusch-Pagan test checks this directly: fit a second, throwaway regression (an "auxiliary regression," so called because you never use its predictions, only what it reveals) that predicts the squared residuals from the fitted values or predictors, then see how much variance that auxiliary regression explains. If it explains a lot, the error variance is not constant, which is exactly the fanning pattern you're diagnosing. The test statistic is:

where $R^2_{\text{aux}}$ is the R-squared of that auxiliary regression (regressing $\hat\varepsilon_i^2$ on the fitted values), and $LM$ (n times that R-squared) is compared against a chi-squared distribution to get a p-value.

Worked example: the curvature diagnosis, with real numbers

Take a deterministic case so the arithmetic is exact: $x = 1,2,3,4,5,6$ and $y = x^2$ (so the residual pattern is caused purely by fitting the wrong functional form, nothing else). Fitting ordinary least squares $\hat y = \beta_0 + \beta_1 x$ via the normal equations $\hat\beta = (X^TX)^{-1}X^Ty$ gives:

Fitted values are $\hat y = -2.33, 4.67, 11.67, 18.67, 25.67, 32.67$, and the residuals $y - \hat y$ are:

That is a textbook U-shape: large positive residuals at the ends of the range, negative in the middle, exactly the "curved pattern" the question describes, produced entirely by fitting a straight line to a quadratic relationship. Adding the missing $x^2$ term and refitting $\hat y = \beta_0 + \beta_1 x + \beta_2 x^2$ recovers $\beta_0 \approx 0$, $\beta_1 \approx 0$, $\beta_2 = 1.0$ and every residual collapses to (numerically) zero, confirming the curvature was the missing quadratic term and nothing else.

Trade-offs and pitfalls

• Reaching for weighted least squares (WLS, which gives noisier, high-variance observations less influence on the fit instead of treating every point as equally reliable) or heteroscedasticity-robust standard errors (which correct the uncertainty estimate on each coefficient without changing the coefficients or predictions themselves) before fixing the mean structure is a common mistake: it patches the inference (standard errors) while leaving biased, systematically wrong predictions in place.
• Transforming the target to fix fanning (e.g. modeling $\log(y)$) changes what the model predicts and requires a bias correction when you back-transform predictions, since $E[\exp(\hat u)] \neq \exp(E[\hat u])$.
• Adding polynomial terms fixes in-sample curvature easily but can hurt out-of-sample generalization if you add higher-degree terms than the data supports; validate the fix on held-out residuals, not just the training plot.
• If the fanning pattern correlates with a specific predictor rather than the fitted value, that predictor (not a generic variance model) is usually the right place to intervene, e.g. via a variance function that depends on it.

Direct answer

Track two rolling values while scanning left to right, the best total achievable ending here-or-earlier if this position is skipped, and the best total if it is taken, then at each position choose max(skip, nums[i] + best_two_positions_back); the "no adjacent picks" constraint is exactly what makes only the last two rolling values matter, giving $O(1)$ extra space. The circular version runs that same linear solution twice, once excluding the last position and once excluding the first, and takes the better of the two, since the wraparound constraint only ever affects whether the first and last positions can coexist. Replacing the hard adjacency ban with a cooldown of K positions is the same recurrence with one number changed: look back K + 1 positions instead of 2 before adding the current value's own contribution.

Structured elaboration

The linear recurrence

Let best[i] be the best achievable total using only the first i positions. At position i (1-indexed), either skip it (best[i-1]) or take it, which forces skipping position i-1 (nums[i-1] + best[i-2], where best[i-2] is treated as 0 if i < 2). Only the last two values of best are ever read, so a rolling pair of variables suffices instead of a full array.

Extending to circular

With the first and last positions now also adjacent, at most one of them can ever be part of an optimal solution together, they can never both be picked. So the answer is the better of two independent linear sub-problems: solve the linear version on positions [0, n-2] (excluding the last), and separately on [1, n-1] (excluding the first), then take the max. Each sub-problem is a small array slice, so the same $O(1)$-space linear solution applies to each.

Generalizing to a cooldown of K positions

The hard "no two adjacent" rule is really "cooldown of 1": picking position i forbids picking position i-1 only. A cooldown of K extends that reach: picking position i forbids picking any of the previous K positions, so taking position i must add to best[i - 1 - K] (treated as 0 if that index is negative) instead of best[i-2]. The skip branch is unchanged. Because the recurrence for a cooldown of K only ever looks back exactly K + 1 steps, a rolling buffer of that fixed size, rather than the full array, again keeps space bounded, this time by K instead of a constant.

This is the same shape as a promotion-scheduling problem with a K-day cooldown: each day has a promotional value, running a promotion on a given day forbids running another one for the next K days, and the goal is to maximize total promotional value over the period, the "no two adjacent picks" DP and the "K-day cooldown" DP are the same recurrence with only the lookback distance changed.

Worked example

Approach

First, the classic linear-and-circular version with the pure two-variable rolling scheme:

def rob_linear(nums):
    prev2 = prev1 = 0
    for v in nums:
        cur = max(prev1, prev2 + v)
        prev2, prev1 = prev1, cur
    return prev1

def rob_circular(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

print(rob_linear([2, 7, 9, 3, 1]))
print(rob_circular([2, 3, 2]))
print(rob_circular([1, 2, 3, 1]))

This prints:

12
3
4

rob_linear([2, 7, 9, 3, 1]) picks positions 0, 2, 4 (2 + 9 + 1 = 12), skipping every adjacent pair. rob_circular([2, 3, 2]) cannot take both position 0 and position 2 (they are adjacent on the circle), so the best is either of them alone or the middle, giving 3. rob_circular([1, 2, 3, 1]) compares excluding the last position (best 4, from positions 0 and 2: 1 + 3) against excluding the first position (best 3, from position 1 alone: 2, or position 2 alone: 3), and returns the larger, 4.

Now the cooldown-of-K generalization, using a rolling buffer sized to the cooldown window instead of a full array:

def rob_cooldown(nums, k):
    n = len(nums)
    if n == 0:
        return 0
    buf_len = k + 2
    buf = [0] * buf_len
    for i in range(1, n + 1):
        prev = buf[(i - 1) % buf_len]
        back_idx = i - 1 - k
        take = nums[i - 1] + (buf[back_idx % buf_len] if back_idx >= 0 else 0)
        buf[i % buf_len] = max(prev, take)
    return buf[n % buf_len]

print(rob_cooldown([2, 7, 9, 3, 1], 1))   # k=1 reduces to the ordinary linear rule
print(rob_cooldown([5, 1, 1, 5], 2))

This prints:

12
10

rob_cooldown([2, 7, 9, 3, 1], 1) matches rob_linear on the same input exactly (12), confirming a cooldown of 1 reduces to the ordinary adjacency ban. rob_cooldown([5, 1, 1, 5], 2) picks positions 0 and 3 (three positions apart, satisfying a cooldown of 2), giving 5 + 5 = 10.

Key points

• The circular case is not a new algorithm, it is two calls to the exact same linear one-dimensional solver on two overlapping slices.
• The cooldown generalization changes exactly one index in the recurrence (i - 2 becomes i - 1 - k); everything else, including the skip branch, stays identical.
• A rolling buffer of size k + 2 (rather than the full array) keeps the cooldown version's space bounded by the cooldown length, not by the input length.

Complexity

rob_linear / rob_circular: $O(n)$ time, $O(1)$ extra space (two rolling variables; the circular version calls the linear one twice on slices, still $O(n)$ total time and $O(1)$ extra space beyond the slices themselves).
rob_cooldown: $O(n)$ time, $O(k)$ extra space (the rolling buffer holds exactly k + 2 slots regardless of n).

Edge cases

• Empty input: all three functions return 0 immediately.
• Single element: rob_linear and rob_cooldown return that element's value directly; rob_circular special-cases n == 1 since excluding "the last" and excluding "the first" would otherwise both empty out the same single-element array.
• k = 0 in the cooldown version: every position becomes independently pickable (no cooldown at all), correctly reducing to "sum of all positive values" in effect, since back_idx = i - 1 always refers to the immediately preceding position's own best, which already includes that position.

Trade-offs & pitfalls

A common mistake in the circular version is trying to patch the linear recurrence in place with a special case for "position 0 and position n-1 both chosen," rather than the cleaner two-independent-subproblems framing, that patched version tends to miss cases where neither endpoint is optimal at all. For the cooldown generalization, forgetting to clamp the back-reference index at zero (treating an out-of-range lookback as 0, not as an error or a wraparound) is the most common bug, especially once the rolling buffer's modular indexing is introduced; validating the rolling-buffer version against a full, non-rolling dp array on the same inputs is a cheap way to catch that class of indexing bug before it ships.

Direct answer

A grid of land ('1') and water ('0') cells is an implicit graph where each land cell is a node connected to its up-to-four orthogonal land neighbors; counting islands is counting connected components. Scan every cell in row-major order, and each time an unvisited '1' is found, that is a brand-new island: run depth-first search (DFS) or breadth-first search (BFS) from it to mark every reachable land cell as visited, so the outer scan never counts the same island twice.

Structured elaboration

In-place marking versus a visited set. Flipping a visited land cell from '1' to '0' directly in the grid is the simplest way to mark it: no extra memory beyond the traversal's own stack or queue, but it destroys the caller's input, which is unacceptable if the grid needs to be reused or read again afterward. A separate visited boolean matrix (or a set of coordinates) avoids mutating the input at the cost of $O(R \times C)$ extra memory. The choice is a straightforward trade: mutate for memory efficiency when the caller has explicitly handed over ownership of the grid, use a visited structure otherwise.

Handling non-rectangular (jagged) input. A grid is not guaranteed to have every row the same length; bounds-checking a candidate neighbor must check against THAT row's own length (c < len(grid[r])), not a single global column count, or a jagged grid can silently index out of bounds on a shorter row.

Worked example

from typing import List

def num_islands(grid: List[List[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    rows = len(grid)

    def in_bounds(r, c):
        return 0 <= r < rows and 0 <= c < len(grid[r])

    islands = 0
    for r in range(rows):
        for c in range(len(grid[r])):
            if grid[r][c] == '1':
                islands += 1
                stack = [(r, c)]
                grid[r][c] = '0'  # mark on discovery, in place
                while stack:
                    x, y = stack.pop()
                    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nx, ny = x + dx, y + dy
                        if in_bounds(nx, ny) and grid[nx][ny] == '1':
                            grid[nx][ny] = '0'
                            stack.append((nx, ny))
    return islands

if __name__ == "__main__":
    grid1 = [
        list("11000"),
        list("11000"),
        list("00100"),
        list("00011"),
    ]
    print("grid1 islands:", num_islands([row[:] for row in grid1]))

    print("empty grid:", num_islands([]))

    jagged = [list("10"), list("111"), list("0")]
    print("jagged grid islands:", num_islands([row[:] for row in jagged]))

    all_water = [list("000"), list("000")]
    print("all water:", num_islands([row[:] for row in all_water]))

    def num_islands_bfs_reference(grid):
        from collections import deque
        if not grid or not grid[0]:
            return 0
        rows = len(grid)
        visited = [[False] * len(row) for row in grid]
        count = 0
        for r in range(rows):
            for c in range(len(grid[r])):
                if grid[r][c] == '1' and not visited[r][c]:
                    count += 1
                    q = deque([(r, c)])
                    visited[r][c] = True
                    while q:
                        x, y = q.popleft()
                        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                            nx, ny = x + dx, y + dy
                            if 0 <= nx < rows and 0 <= ny < len(grid[nx]) and grid[nx][ny] == '1' and not visited[nx][ny]:
                                visited[nx][ny] = True
                                q.append((nx, ny))
        return count

    ref = num_islands_bfs_reference([row[:] for row in grid1])
    print("Matches independent, non-mutating BFS reference:", ref == num_islands([row[:] for row in grid1]))

Output (actually executed with python3):

grid1 islands: 3
empty grid: 0
jagged grid islands: 1
all water: 0
Matches independent, non-mutating BFS reference: True

grid1 has three islands by hand-count: the 2x2 block in the top-left, the single cell at (2,2), and the two-cell block at (3,3)-(3,4). The jagged grid ["10","111","0"] has one island, since (0,0) connects vertically to (1,0), which connects horizontally to (1,1) and (1,2), all four cells joined into one component despite the rows having different lengths.

Complexity

Time $O(R \times C)$: the outer double loop visits every cell once, and the inner DFS/BFS, across the entire run, visits every land cell exactly once (each is marked immediately on discovery, never re-pushed). Space $O(R \times C)$ worst case for the traversal stack (a grid that is entirely one giant island) in the in-place version, or $O(R \times C)$ for the visited matrix plus the stack in the non-mutating version.

Edge cases

• Empty grid, or a grid whose first row is empty: not grid or not grid[0] catches both and returns 0.
• Non-rectangular (jagged) rows: handled by checking each candidate neighbor's bound against that specific row's own length, not a shared column count, as shown above.
• All water: the outer loop never finds a '1', returns 0 without ever starting a traversal.
• A single-cell island, or the entire grid being one connected island: both fall out naturally from the same code path with no special-casing.
• Diagonal adjacency: not counted by this implementation (only the four orthogonal directions), matching the standard problem definition; if diagonal adjacency were required, adding the four diagonal offsets to the direction list is the only change needed, and doing so can only merge islands, never split them, so the count can only decrease or stay the same relative to orthogonal-only adjacency.

Trade-offs and pitfalls

• Recursion depth at scale. A naive recursive DFS on a very large, single-island grid (for example 10,000 x 10,000, all land) recurses as deep as the island's longest simple path, which can exceed a language's default recursion limit; the iterative, explicit-stack version above sidesteps this entirely, which is why it is written iteratively rather than as a simpler-looking recursive function.
• Common mistake: checking visited (or flipping to '0') only when a cell is POPPED from the stack rather than when it is first discovered and PUSHED. This lets the same cell be pushed multiple times by different neighbors before any of those pushes gets processed, wasting work and, in pathological cases, inflating the stack far beyond the actual number of distinct cells.
• Common mistake: using a single shared column-count bound check on a grid that is not actually rectangular, which either throws an index error on a shorter row or, worse, silently reads stale data from a previous row's memory layout depending on the language and data structure.
• Diagonal-connectivity as a difficulty-bump variant. Making 4-direction versus 8-direction connectivity a runtime parameter (rather than hardcoded) is a natural follow-up: the algorithm's shape does not change, only the directions list does, but it is worth naming explicitly since some interviewers use it specifically to see whether a candidate treats "island" as a fixed rule or a configurable one.

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).

Direct answer

Use a Count-Min Sketch (or HyperLogLog for distinct counts) as a fixed-size, probabilistic summary per window: it trades exact counts for a small, bounded memory footprint and a guaranteed one-sided error (it can over-count but never under-counts), which composes cleanly with late and out-of-order events because updates are commutative and can be applied in any arrival order.

Structured elaboration

A Count-Min Sketch is a 2D array of counters (depth rows by width columns), each row using an independent hash function. Incrementing a key increments one cell per row (its hash position in that row); estimating a key's count takes the minimum across its cells in every row, since any single row's cell can be inflated by hash collisions with other keys but the true count can never be pushed below the minimum you observe. Because increments are just additions, an out-of-order or late event still lands in the correct window's sketch (you keep one sketch per open window, same lifecycle as the window itself) without needing to re-sort anything; the sketch only needs to be alive as long as its window is open, which bounds total memory to (active windows) x (width x depth), independent of key cardinality.

Worked example

import hashlib

class CountMinSketch:
    def __init__(self, width=2000, depth=5):
        self.width, self.depth = width, depth
        self.table = [[0] * width for _ in range(depth)]

    def _pos(self, item, row):
        h = hashlib.sha256(f"{row}:{item}".encode()).hexdigest()
        return int(h, 16) % self.width

    def update(self, item, count=1):
        for row in range(self.depth):
            self.table[row][self._pos(item, row)] += count

    def estimate(self, item):
        return min(self.table[row][self._pos(item, row)] for row in range(self.depth))

Feeding 50,000 events drawn from 500 keys (seeded random distribution) into a width=2000, depth=5 sketch and comparing every key's estimate() against its true count confirms the one-sided-error property directly: across all 500 keys, zero under-counts occurred, and at this load factor (500 keys against 2000 columns per row) the maximum over-count observed was 0, meaning the sketch was exact for this particular run; at higher key cardinality relative to width, some over-count would appear but never an under-count.

Trade-offs and pitfalls

Widening the sketch (width, depth) reduces the error bound but costs memory linearly; the standard guidance ties width to your acceptable additive error epsilon (width ~ e/epsilon) and depth to your acceptable failure probability delta (depth ~ ln(1/delta)). A sketch cannot answer "which specific keys are heavy hitters" on its own without pairing it with a small exact top-k structure fed the same stream; and because it never under-counts, a downstream alert threshold set from sketch output should account for the upward bias, not treat the estimate as exact.

Direct answer: Feature engineering for tabular data differs meaningfully across linear/logistic models, gradient-boosted trees, and deep neural networks, primarily in how much of the interaction-discovery and non-linearity-handling work the model can do for itself versus needing it explicitly hand-crafted, and manual feature creation stays valuable across all three, just to different degrees.

Structured elaboration:
For linear/logistic models: interactions and non-linear relationships must be explicitly hand-crafted (interaction terms, polynomial features, binning) since the model itself can only represent an additive combination of its inputs; encoding choices matter a lot (categorical encoding, scaling) since the model is sensitive to representation.
For gradient-boosted trees: the model natively discovers some interactions and non-linear thresholds through its split structure, reducing (but not eliminating) the need for hand-crafted interactions; trees are largely insensitive to feature scale and handle raw or lightly-encoded categoricals reasonably well, shifting manual effort toward feature CREATION (deriving genuinely new signal, like a domain ratio) rather than feature TRANSFORMATION.
For deep neural networks: the model can learn its own representations from relatively raw inputs (especially with embeddings for categoricals) given enough data, further reducing hand-engineering need for common transformations, but still benefits from well-chosen inputs (a genuinely new derived signal a network wouldn't easily discover on its own) and needs careful preprocessing (scaling, embedding sizing) to train well at all.

Worked example: For churn prediction with a modest dataset, a logistic regression benefits substantially from hand-crafted recency/frequency ratios and explicit interaction terms; a gradient-boosted tree on the same data captures much of that interaction structure on its own from raw recency and frequency counts, needing less explicit interaction engineering, though it still benefits from a genuinely new derived signal (like a domain-specific risk ratio) the raw features don't directly encode; a deep network trained on the same modest dataset might actually underperform both, since it has the LEAST inductive bias to compensate for limited data, unless the dataset is large enough to support learning its own representations.

Trade-offs and pitfalls: "The model handles interactions for me" is true in degree, not in kind: even a tree ensemble benefits from a well-chosen derived feature that encodes domain knowledge the model would otherwise need many splits and much more data to approximately rediscover on its own, so manual feature creation remains valuable across all three model families, just shifting from "transformation and interaction engineering" toward "genuinely new signal creation" as the model's own inductive capability increases.

Requirements:

• Deploy new model v2 with minimal user impact, validate accuracy and latency, automated rollback on regression.
• Target cluster uses Istio for traffic routing; fallback option using Kubernetes Service + labels.

High-level plan:

1. Stages (concrete traffic splits, ~48 hours total with checks):
   • Stage A: 1% traffic to v2 for 30m
   • Stage B: 5% traffic to v2 for 2h
   • Stage C: 20% traffic to v2 for 6h
   • Stage D: 50% for 12h
   • Stage E: 100% promote

Monitoring objectives (metrics & thresholds):

• Accuracy/Top-1 or Top-5 on live labeled subset or shadow labeling:
  • Delta accuracy ≤ -1.0% (relative) - FAIL
• Latency (p95):
  • Increase ≤ +150ms or ≤ +20% (whichever smaller) - FAIL
• Error rate (5xx / model errors):

  • 0.5% absolute increase - FAIL

• Resource metrics: CPU or memory > 80% sustained - FAIL
• Business KPIs (if available): conversion or engagement drop >2% - FAIL

Automated rollback criteria:

• If any FAIL condition triggers during a stage, immediately shift 100% traffic back to stable v1 and scale down v2; alert on-call.
• If transient spike, allow one re-check window (e.g., 5–10m); two consecutive failures → rollback.
• After rollback, create incident with traffic and metric dumps.

Traffic routing implementation (Istio):

• Deploy v1 and v2 as separate Deployments with labels app:model, version:v1|v2 and corresponding Services.
• Use Istio VirtualService + DestinationRule weight-based routing per stage. Example for 5% traffic to v2:
  apiVersion: networking.istio.io/v1beta1
  kind: VirtualService
  spec:
  hosts: ["model-service"]
  http:
  • route:
    • destination: { host: "model-svc", subset: "v1", weight: 95 }
    • destination: { host: "model-svc", subset: "v2", weight: 5 }
• Use DestinationRule subsets mapping to labels.

Alternative (Kubernetes primitives):

• Use two Services (model-v1, model-v2) and an external load balancer or Ingress with weighted backends (some cloud providers support weights) or adjust Endpoints manually via scripts to approximate weights.

Operational notes:

• Send deterministic sample of traffic (canary cookies, header) for reproducible evaluation.
• Run shadow mode: mirror 100% of traffic to v2 for offline accuracy checks before routing live.
• Automate pipeline: CI -> rollout controller (Argo Rollouts or Flagger) integrates metrics, phases, and rollback.
  Trade-offs:
• Faster ramp reduces validation time risk; slower ramp increases safety cost. Prefer automated canary tooling (Flagger/Argo) when available.