FAANG-Standard Interview Preparation Guide: Mid-Level AI Engineer

Direct answer
Give the listener a short roadmap up front (what you're about to walk through and in how many steps), narrate one idea at a time in order, and periodically restate where you are relative to that roadmap, rather than free-associating through your thought process.

Structured elaboration

1. State the roadmap before diving in: "There are two things going on here: first the root cause, then the fix I'd propose. Let me start with the root cause." This gives the listener a mental container to place what follows.
2. Narrate conclusions and reasons, not raw stream-of-consciousness. Say what you're checking and why, not just what you're doing: "I'm checking the logs because I suspect this is a timeout, not a crash," rather than silently scrolling and occasionally muttering.
3. Signal transitions explicitly: "okay, that rules out X, so now let's look at Y," so the listener can track your position in the reasoning instead of having to reconstruct it after the fact.
4. Pause at natural checkpoints to check the listener is still following, especially before switching to a new sub-problem, rather than only checking in at the very end.
5. Name your assumptions out loud as you make them, since an unstated assumption is invisible to the listener and, if wrong, can make the rest of your reasoning look wrong for a reason they can't see.

Worked example
Unstructured: "Okay so let me look at this... hmm... yeah so there's this function... wait, let me check something else... okay so actually I think the issue might be... let's see... yeah I think it's the caching."

Structured: "I'm going to check three possible causes in order of likelihood: caching, a race condition, or a bad config value. Starting with caching, since it's the most common cause of this symptom... [checks] ...that rules out caching, the values are fresh. Moving to the race condition..."

The second version gives the listener the plan up front, tells them which hypothesis is being tested and why, and explicitly states when a hypothesis is ruled out, so they can follow the reasoning instead of just watching an unexplained sequence of actions.

Trade-offs and pitfalls

• Over-narrating every micro-step can slow you down and annoy a listener who just wants the conclusion; calibrate the level of narration to whether the audience needs to follow the reasoning (an interview, a mentoring session) or just wants the answer (a peer who trusts you and is short on time).
• It's easy to silently switch approaches mid-thought without saying so; if you change direction, say so explicitly ("actually, let me back up") rather than leaving the listener to notice on their own.
• This is a skill that degrades under real pressure or unfamiliar problems; it's worth practicing the "state the roadmap first" habit specifically, since it's the cheapest part to do consistently even when the rest of your thinking is genuinely uncertain.

Direct answer. Ranking candidate upstream root causes from a dependency graph and a set of observed failures means combining three kinds of evidence into one score per candidate: how many of the observed failures a candidate could structurally explain via the dependency graph, how recently that candidate started relative to the failure window, and that candidate's own historical failure rate, since any one signal alone can point at the wrong node.

Structured elaboration. Dependency impact: for each candidate (non-failed) node, compute which failed nodes are reachable from it via the dependency graph (a breadth-first traversal), and use the fraction of total observed failures it could explain as one input to the score; a node reachable to more of the observed failures is a stronger candidate, all else equal. Temporal proximity: weight candidates that started closer in time to the observed failure window more heavily than ones that started long before, since a cause is more likely to be something that changed recently relative to when problems appeared. Historical failure rate: a node with a track record of frequently causing issues is a more probable culprit than an equally-plausible-looking node with a clean history, all else equal. Combine these into a single weighted score (the specific weights are a judgment call reflecting how much each organization trusts each signal) and approximate for a large graph by capping the reachability search depth or sampling candidate subgraphs rather than exhaustively traversing an enormous dependency graph for every candidate.

Worked example (executed in Python). A small DAG: A feeds into both B and C, and both B and C feed into D; separately, E feeds into F. Failures are observed at D and F. Running the ranking algorithm (weights: 40% dependency impact, 40% recency, 20% historical rate): C and B both rank above A, despite A being the common ancestor of both paths to D, because A started earliest of the three (lowest recency score) while B and C started closer to the failure window; E ranks below B and C despite explaining a real failure (F) because of its lower combined score, illustrating that the algorithm's recency weighting is doing real, visible work, not just reachability. This is a legitimate design choice worth being explicit about: a pure reachability-only ranking would have put A on top as the single common ancestor of the most failures, while this temporally-aware version prefers more recently-changed, more specific culprits, which better matches how root causes usually actually work (the ancestor that's ALWAYS been there is less suspicious than the specific service that changed right before things broke).

Trade-offs and pitfalls. The weighting scheme materially changes the ranking, as the worked example shows, so the weights should be treated as a tunable, disclosed design choice, not a hidden implementation detail; a team using this tool should know whether it's biased toward temporally-recent culprits or toward structurally-central ones, since that bias shapes which real incidents it will and won't surface well. For a genuinely large dependency graph, exact reachability computation for every candidate becomes expensive; capping traversal depth or focusing the search on nodes within a bounded time window of the failures first is a practical approximation that trades some completeness for tractable runtime.

Direct answer

Before the call, do the homework a genuinely curious, well-prepared candidate would do: read what the team has published publicly, read what others have said about working there, and bring specific, current signals to the conversation instead of questions you could have answered yourself with 30 minutes of research.

Public sources to consult

The company's engineering blog, since its topics and frequency reveal what the team is proud of or currently building; public repositories if any exist, for commit cadence and recent activity; the job posting itself, read closely for named tools and responsibilities rather than just the title; review sites like Glassdoor or Blind for team-specific commentary, treated as directional hypotheses rather than fact; and the product itself, used firsthand for rough edges or recent changes.

Harder-to-reach sources

LinkedIn profiles of current team members, where tenure patterns (a burst of very recent joiners, or a lot of very long tenure) both tell you something different; any mutual connections who might give an informal read; and the interviewer's own public talks or writing, if they have any.

Signals to look for

Commit cadence and recency on public repositories, to judge whether something is actively maintained or legacy; recurring themes in open issues, which hint at known pain points; incident history if publicly documented, like a status page's past record; product metrics you can observe externally, like app store ratings and review themes; the pattern of recent job postings, since a burst of hiring for one specialty suggests a recent gap or new initiative; and engineering blog posts, since a post about a migration tells you exactly what's currently being rebuilt.

How to prioritize what to bring up

Favor things that are recent (shows fresh research, not a five-year-old post), specific to this team rather than generic to the company, and genuinely uncertain to you. Save your best, most specific question for something public information alone couldn't resolve, that's what the live conversation is actually for, rather than asking something the job posting already answered.

Worked example

If the engineering blog has a post from two months ago about migrating to a new queueing system, and the job posting separately mentions "own reliability of the payments pipeline," I'd connect the two and ask something like "how has the queueing migration affected the reliability work this role owns, is that mostly finished or still in progress." That shows I read both artifacts and connected them, rather than asking a generic "what's a typical day like" question.

Trade-offs and pitfalls

Over-researching to the point of asking overly narrow or gotcha-sounding questions can come across as trying to catch the team out rather than being genuinely curious. The other pitfall is treating review-site commentary as fully reliable, it's useful for hypotheses to verify live, not conclusions to state as fact in the interview.

Direct answer
For model selection and tuning, you compare the MEAN cross-validated score across candidate configurations (or candidate models), not any single fold's score; this differs from a single held-out validation set mainly in how much you trust small differences between close candidates, k-fold gives you multiple independent estimates to average and to gauge fold-to-fold spread from.

Structured elaboration
The procedure: for each candidate hyperparameter setting (or model family), run k-fold CV and compute the mean score across the k folds; compare those means across candidates and pick the best. Using k-fold this way, rather than a single validation set, matters most when candidates are close: a single split can favor one configuration purely by chance of which rows landed in that particular validation fold, while averaging over k folds smooths out that luck and gives you a sense (via the fold-to-fold standard deviation) of whether an observed difference between two candidates' mean scores is larger than the natural noise between folds.
The final chosen configuration is then typically refit on the FULL training data (all folds combined) rather than kept as an ensemble of k fold-specific models, since the CV process was only ever meant to help you SELECT a configuration, not to be the production model itself.

Worked example
Comparing two candidate regularization strengths via 5-fold CV: config A averages 0.842 accuracy (fold scores 0.83, 0.85, 0.84, 0.86, 0.83, std 0.012) and config B averages 0.845 (fold scores 0.80, 0.87, 0.84, 0.88, 0.83, std 0.030). A single validation split might have shown B ahead by more just by chance of which fold got picked; looking at the full spread, B's higher variance across folds should make you less confident that its slightly higher mean reflects a real, reproducible advantage over A.

Trade-offs & pitfalls
k-fold CV for tuning is still just an ESTIMATE of generalization, if the same k-fold CV score that selected the winning configuration is also the number you report as your final generalization estimate, you're back to the nested-CV problem: the selection process has looked at that number, so it's mildly optimistic as a stand-alone report.

Direct answer

Keep a min-heap (a priority queue: a tree-shaped structure that keeps the smallest element accessible at the root in logarithmic time) holding one candidate element from each of the k sources, tagged with which source it came from. Repeatedly pop the smallest, emit it, then pull the next element from that same source and push it back in. This touches every element exactly once and never holds more than k elements in the heap at a time, unlike scanning all k sources for the minimum on every step, which redoes that comparison work from scratch each time.

Structured elaboration

Maintain, per source, an iterator (or a buffered read-ahead block if the source is a file or network stream) rather than loading the whole source into memory. The heap holds at most one (value, source_id) pair per still-active source:

1. Prime the heap: pull the first element from each source and push all k pairs in.
2. Loop while the heap is non-empty: pop the smallest pair, emit its value, then pull the next element from that same source; if one exists, push it back onto the heap.
3. Stop when the heap empties, meaning every source is exhausted.

Why the heap beats scanning all k sources for the minimum: a linear scan over k sources costs $O(k)$ per output element, for $O(N \cdot k)$ total across $N$ elements. The heap instead pays $O(\log k)$ per push and pop, for $O(N \log k)$ total. Once k grows past a small constant (which it does for genuinely large fan-in, like merging thousands of shards), $\log k$ is dramatically cheaper than $k$, and the heap only ever holds k items regardless of how large each individual source is, which is what makes this work under a fixed memory budget.

Worked example

import heapq
from typing import Iterable, Iterator


def k_way_merge(sources: list[Iterable[int]]) -> Iterator[int]:
    heap: list[tuple[int, int, Iterator[int]]] = []
    for i, source in enumerate(sources):
        it = iter(source)
        first = next(it, None)
        if first is not None:
            heap.append((first, i, it))
    heapq.heapify(heap)

    while heap:
        value, i, it = heapq.heappop(heap)
        yield value
        nxt = next(it, None)
        if nxt is not None:
            heapq.heappush(heap, (nxt, i, it))


stream_a = [1, 4, 9, 15]
stream_b = [2, 3, 8]
stream_c = [0, 5, 6, 7, 20]

merged = list(k_way_merge([stream_a, stream_b, stream_c]))
print(merged)
print(merged == sorted(stream_a + stream_b + stream_c))

Running this prints:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 15, 20]
True

Key points

• The heap never grows past k elements no matter how large each source is, which is exactly what makes this work when sources are too large to fit in memory together.
• Each source only needs to expose "give me the current head" and "advance to the next element," which is why the same code works whether a source is a Python list, a sorted linked list, or a buffered file reader.

Complexity

where $N$ is the total number of elements across all sources. If sources are read from disk in blocks rather than streamed one element at a time, add $O(k \cdot \text{block\_size})$ for the read-ahead buffers.

Edge cases

• An empty source: simply contributes nothing to the initial heap priming, handled by the if first is not None guard.
• Duplicate values across sources: the heap comparison ties are broken by insertion order in this implementation (via the source index in the tuple), so output remains stable and well-defined.
• All sources exhausted simultaneously: the loop ends naturally when the heap empties.

Trade-offs & pitfalls

For disk-resident or over-the-network sources, reading one element at a time is usually the wrong granularity: buffering a block per source amortizes I/O overhead, at the cost of O(k * block_size) memory instead of O(k). This is the same "k-way-merge" primitive whether the k inputs are k sorted arrays, k sorted linked lists (pop the head node instead of an array iterator), or k disk-resident sorted files too large to hold together, and it generalizes further to an external top-K query across those files by simply stopping the loop after K pops instead of draining the heap. A common mistake is reaching for a full sort of the concatenated data instead of a merge: since each source is already sorted, a merge is $O(N \log k)$ while re-sorting everything from scratch is $O(N \log N)$, strictly worse whenever $k \ll N$, which is the normal case.

Direct answer

Track a small mix of signals across a few categories: ownership and scope, what decisions and outcomes you're trusted with now versus a few months ago, skill evidence, things you can now do that you couldn't before, and external signal, feedback you actively solicit rather than wait for, reviewed on a set cadence so busyness doesn't get mistaken for progress.

Structured elaboration

Ownership and scope signal. Periodically write down, in a sentence or two, what you're currently trusted to decide or own without checking in first, and compare it to the same note from a few months earlier. If it reads the same, that's useful information regardless of how busy you've been.

Skill evidence signal. Keep a short, honest log of specific instances where you did something you genuinely couldn't have done a few months prior, a list of capability demonstrated, not a list of tasks completed.

External signal, actively solicited. The input side of tracking is asking for feedback on a regular cadence rather than waiting for a formal review to surface it. Pick one or two people whose judgment you trust, a manager, a peer, a cross-functional partner, ask a specific rather than generic question, do it on a set interval so the answers accumulate into a trend, and use that same conversation to show your manager concrete evidence of the movement you've tracked, not just to ask how you're doing.

Keep yourself honest. At each check, ask whether the evidence you've gathered would convince someone who doesn't already like you, not just whether you feel you've been busy. Busyness isn't itself a metric, the ownership, skill, and feedback signals above are proxies for actual movement.

Worked example

"Every few months I set aside a short amount of time to update three things: a one-line note on what I currently own without checking in, a short log entry on anything I did recently that I genuinely couldn't have done before, and a specific question I asked one trusted colleague or my manager about what was still holding me back. One quarter my log of things I did looked long and I felt productive, but my ownership note hadn't changed at all from the previous check, and when I asked my manager the specific question, the answer named a gap I hadn't noticed because I'd been focused on volume rather than scope. That mismatch, feeling busy while the ownership and feedback signals were flat, was the useful signal, and it redirected my effort the following quarter toward the specific gap rather than more of the same work."

Trade-offs & pitfalls

• Treating task completion as the metric rewards busyness and tells you nothing about whether your scope or trust is actually growing.
• Waiting for a formal review cycle to get feedback means the signal arrives too infrequently and too late to redirect effort.
• Asking for feedback with a generic question, how am I doing, tends to produce generic, unhelpful answers. A specific question produces something you can act on.
• Tracking too many metrics becomes its own busywork. A small, consistent set reviewed honestly beats an elaborate dashboard reviewed rarely.

Requirements:

• Process sensitive frames locally (no cloud leave), upload only non-sensitive for higher-accuracy inference.
• Low latency for on-device actions; eventual consistency for cloud-enhanced labels.
• Strong privacy, consent, and auditability; robust offline fallback.

High-level architecture:
Edge device (camera + NPU + secure enclave) → Sensitivity classifier → Router:

• Sensitive frames → local inference store (encrypted) + local models
• Non-sensitive frames → encrypted queue → cloud inference + model retraining

Sensitivity classification:

• Lightweight on-device classifier (binary sensitive/non-sensitive) trained on curated labeled data; calibrated to favor recall for sensitive class (i.e., minimize false negatives). Use ensemble of visual cues: faces, ID/text detection (OCR), motion/scene context, and confidence thresholding. Periodically update thresholds via federated analytics (no raw sensitive frames leave device).

Encryption & key management:

• In-transit: TLS 1.3 with mutual auth.
• At-rest: AES-256 in secure enclave/TPM. Keys stored per-device; rotate via PKI. Uploads signed to ensure provenance.
• Cloud access uses least-privilege IAM and customer-controlled keys (KMS/HSM).

Buffer / sync strategies:

• On-device FIFO encrypted buffer with configurable quota and eviction policy (drop oldest non-sensitive when full). Backoff and exponential retry for uploads; prioritize metadata-only first (lower bandwidth): anonymized features or embeddings with differential privacy noise before full-frame upload if bandwidth constrained.
• Sync acknowledges with versioning; cloud returns enhanced labels and model deltas for edge personalization.

Privacy / consent handling:

• Explicit opt-in UI; per-use granular controls (categories allowed/disallowed). Local audit log of frames processed and uploads; option to delete raw cloud data. Use differential privacy for analytics; store consent tokens and enforce policy checks before any upload.

Network considerations:

• Adaptive upload based on bandwidth, latency, cost: batch during Wi‑Fi, send smaller anonymized payloads on cellular, use QoS tagging. Monitor link health and telemetry to switch modes.

Fallback when cloud unreachable:

• Degraded local model (small, optimized) for core tasks; operate in conservative mode where sensitivity classifier errs on side of sensitive (avoid uploads). Queue non-sensitive frames for later sync. Signal feature-limited mode to user/owners.

Operational notes:

• Continuous evaluation: monitor false-negative sensitive leaks via synthetic tests; use federated learning to improve on-device classifiers without sharing raw sensitive frames.
• Threat model: assume compromised network; minimize attack surface via enclave, signed uploads, and strict retention policies.

Direct answer: A multi-tenant feature platform for hundreds of teams needs tenant isolation so one team cannot starve or corrupt another's workload, resource quotas and cost attribution so usage maps back to accountability, a shared but namespaced catalog so features are discoverable without colliding, a low-friction onboarding path, and access control with audit logging baked in from the start rather than bolted on later.

Structured elaboration:

• Tenant isolation. Logical isolation (shared infrastructure, separate namespaces, quota-enforced) is cheaper to operate and scales to hundreds of teams more easily than physical isolation (dedicated clusters per tenant), but it requires strong quota enforcement so a noisy tenant cannot degrade others; physical isolation is reserved for tenants with hard compliance or extreme-scale requirements that justify the operational cost.
• Resource quotas. Per-tenant limits on storage, compute (materialization job concurrency), and read/write throughput against the online store, enforced at the platform layer (not just monitored after the fact), with headroom for legitimate bursts via a request-based override process.
• Cost attribution and chargeback. Tag every resource (storage bytes, compute-seconds, online-store operations) with a tenant ID at creation time, and aggregate into a per-team cost report; this is what makes quotas defensible and gives teams an incentive to clean up unused features.
• Feature namespace and discovery. A shared catalog with tenant-scoped namespaces (so team_a.feature_x and team_b.feature_x do not collide) plus cross-tenant search and reuse, since a major value of a shared platform is avoiding duplicate feature engineering across teams.
• Onboarding. Self-service registration with sane defaults (starter quotas, template pipelines) so a new team can start producing features within hours, not weeks of platform-team involvement, gated by automated checks (schema validation, basic hygiene) rather than manual review for every request.
• Security. Role-based access control scoped per namespace, with audit logging of who read, wrote, or materialized what, satisfying both internal governance and external compliance needs.

Worked example: With hundreds of teams and thousands of feature definitions, a realistic starting quota might be: 500GB offline storage, 10,000 online-store operations/sec, and 4 concurrent materialization job slots per team by default, with an escalation path (a lightweight request reviewed against actual usage data) for teams that outgrow the default; cost attribution then shows, for example, that 10% of teams consume 60% of platform resources, which becomes the input to a capacity-planning and chargeback conversation rather than an ad-hoc "why is the bill so high" investigation.

Trade-offs & pitfalls: Logical isolation's biggest failure mode is quota enforcement that is advisory rather than actually enforced at the resource layer (a team's job silently exceeds its quota and degrades others before anyone notices); the fix is hard limits with clear, fast-failing errors rather than soft alerts a team can ignore. Namespacing solves the naming-collision problem but does not by itself solve feature duplication (two teams independently building near-identical features under different names); that requires an active discovery and deduplication process on top of the namespace, not just the namespace itself. Over-indexing on self-service onboarding without automated hygiene checks (schema validation, basic testing) trades short-term onboarding speed for long-term platform-quality debt, since a platform with hundreds of self-onboarded teams and no guardrails accumulates low-quality, undocumented features quickly.

Direct answer

I noticed a recurring, tedious task nobody had gotten around to fixing, built the smallest tool that solved it rather than the most impressive one I could imagine, and ran it alongside the manual process for a while before trusting it fully. Nobody asked me to do this. I picked it because it was a real, recurring cost, not because it was the biggest problem on the team.

Structured elaboration

Identifying the pain point. I look for tasks that are manual, repeated on a predictable cadence, and error-prone specifically because a human is doing them by hand, not because the underlying logic is hard. It doesn't need to be the team's biggest problem, just a genuine recurring cost that everyone had quietly accepted as normal.

Tools and approach. I reach for the smallest tool that actually solves the problem, usually a script using libraries already in use on the team, rather than standing up new infrastructure to justify the effort. The goal is removing the manual step, not building something impressive.

Validating it. I run the automation in parallel with the existing manual process for a defined period before fully trusting it, comparing outputs so any discrepancy surfaces while a human is still double-checking, not after the manual process has already been retired.

Rolling it out. I use it myself first, then share it with teammates doing the same manual task, with just enough documentation that someone else can run it without needing me in the room.

Measuring impact. I look at three things: time saved on the recurring task, errors caught that the manual process had been missing, and incidents avoided because a mistake never got the chance to reach anyone downstream.

Worked example

A weekly reconciliation between two data sources took about three hours every Monday and had a history of small mismatches slipping through unnoticed. Nobody had assigned fixing this to anyone, it was just accepted as the cost of Monday mornings.

I identified the pain point by noticing how much of that three hours was pure manual comparison rather than actual judgment calls. I wrote a script that pulled both sources and automatically flagged any mismatch above a small threshold, using tools the team already had access to rather than introducing anything new. To validate it, I ran the script alongside the manual process for three weeks, comparing its output against what the manual review caught each week. During that period, it caught every discrepancy the manual process had also caught, plus one that the manual process had missed entirely that week. I rolled it out by using it myself first, then sharing it with the two teammates who did the same reconciliation on other teams, along with a short readme covering how to run it and what the flag threshold meant.

Measurable impact: the task went from about three hours to roughly fifteen minutes of review, a time reduction of about 92% (165 divided by 180 minutes). Over the following quarter, the script caught four discrepancies that would previously have gone unnoticed until a downstream report was already built on the wrong numbers.

Trade-offs and pitfalls

Building something clever enough that only I understand or can maintain it creates a single point of failure, so I kept the logic simple enough for a teammate to read and adjust without me. Skipping validation because the automation "obviously" works is a common shortcut, and it's exactly how a subtle bug in the automation itself slips past unnoticed. It's also worth asking whether the manual process should even exist in its current form before automating it exactly as-is, rather than automating a bad process faster. And a real risk worth watching for: an automation's output can differ subtly in format from what the manual process produced, and if something downstream was quietly parsing the old manual report's exact shape, that consumer can break the moment the automation changes it, even though the automation's own logic is completely correct. Checking who else consumes the output, not just verifying your own correctness, is what catches that before it ships.

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