Shelf · DSA Patterns · Chapter 7

Chapter 7: Dynamic programming

Dynamic programming is one habit repeated six ways. Define the state, write the transition, fix the base case, pick an order, then compress space. This chapter drills each step with generic templates so you can rebuild any variant aloud instead of recalling a memorised table.

Difficulty
Priority
dsa-07-01Card 1 of 6

Define a sufficient DP state

HardP3 · Role-dependentKnow cold8 min
dpstatememo-keyoptimal-substructure

Why you care

Most wrong DP answers are decided before any recurrence exists: the state is missing a variable, so two situations share one cache entry. On the job that is the planner right on a small fixture and wrong at production size, with no error. Interviewers open with "what does your function return, and for which arguments?" because naming a state separates understanding from pattern-matching.

Explain like I'm 5

Halfway through a train journey, a friend asks what the rest will cost. You do not recite every station so far. You say where you are and whether the next ticket has a restriction based on the last. Those two facts are the state. The full diary is history; use it as your notebook key and you never recognise a situation you have already seen.

Core concept

A state is the smallest set of facts that, with the remaining input, fully determines the future. Write it as a sentence: "f(i, last) = ways to fill slots i.. given the previous kind last".

  • Overlapping subproblems: different paths reach the same state. If none do, memoisation buys nothing.
  • Optimal substructure: the future ignores how you arrived.
  • Name the question: feasibility (or), counting (+) or optimization (min/max); only the combine changes. Say where the answer lives, e.g. f(0, None).
  • Key every variable a future rule reads, and nothing else.

Use DP when the same sub-situation recurs and a small summary captures the past. Do not use it when a greedy choice is provably safe or the only valid summary is the whole history.

Under the hood

functools.cache and lru_cache store results in a dict keyed by the arguments, so they must be hashable: a list raises TypeError. The docs add that f(a=1, b=2) and f(b=2, a=1) may be separate entries, so pass state positionally.

Minimal example A memo key that forgets one dependency

PythonKey by n alone versus (n, last)runs
def brute(n, last=None):
    if n == 0: return 1
    return sum(brute(n - 1, s) for s in "ABC" if (last, s) != ("A", "C"))

def count(n, last, memo, key):
    k = key(n, last)
    if k not in memo:
        memo[k] = 1 if n == 0 else sum(
            count(n - 1, s, memo, key) for s in "ABC" if (last, s) != ("A", "C"))
    return memo[k]

print(brute(10))
print(count(10, None, {}, lambda n, last: n))
print(count(10, None, {}, lambda n, last: (n, last)))
Output
17711
1536
17711

In production One state, three questions, and an honest key

PythonFeasible, count and cheapest plan from one (slot, last) stateruns
INF = float("inf")

def solve(n, kinds, banned, cost, key_mode="state"):
    """Pick one kind per slot; (prev, next) pairs in `banned` are illegal.
    Returns (feasible, count, min_cost, memo_entries). Recursive: keep n below ~900
    (default recursion limit 1000; see dsa-07-03)."""
    memo = {}
    def go(i, last, hist):
        k = (i, last) if key_mode == "state" else hist
        if k in memo:
            return memo[k]
        if i == n:
            res = (True, 1, 0)                     # base: nothing left to place
        else:
            feas, cnt, best = False, 0, INF
            for s in kinds:
                if (last, s) in banned:
                    continue
                f, c, m = go(i + 1, s, hist + (s,))
                if not f:
                    continue                       # never add to the INF sentinel
                feas, cnt, best = True, cnt + c, min(best, m + cost[s])
            res = (feas, cnt, best)
        memo[k] = res
        return res
    return go(0, None, ()) + (len(memo),)

cost = {"A": 3, "B": 1, "C": 2}
banned = {("A", "C"), ("B", "B")}
print(solve(0, "ABC", banned, cost))
print(solve(1, "ABC", banned, cost))
print(solve(12, "ABC", banned, cost))
print(solve(12, "ABC", banned, cost, key_mode="history"))
print(solve(3, "B", {("B", "B")}, {"B": 1}))
print(solve(4, "AB", {(p, q) for p in "AB" for q in "AB"}, {"A": 5, "B": 0}))
Output
(True, 1, 0, 1)
(True, 3, 1, 4)
(True, 23427, 18, 37)
(True, 23427, 18, 42212)
(False, 0, inf, 2)
(False, 0, inf, 3)

See it happen Two states, one wrong key

memo keyed by n only (key 2)5memo keyed by (n, last): (2,A) and (2,B)58
  1. Both memos start empty; the question is how many ways to fill 2 remaining slots.
  2. A call with 2 slots left after A computes 5 ways (A cannot be followed by C) and stores it.
  3. A call with 2 slots left after B has 8 ways, but the n-only memo finds key 2 and returns 5.
  4. The (n, last) memo treats it as a new state and stores 8 beside the 5.
Notice: The collision sits in one cell: the second state reads the first state's answer.
Scenario A

In your world

The situation

A nightly planner schedules 30 days of runs, each FULL (A), DELTA (B) or REPAIR (C); REPAIR may not directly follow FULL. A Jenkins stage prints the number of legal plans to size the QA matrix.

What actually breaks

The memo was keyed on days remaining only. The stage prints 1,610,612,736 and stays green; the true count is 4,052,739,537,881. The matrix is about 2,500 times too small; nothing errors.

What you'd do on Monday

Key on (days_left, last): 31 x 4 states, 3 transitions each, about 370 steps. Add a check comparing the memo with plain recursion at n = 10 (17,711) and fail the build on mismatch.

Scenario B

Imagine you work at LinkedIn

20 feed slots, 4 item types

The numbers

Fill 20 slots from 4 types (post, job, ad, suggestion), no two adjacent equal. Histories: 4 x 3^19 = 4,649,045,868. State (slot, last): 20 x 4 = 80 states x 4 transitions = 320 checks. Add "at most 3 ads": (slot, last, ads_used) = 20 x 4 x 4 = 320 states, 1,280 checks.

What the Scenario-A answer does here

The Monday fix, a key of exactly the variables the rules read, still works. What breaks is keying on the partial feed: 4.6 billion entries cannot exist, while the true state is under a thousand.

What flips at this scale

Each new rule asks whether the future reads something not yet in the key. Add that one variable with its smallest range (ads used 0-3, not ad positions); state count multiplies by that range, never by history length.

The trade-off you'd defend

I would defend a small rule-derived state over a history key, trading an hour of thinking per rule for a memo under a thousand entries.

Illustrative; slot count, types and rules are assumptions, not LinkedIn-published. Arithmetic is exact for them.

Gotchas

Key omits a dependency

Symptom

Memo count 1,536 where brute force gives 17,711, no exception.

Cause

States differing in last shared one entry.

Fix

List every variable any rule reads and key on all of them; cross-check small n against brute force.

Key stores the whole history

Symptom

Correct answer but 42,212 memo entries for 12 slots instead of 37.

Cause

No two paths share a key, so the cache never hits.

Fix

Key on the summary the future reads (state mode in the production block).

Unhashable argument

Symptom

TypeError: unhashable type: 'list'.

Cause

The cache is a dict and a list cannot be a key.

Fix

Pass a tuple or an index.

PythonLists cannot be cache keysruns
from functools import cache

@cache
def total(xs):
    return sum(xs)

try:
    total([1, 2])
except TypeError as e:
    print("TypeError:", e)
print(total((1, 2)))
Output
TypeError: unhashable type: 'list'
3

Tricky questions

"Use DP whenever it asks for a maximum."
Most people say

A maximum with a recursive description means DP.

Actually

DP needs overlapping states and a small summary of the past. A provably safe local choice is greedy; with no repeated sub-situation it is a scan.

Scenario question

You're handed a function counting valid weekly schedules, memoised on (day,). It is right for 3 days and wrong for 10. Find the bug and say how you will trust the fix.

Model answer

I list what the validity rule reads: the previous day's mode. It is missing from the key, so I change it to (day, last_mode) and compare against brute force for n up to about 12, plus n = 0. The trade-off is a table four times larger for a correct answer; a smaller wrong table is no optimisation.

Interview corner

CommonWhat does your DP function return, and what are its arguments?
“I'd say it in one sentence first: f(i, last) is the number of ways to fill slots i onward given the previous kind. Then the key, recurrence and answer location follow.”
TrickYour memo gives a smaller count than brute force. Where do you look?
“I'd look at the key before the recurrence. A variable the rules read is probably missing, so two states collide. I'd print both keys for a small n to find the collision.”
Experience checkHave you cached something whose key was incomplete?
“I've seen a lookup keyed on customer but not effective date return stale values, so I list every input first.”

Memory hook

The state is the notebook entry that lets the trip planner forget the diary.

If you remember only one thing:

Put every variable the future reads in the key and nothing else.

Self-check

  1. What three questions can one state answer?

    Feasibility, counting and optimization; only the combine step changes.

  2. Why does keying on the full path defeat memoisation?

    No two paths share a key, so there are no hits and entries are exponential.

  3. Which variables belong in the key?

    Those the remaining rules read.

Prove it

Assert brute force equals the (n, last) memo for n = 1..12, then run the n-only key and paste the first n where they differ, plus the 30-day count 4,052,739,537,881.

dsa-07-02Card 2 of 6

Derive recurrence and dependency order

HardP3 · Role-dependentKnow cold8 min
dprecurrencebase-casedependency-ordersentinel

Why you care

A wrong recurrence rarely crashes. It reads an unfilled cell, adds to an "unreachable" marker or counts one choice twice, and the output still looks like a number. In ETL that is a cost table finance trusts because the values look plausible. Interviewers ask for recurrence and fill order separately because proving it reads only finished values is where candidates stall.

Explain like I'm 5

A recipe card says "use the sauce from card 3 and the dough from card 5". You may cook a card only when its ingredients are on the counter. Base cases are what you already own. An impossible dish needs an ingredient that does not exist, and the kitchen must not pretend it costs zero.

Core concept

Write four parts before code: meaning of f(state), transitions (every legal choice, with its local contribution), combine (min, +, or) and base and impossible states.

  • Exhaustive: every legal way into the state is a transition.
  • For counting, each complete solution is counted once. Split by one unique decision such as the last step.
  • Acyclic: pick a numeric order (index, budget, prefix length) in which every dependency is strictly earlier. That is your proof the fill reads finished cells.
  • Unreachable is inf or None, never -1 or 10**9, and never added to.
  • Time is states times work per state, the sum of transition counts.

If dependencies are a general graph, order them with Topological sort and dependency cycles first. If they contain a cycle there is no DP.

Under the hood

Memoised recursion caches on return, not on entry. A cyclic dependency therefore never fills the cache and runs until RecursionError; read the limit (default 1000) with sys.getrecursionlimit(). float("inf") behaves: inf + 5 is inf and min(inf, x) is x. Integer stand-ins have no such property.

Minimal example Fill order is part of the recurrence

PythonThe same recurrence, two ordersruns
w = {(0, 1): 1, (0, 2): 4, (1, 2): 2, (2, 3): 5, (1, 3): 9}   # edges j -> i

def fill(order):
    f = {0: 0}
    for i in order:   # a missing f[j] reads as 0: the bug being shown
        f[i] = min(f.get(j, 0) + c for (j, t), c in w.items() if t == i)
    return f

print(fill([1, 2, 3]))   # dependency order
print(fill([2, 1, 3]))   # node 2 reads f[1] before f[1] exists
Output
{0: 0, 1: 1, 2: 3, 3: 8}
{0: 0, 2: 2, 1: 1, 3: 7}

In production A dependency-ordered table for costs and path counts

PythonCheapest cost and path count with explicit unreachable handlingruns
import math
INF = math.inf

def route_table(n, edges, mode="min"):
    """f[i] over nodes 0..n-1 from node 0. Edges (j, i, w) need j < i: that is the
    acyclicity proof. mode 'min' = cheapest cost, 'count' = number of distinct paths."""
    preds = [[] for _ in range(n)]
    for j, i, wt in edges:
        if not 0 <= j < i < n:
            raise ValueError(f"edge {j}->{i} breaks the order contract")
        preds[i].append((j, wt))
    if n == 0:
        return []
    f = [INF] * n if mode == "min" else [0] * n
    f[0] = 0 if mode == "min" else 1             # base: the origin
    for i in range(1, n):
        for j, wt in preds[i]:
            if mode == "min":
                if f[j] != INF:                  # unreachable stays INF
                    f[i] = min(f[i], f[j] + wt)
            else:
                f[i] += f[j]                     # each path has exactly one last edge
    return f

edges = [(0, 1, 1), (0, 2, 4), (1, 2, 2), (2, 3, 5), (1, 3, 9)]
print(route_table(4, edges))
print(route_table(4, edges, "count"))
print(route_table(5, edges))                    # node 4 has no incoming edge
print(route_table(1, []), route_table(0, []))
for bad in ([(2, 1, 1)], [(1, 1, 1)]):
    try:
        route_table(3, bad)
    except ValueError as e:
        print("ValueError:", e)
Output
[0, 1, 3, 8]
[1, 1, 2, 3]
[0, 1, 3, 8, inf]
[0] []
ValueError: edge 2->1 breaks the order contract
ValueError: edge 1->1 breaks the order contract

See it happen Filling a cost table in dependency order

f[0..3]0127
  1. Base case: f0 is 0 because the origin costs nothing; every other slot starts at INF, meaning not reached yet.
  2. f1 reads only f0: 0 + 1 = 1, so the first finished value comes from the base.
  3. f2 reads f0 and f1: min(0 + 4, 1 + 2) = 3, both dependencies already finished.
  4. f3 reads f2 and f1: min(3 + 5, 1 + 9) = 8, and the answer is the last cell.
  5. Wrong order on the same graph: f2 is computed before f1 exists, reads it as 0, gets 2 instead of 3, and f3 drifts to 7.
Notice: Each cell is final when written because everything it reads sits to its left; the bad frame breaks exactly that promise.
Scenario A

In your world

The situation

A Jenkins stage builds a fee table: cheapest total fee from the settlement hub to each of 6,000 merchant accounts over banking hops. Accounts with no route get -1 so the CSV column stays integer.

What actually breaks

A later step computed table[hop] + fee. Merchant 4,118 had no route, and -1 + 3 produced a "cheapest fee" of 2. The stage logged 6,000 rows, finance saw a fee no bank offers, nothing failed.

What you'd do on Monday

Keep INF inside the computation and convert at the output edge; branch before adding.

Python
if f[j] != INF:
    f[i] = min(f[i], f[j] + wt)
row = None if f[i] == INF else f[i]      # write NULL, not -1, to Postgres

Assert every edge has j < i after numbering, so a cycle fails the build.

Scenario B

Imagine you work at Juspay

3M payment requests/day

The numbers

A fee graph of 5,000 nodes and 20,000 edges. One table is the sum of in-degrees, 20,000 relaxations; at an assumed 1M/s that is 20 ms. Per request: 3,000,000 x 20 ms = 60,000 s = 16.7 CPU-hours/day. With 200 origins and 30 fee-schedule versions a day: 200 x 30 x 20 ms = 120 s/day.

What the Scenario-A answer does here

The Monday fix, a correct recurrence with honest INF, still holds. What breaks is running it inside the request path: 20 ms of repetition per request on a table that has not changed.

What flips at this scale

Move the state out of the call. Key the table on (origin, schedule_version); requests look up, and a new version triggers one rebuild. The recurrence is untouched.

The trade-off you'd defend

I would defend precomputing per version over per-request recomputation, trading memory (200 tables x 5,000 = 1M cells) and a staleness window at version switch for 20 ms off every request.

Illustrative; graph size, volume and 1M relaxations/s are assumptions, not Juspay-published.

Gotchas

Integer sentinel for unreachable

Symptom

A node with no route shows a plausible cost (2 below).

Cause

-1 + 3 is a normal integer.

Fix

Use inf or None and test before adding.

Python-1 is not a safe sentinelruns
f = {0: 0, 4: -1}                       # node 4 unreachable, marked -1
print("sentinel -1 gives cost", f[4] + 3)
INF = float("inf")
print("inf stays", INF + 3, min(INF, 8))
Output
sentinel -1 gives cost 2
inf stays inf 8

A dependency cycle in memoised recursion

Symptom

RecursionError rather than a wrong number.

Cause

A state depends on itself, so no call finishes and nothing is cached.

Fix

Re-derive the order; a truly cyclic dependency is not this DP.

PythonCycle hits the recursion limitruns
from functools import cache

@cache
def f(i):
    return 1 + f((i + 1) % 3)           # 0 -> 1 -> 2 -> 0 ...

try:
    f(0)
except RecursionError:
    print("RecursionError: no base case reachable")
Output
RecursionError: no base case reachable

Duplicate transitions double count

Symptom

Path counts [1, 2, 3, 5] where the distinct graph gives [1, 1, 2, 3].

Cause

One edge row arrived twice, so every path through it is counted twice downstream.

Fix

Make transitions a set of distinct decisions before counting.

PythonDuplicate edge inflates the countruns
edges = [(0, 1), (0, 2), (1, 2), (2, 3), (1, 3)]
def paths(es):
    c = [1, 0, 0, 0]
    for j, i in sorted(es, key=lambda e: e[1]):
        c[i] += c[j]
    return c
print(paths(edges + [(0, 1)]), paths(sorted(set(edges + [(0, 1)]))))
Output
[1, 2, 3, 5] [1, 1, 2, 3]

Tricky questions

"The recurrence is right, so loop order does not matter."
Most people say

Any order that touches every cell gives the same table.

Actually

The order is part of the proof. A cell must come after everything it reads; the minimal example returns 7 or 8 from one formula.

Scenario question

You're handed a cost table where some unreachable destinations show small positive numbers. Diagnose it.

Model answer

I first check how unreachable is encoded. An integer like -1 or a large constant may have had a hop cost added. I reproduce with one unreachable node, then switch to inf or None with an explicit branch, and assert every dependency index is smaller than the cell. The trade-off is clumsier code and NULL handling at the output edge, for numbers I can defend.

Interview corner

CommonHow do you write a recurrence?
“I'd write meaning, transitions, combine and base cases in that order, then state the order: every dependency strictly earlier. That is my proof the fill is valid.”
TrickWhy is counting harder to get right than minimising?
“I'd say duplicates are harmless in a min but fatal in a sum. For counting I split by one unique decision, like the last step, so each solution appears once.”
Experience checkHave you seen a sentinel cause a silent wrong number?
“I've seen a zero default for missing prices flow into a total. It is the same bug as a -1 distance, so I use NULL or inf and branch before arithmetic.”

Memory hook

A recipe card may only use ingredients already on the counter.

If you remember only one thing:

Every dependency must be computed earlier, and unreachable must never be a number you add to.

Self-check

  1. What proves a fill order is valid?

    Every dependency of a cell has a strictly smaller position in that order.

  2. Why not use -1 for unreachable in a min-cost table?

    -1 + w can win a min or leak into a sum.

  3. What is the time cost of a recurrence?

    States times work per state, the sum of transition counts.

Prove it

Implement route_table on a 6-node DAG with one unreachable node. Paste the cost list, the path-count list and the ValueError for a backward edge. Then replace INF with -1 and paste the wrong value that appears.

dsa-07-03Card 3 of 6

Memoization versus tabulation in 1D and 2D

MediumP3 · Role-dependentKnow cold8 min
dpmemoizationtabulationrecursion-depth2d-table

Why you care

You will meet both styles. Each fails differently. Recursion passes the test grid and raises RecursionError on the real one; a table built with [[0]*m]*n shares one row and gives quietly wrong totals. Interviewers ask for both to see whether you understand the recurrence or only a template.

Explain like I'm 5

Memoisation is a clerk who answers questions as customers ask and writes each answer on a sticky note. Tabulation is a clerk who fills a whole spreadsheet from the bottom row up before opening. The first works only on questions asked; the second does everything but never leaves customers waiting.

Core concept

Same recurrence, two evaluators.

  • Memoisation: recursion plus a cache keyed on the state. Only reachable states run. Recursion depth equals the longest dependency chain, and CPython's default limit (1000; read sys.getrecursionlimit()) applies.
  • Tabulation: loops over an array in dependency order. Every state is computed. No recursion, predictable memory, old rows can be dropped (Space optimization without losing dependencies).
  • 1D versus 2D: one axis per independent state variable. Include a padding row or column for empty or off-grid cases.
  • Keys are immutable: ints, tuples, strings.
  • Build rows with [[0]*m for _ in range(n)]; [[0]*m]*n repeats one row object.

Use memoisation when reachable states are a small fraction of the space. Use tabulation when most states are needed, depth may exceed the limit, or you want to compress space. Raising sys.setrecursionlimit is not a plan.

Minimal example Aliased rows and the recursion limit

PythonTwo classic table failuresruns
from functools import cache
rows = [[0] * 3] * 2
rows[0][1] = 7
print(rows)
good = [[0] * 3 for _ in range(2)]
good[0][1] = 7
print(good)

@cache
def depth(n):
    return 0 if n == 0 else 1 + depth(n - 1)
try:
    depth(100_000)
except RecursionError:
    print("RecursionError at n=100000")
Output
[[0, 7, 0], [0, 7, 0]]
[[0, 7, 0], [0, 0, 0]]
RecursionError at n=100000

In production Both evaluators over an abstract dependency rule

PythonMemo versus table: reachable states, keys, depthruns
def deps(i, j, R, C):
    """Abstract rule: even rows depend on the cell below and to the right, odd rows on the right."""
    out = []
    if i % 2 == 0 and i + 1 < R:
        out.append((i + 1, j))
    if j + 1 < C:
        out.append((i, j + 1))
    return out

def eval_memo(R, C):
    memo = {}                                    # keys are tuples: immutable and hashable
    def go(s):
        if s not in memo:
            ds = deps(*s, R, C)
            memo[s] = 1 if not ds else 1 + sum(go(d) for d in ds)
        return memo[s]
    return (go((0, 0)), len(memo)) if R and C else (0, 0)

def eval_table(R, C):
    if not R or not C:
        return 0, 0
    t = [[0] * C for _ in range(R)]              # not [[0] * C] * R
    for i in range(R - 1, -1, -1):               # dependencies have larger i or j: fill them first
        for j in range(C - 1, -1, -1):
            ds = deps(i, j, R, C)
            t[i][j] = 1 if not ds else 1 + sum(t[a][b] for a, b in ds)
    return t[0][0], R * C

for R, C in [(0, 3), (1, 1), (1, 4), (4, 4), (40, 40)]:
    print(R, C, "memo", eval_memo(R, C), "table", eval_table(R, C))
try:
    eval_memo(600, 600)
except RecursionError:
    print("memo 600x600: RecursionError")
print("table 600x600 cells:", eval_table(600, 600)[1])
Output
0 3 memo (0, 0) table (0, 0)
1 1 memo (1, 1) table (1, 1)
1 4 memo (4, 4) table (4, 4)
4 4 memo (14, 8) table (14, 16)
40 40 memo (860, 80) table (860, 1600)
memo 600x600: RecursionError
table 600x600 cells: 360000

Pairs are (value, states evaluated): the memo touches 8 of 16 and 80 of 1,600 states.

See it happen Bottom-up fill of a 2 x 3 table

row 0952row 1 (last)952
  1. Nothing is computed yet; the table is a plan, not a result.
  2. The base case first: the bottom-right cell has no dependencies, so its value is 1.
  3. Rest of the last row, right to left: each odd-row cell reads only its right neighbour.
  4. Row 0 starts from its last column, which reads only the cell below: 1 + 1 = 2.
  5. Remaining row-0 cells read the cell below and the cell to the right, both already finished: 5 then 9.
  6. Run with aliased rows, the finished table has both rows equal to 9, 5, 2, because both names are one list; row 1 should be 3, 2, 1.
Notice: The fill direction is the reverse of the call direction, and the last frame shows why one shared row object ruins it.
Scenario A

In your world

The situation

You build a cumulative table of 6 settlement days by 3 payment channels as table = [[0]*3]*6, add each day's amounts, and load the grand total into Postgres.

What actually breaks

Day 0 adds 100 to channel 1 and day 1 adds 50. All six rows are one list, so every row shows 150 and the grand total of that column reads 900, not 150. The audit table logged 18 cells and the job was green.

What you'd do on Monday

Build rows with a comprehension and assert independence once. For long chains, tabulate: with a 1000-frame default limit, a 1,500-step path fails on real data and passes on a 30-row fixture.

Python
table = [[0] * 3 for _ in range(6)]
assert len({id(r) for r in table}) == len(table)
Scenario B

Imagine you work at Instacart

2,000 store layouts, nightly

The numbers

Each layout is 1,500 aisle positions x 80 shelf slots = 120,000 states, 2 transitions = 240,000 steps. At an assumed 2.5M steps/s that is about 0.1 s per store, 2,000 stores = 200 s. The longest dependency chain is 1,500 + 80 - 1 = 1,579 calls, above the default 1000 limit. The table is 120,000 cells x ~41 B (distinct ints above 256) = 4.9 MB; about 1.1 MB at 8.9 B if values stay at or below 256.

What the Scenario-A answer does here

The Monday fix, a comprehension-built table, still holds. What fails is the memoised recursion that passed on 30 x 30 layouts (chain 59): on a real layout it raises RecursionError mid-run.

What flips at this scale

Tabulate row by row so no frames stack up. Chain length stops mattering and memory is a flat array.

The trade-off you'd defend

I would defend bottom-up tabulation for production layouts, trading the reachable-only saving of memoisation for a loop that cannot overflow the stack.

Illustrative; grid size, store count and 2.5M steps/s are assumptions, not Instacart-published. Per-cell bytes measured with tracemalloc on CPython 3.12.4: 8.9 B for ints up to 256, 40.9 B for distinct ints above 256.

Gotchas

Aliased rows in a 2D table

Symptom

Writing one cell changes that column in every row ([[0, 7, 0], [0, 7, 0]]).

Cause

[[0]*m]*n repeats a reference to one list.

Fix

[[0]*m for _ in range(n)], as in the minimal example.

RecursionError on a long chain

Symptom

RecursionError on real input while small tests pass.

Cause

Memo depth equals the dependency chain; the default limit is 1000 frames.

Fix

Tabulate or use an explicit stack (production block, 600 x 600).

A cache smaller than the working set evicts states

Symptom

Same answer but 11,456 calls instead of 224, and runtime explodes with size.

Cause

lru_cache evicts when maxsize is below the states still needed. 4 is too small here; the default 128 sufficed, but not once live states exceed 128.

Fix

Pass maxsize=None or use functools.cache (3.9+), and compare call counts.

PythonEviction forces recomputationruns
from functools import lru_cache

def calls_for(maxsize, n=14):
    calls = 0
    @lru_cache(maxsize=maxsize)
    def f(i, j):
        nonlocal calls
        calls += 1
        return 1 if i == 0 or j == 0 else 1 + max(f(i - 1, j), f(i, j - 1))
    f(n, n)
    return calls

print(calls_for(None), calls_for(128), calls_for(4))
Output
224 224 11456

Tricky questions

"Memoisation and tabulation cost the same."
Most people say

Same recurrence means same time and memory.

Actually

Memoisation touches only reachable states (80 of 1,600 above) but pays call overhead and stack depth; tabulation touches all, loop-cheap and stack-free.

Scenario question

You're handed a memoised 2D function that works on 50 x 50 inputs and fails on 5,000 x 200. What do you do?

Model answer

I compute the dependency chain, 5,199 calls (R + C - 1), and compare it with sys.getrecursionlimit(). It exceeds it, so I convert to a bottom-up table with the same axes. The trade-off: I now evaluate all 1,000,000 cells even if many are unreachable, and must prove the loop order; I accept that over a stack failure.

Interview corner

CommonMemoisation or tabulation, and why?
“I'd start with memoisation because it follows the recurrence directly, then move to a table if depth is a problem or I need space compression.”
TrickWhat is wrong with [[0]*m]*n?
“I'd say it makes n references to one row, so a write shows in every row. I use a comprehension and check the rows are distinct objects.”
Experience checkWhen have recursion limits bitten you?
“I haven't in DP yet, but I hit it recursing over nested JSON in an ETL job. The fix was an explicit stack, and I'd do the same for a deep memo.”

Memory hook

A clerk with sticky notes answers what is asked; a clerk with a spreadsheet fills every row first.

If you remember only one thing:

Memo is bounded by stack depth, a table by loop order; the recurrence is the same.

Self-check

  1. Which evaluator touches only reachable states?

    Memoisation.

  2. Why does [[0]*m]*n break a table?

    All rows are the same list object, so a write changes every row.

  3. Why not just raise the recursion limit?

    It can turn a clean RecursionError into an interpreter crash; tabulate instead.

Prove it

Run eval_memo and eval_table on 60 x 60 and paste both value pairs. Then confirm the 600 x 600 memo RecursionError and, by changing the rule so even rows depend on the right only, find the smallest square size where it stops failing.

dsa-07-04Card 4 of 6

Recognize the knapsack family

HardP3 · Role-dependentTalk about it7 min
dpbudgetreusepseudopolynomialupdate-direction

Why you care

"Pick things under a limit" shows up as capacity planning, batch sizing, payout files under a bank cap, or jobs in a time window. Candidates who recognise it pick the state quickly; the rest reach for a plausible, wrong greedy rule. Interviewers ask because reuse changes the loop direction and "pseudopolynomial" is easy to misstate.

Explain like I'm 5

A suitcase has a weight limit and you have a pile of things, each with a weight and a worth. For every total weight you track the best worth achievable, going through the pile one item at a time. What changes the algorithm is whether you own one copy of each thing or a shelf with endless copies.

Core concept

Signals: a numeric budget, items with a cost and maybe a value, a choice per item, and a goal of best value, reachability or count.

  • State: dp[b] = best value at total cost b (exact) or at most b. The item index is implicit in the pass.
  • Availability: 0/1 at most once, unbounded any number, bounded up to k (as k separate 0/1 items).
  • Update direction is reuse control. High to low: dp[b - cost] still holds the row from before this item, so no reuse. Low to high: it may already include this item, so copies are allowed.
  • Contract: exactly b seeds only dp[0]; at most b seeds every leftover.
  • Cost is O(items x budget): pseudopolynomial, polynomial in the budget's value but exponential in its bit length.

Skip it when a greedy rule is proven or costs cannot be quantised.

Under the hood

The in-place array is the 2D table dp[item][b] with the item axis collapsed. Descending loops read the previous-item row because smaller indices are not yet overwritten; ascending loops read the current-item row because they are. A 5,000,000-entry list is at least 40 MB of pointers.

Minimal example Direction decides whether an item can be reused

PythonReachable totals with each cost once versus many timesruns
def reachable(costs, budget, once):
    ok = [True] + [False] * budget
    for c in costs:
        order = range(budget, c - 1, -1) if once else range(c, budget + 1)
        for b in order:
            ok[b] = ok[b] or ok[b - c]
    return [b for b in range(budget + 1) if ok[b]]

print(reachable([3, 5], 9, once=True))
print(reachable([3, 5], 9, once=False))
Output
[0, 3, 5, 8]
[0, 3, 5, 6, 8, 9]

In production Reuse and contract skeleton, reachability only

PythonDirection controls reuse; initialisation controls the contractruns
def reachable_totals(costs, budget, reuse="once", copies=None):
    """Reachability only: which exact totals <= budget can be spent? No values, no optimum."""
    if budget < 0:
        raise ValueError("budget must be >= 0")
    ok = [True] + [False] * budget                 # exact-fill contract: only 0 is reachable
    for k, c in enumerate(costs):
        if c < 0 or (c == 0 and reuse == "unbounded"):
            raise ValueError("cost must be >= 0 (> 0 when unbounded)")
        passes = copies[k] if reuse == "bounded" else 1
        order = range(c, budget + 1) if reuse == "unbounded" else range(budget, c - 1, -1)
        for _ in range(passes):
            for b in order:
                if ok[b - c]:
                    ok[b] = True
    return [b for b in range(budget + 1) if ok[b]]

def start_row(budget, exact):
    return [0] + [None] * budget if exact else [0] * (budget + 1)

print(reachable_totals([3, 5], 9), reachable_totals([3, 5], 9, "unbounded"))
print(reachable_totals([3], 9, "bounded", [2]), reachable_totals([4], 3), reachable_totals([], 0))
print(reachable_totals([0, 2], 4), reachable_totals([], 5))
try:
    reachable_totals([0], 4, "unbounded")
except ValueError as e:
    print("ValueError:", e)
print(start_row(3, True), start_row(3, False))
items = [(6, 60), (5, 45), (5, 45)]                # (cost, value), budget 10
first = max(items, key=lambda it: it[1] / it[0])
print("greedy:", first[1], "vs hand pick:", 45 + 45, "at cost", 5 + 5)
Output
[0, 3, 5, 8] [0, 3, 5, 6, 8, 9]
[0, 3, 6] [0] [0]
[0, 2] [0]
ValueError: cost must be >= 0 (> 0 when unbounded)
[0, None, None, None] [0, 0, 0, 0]
greedy: 60 vs hand pick: 90 at cost 10

Start rows are the contract: exact seeds only spend 0, at-most seeds every leftover. No best value is computed here.

Scenario A

In your world

The situation

A payout planner fills a bank file up to a limit of 9 lakh from pending payouts of 3 and 5 lakh, each sendable once. Ops choose from the totals the file can reach.

What actually breaks

The loop ran for b in range(c, budget + 1). The planner offered totals 6 and 9, which exist only if the 3-lakh payout is sent two or three times. The file passed its schema check; the duplicate surfaced at reconciliation.

What you'd do on Monday

Descending loop for once-only items, with a test that expects [0, 3, 5, 8].

Python
for b in range(budget, c - 1, -1):    # not range(c, budget + 1)
    ok[b] = ok[b] or ok[b - c]
Scenario B

Imagine you work at Coinbase

300 candidate trades, budget in cents

The numbers

Allocate a $50,000 risk budget over 300 positions. At 1-cent precision the axis is 5,000,000 cells: 300 x 5,000,000 = 1.5 billion updates. At an assumed 2.5M updates/s that is 600 s, and the array is 5,000,000 x 8 B = 40 MB of pointers. At $1 precision: 300 x 50,000 = 15,000,000 updates, 6 s. In 10^-8 units the budget needs 5 x 10^12 cells.

What the Scenario-A answer does here

The Monday fix, correct direction and an explicit contract, stays correct. The table size is the problem: work follows the budget's value, so a finer unit multiplies it and an hourly run misses its window.

What flips at this scale

Quantise. Round every cost up to a coarser unit so a chosen set can never exceed the true budget, and accept some lost optimality of at most items x unit.

The trade-off you'd defend

I would defend rounding costs up to a coarser grid over a cent-level table, trading unused budget (at most 300 x $1) for a 100x smaller table. If that loss is not acceptable I would use an integer-programming solver, not a bigger loop.

Illustrative; item count, budget and update rate are assumptions, not Coinbase-published. Table arithmetic is exact for them.

Gotchas

Wrong update direction

Symptom

Totals 6 and 9 appear with only one 3 available.

Cause

An ascending loop lets dp[b - cost] include the current item.

Fix

Descending for once-only items; print a small case to check, as in the minimal example.

Exact versus at-most mix-up

Symptom

A total reported reachable that was never spent, or leftover budget rejected.

Cause

Initialisation encodes the contract; the production output shows [0, None, None, None] against [0, 0, 0, 0].

Fix

State the contract first, then initialise.

Greedy by value density

Symptom

Answer 60 where 90 exists (production output; 90 is summed by hand).

Cause

Best value-per-cost first can block a combination that fits exactly.

Fix

Keep greedy only with a proof.

PythonPseudopolynomial: table size follows the value of the budgetruns
for bits in (20, 30, 40):
    print(bits, 300 * 2 ** bits)
Output
20 314572800
30 322122547200
40 329853488332800

Tricky questions

"The budget fits in 4 bytes, so O(items x budget) is polynomial."
Most people say

Cost is linear in the input.

Actually

The input is the budget's digits; the work follows its value. 20 bits is about 3 x 10^8 cells for 300 items, 40 bits about 3 x 10^14.

Scenario question

You're handed a service that picks jobs to fit a time window and sometimes schedules one job twice. Check and fix it.

Model answer

I confirm availability: each job once. Then I read the update loop; an ascending pass reuses a job. I switch to descending and add a test with one job whose cost divides the window. Time is unchanged.

Interview corner

CommonHow do you recognise this family?
“I'd look for a numeric limit plus costed choices, then ask: can an item be reused, is the limit exact or at most, and is the goal value, reachability or count.”
TrickWhy does loop direction matter?
“I'd say it decides which row I read. Descending reads the previous item's values, so an item is used once; ascending reads the current item's, so it can repeat.”
TrickIs O(items x capacity) polynomial?
“I'd say pseudopolynomial: polynomial in the capacity's value, exponential in its bit length. Adding a digit multiplies the work.”

Memory hook

Same suitcase, but the loop direction decides whether the shelf holds one copy or endless copies.

If you remember only one thing:

Descending budget loop means each item once; ascending means reuse, and work scales with the budget's value.

Self-check

  1. What does an ascending budget loop allow that a descending one does not?

    Reusing the current item within the same pass.

  2. How do you encode exactly b versus at most b?

    Exact: only dp[0] reachable at the start. At most: all zeros.

  3. Why is it called pseudopolynomial?

    Work grows with the budget's numeric value, exponential in its bit length.

Prove it

Run the production block and paste its six output lines. Then compare reachable_totals([3], 9, "bounded", [2]) with reachable_totals([3], 9) and explain, from the passes and loop direction, why one gives [0, 3, 6] and the other [0, 3].

dsa-07-05Card 5 of 6

LIS and string DP state families

HardP3 · Role-dependentTalk about it8 min
dpsubsequenceprefix-statesstring-dpreconstruction

Why you care

Ordering and alignment questions are everywhere in data work: matching exports with inserted lines, detecting out-of-order sequence numbers, deduplicating near-identical references. The states are "ending at position i" for one sequence and a prefix pair (i, j) for two. Interviewers ask because the contract (substring or subsequence, strict or not, length or items) changes the answer.

Explain like I'm 5

You want the longest stretch of stepping stones you can cross in order. For one row, ask of each stone: what is the longest path ending right here? For two paths, ask about the first i stones of one and the first j of the other. Zero stones is legal and worth nothing.

Core concept

Pin the contract first; the state follows.

  • Subsequence keeps order but may skip; a substring is contiguous and needs only a running counter.
  • Strict versus non-decreasing is one operator; [2, 2, 2] gives chain 1 or 3.
  • One sequence: best[i] = longest chain ending exactly at i; scan allowed earlier j (see predecessors); answer is the max over i. O(n squared).
  • Two sequences: t[i][j] over prefixes; row 0 and column 0 are empty prefixes, so cell (1, 1) has something to read. Size (n+1) x (m+1), O(1) per cell.
  • Length versus reconstruction: a length needs values only; the items need a walk back, and ties mean the tie rule decides which prints.
  • An O(n log n) "tails" method gives the chain length by storing a different summary. The tails array alone is not a chain; reconstruction needs extra predecessor pointers.

Use the quadratic scan for a few thousand elements or when you need the chain.

Under the hood

A prefix-table cell costs a few bytecodes: about 0.4-0.5 s per million cells on 3.12.4. Measured per cell: 40.9 B for distinct ints above 256, 8.9 B at or below. So 5,000 x 5,000 = 25M cells is about 1 GB, or 0.2 GB if small.

Minimal example One comparison changes the allowed predecessors

PythonStrict versus non-decreasing on equal valuesruns
def predecessors(xs, ok):
    """For each index i, the earlier indices j allowed directly before it in a chain."""
    return [[j for j in range(i) if ok(xs[j], xs[i])] for i in range(len(xs))]

xs = [2, 2, 2]
print(predecessors(xs, lambda a, b: a < b), predecessors(xs, lambda a, b: a <= b))
print(predecessors([5, 1, 6], lambda a, b: a < b), predecessors([], lambda a, b: a < b))
Output
[[], [], []] [[], [0], [0, 1]]
[[], [], [0, 1]] []

In production Prefix-grid scaffolding with an empty border

PythonThe shape of the table, with the cell rule left to the callerruns
def prefix_grid(n, m, cell, border=0):
    """(n+1) x (m+1) grid. Row 0 and column 0 are the EMPTY prefixes and hold `border`.
    cell(i, j, up, left, diag) is supplied by the caller: scaffolding, not a solution."""
    if n < 0 or m < 0:
        raise ValueError("lengths must be >= 0")
    g = [[border] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            g[i][j] = cell(i, j, g[i - 1][j], g[i][j - 1], g[i - 1][j - 1])
    return g

a, b = "ab", "ba"
match = lambda i, j: a[i - 1] == b[j - 1]
for row in prefix_grid(len(a), len(b), lambda i, j, u, l, d: match(i, j), border=False):
    print(row)
print(prefix_grid(2, 2, lambda i, j, u, l, d: (u, l, d), border="edge")[1][1])
print(prefix_grid(0, 3, None), prefix_grid(0, 0, None))
for n, m in [(4, 6), (25_000, 25_000)]:
    print(n, m, "length-only keeps", m + 1, "cells; a path needs", (n + 1) * (m + 1))
tie = lambda up, left, prefer_up: "up" if (up > left or (up == left and prefer_up)) else "left"
print(tie(2, 2, True), tie(2, 2, False))
Output
[False, False, False]
[False, False, True]
[False, True, False]
('edge', 'edge', 'edge')
[[0, 0, 0, 0]] [[0]]
4 6 length-only keeps 7 cells; a path needs 35
25000 25000 length-only keeps 25001 cells; a path needs 625050001
up left

The grid marks character matches; the edge probe shows cell (1, 1) reading only the border; the last line is a tie.

See it happen The empty border feeds the first cell

row 0: empty prefix of Aedgeedgeedgerow 1: A[:1]edgec11c12
  1. Row 0 is the empty prefix of A, so every cell holds the border value before any comparison happens.
  2. Cell (1, 1) reads up, left and diagonal, and all three come from the border.
  3. Cell (1, 2) reads up from the border, left from the cell just computed, and the diagonal from the border.
Notice: Without the border row and column the first real cell would have nothing to read.
Scenario A

In your world

The situation

A settlement export carries a sequence number per row. A gate alerts when len(rows) - longest in-order chain is above zero. Upstream retries re-send a row with the same number.

What actually breaks

For [1, 2, 2, 3, 3, 4] the strict chain is 4, so the gate reports 2 out-of-order rows; the non-decreasing chain is 6, so the truth is 0. A real file with 120 retry duplicates raised 120 false alarms nightly and the team ignored it.

What you'd do on Monday

Write the contract down (duplicates allowed) and pass that comparison into your chain routine.

Python
longest = your_chain_routine(seq, ok=lambda a, b: a <= b)

At 50,000 rows the scan is 1.25 billion pair checks, so run it only on files failing a cheap sortedness check.

Scenario B

Imagine you work at BookMyShow

50,000 event titles

The numbers

Deduplicate 50,000 titles of about 40 characters. A pair needs a 41 x 41 = 1,681-cell table. All pairs: 50,000 x 49,999 / 2 = 1.25 x 10^9 pairs x 1,681 = 2.1 x 10^12 cells. At an assumed 2.5M cells/s that is 840,000 s, about 9.7 days. Blocking by city and date into groups of 25: 2,000 groups x (25 x 24 / 2 = 300) = 600,000 pairs x 1,681 = 1.0 x 10^9 cells, about 400 s.

What the Scenario-A answer does here

The Monday fix, writing the contract and testing empty boundaries, still works. What fails is the pair count, not the table per pair.

What flips at this scale

Cut pairs before the DP. A cheap blocking key (city plus date) shrinks candidates about 2,000x, so the table confirms rather than searches.

The trade-off you'd defend

I would defend blocking plus a table over all pairs, trading some recall (a mistyped city never meets its twin) for a job that finishes in minutes.

Illustrative; title count, length, block size and 2.5M cells/s are assumptions, not BookMyShow-published.

Gotchas

Strict versus non-decreasing

Symptom

No allowed predecessors for [2, 2, 2], so chains stay at length 1 instead of 3.

Cause

< excludes equal neighbours.

Fix

State the contract, then use <= for non-decreasing (minimal example).

Substring answer for a subsequence question

Symptom

Run of 2 where the chain with gaps is 3 ([5, 1, 6, 2, 7]).

Cause

A running counter finds contiguous runs only.

Fix

Use the ending-position state when skipping is allowed.

PythonContiguous run versus chain with gapsruns
def run_len(xs):
    r = best = 0
    for i, x in enumerate(xs):
        r = r + 1 if i and xs[i - 1] < x else 1
        best = max(best, r)
    return best

print(run_len([5, 1, 6, 2, 7]), run_len([]))
Output
2 0

Reconstruction is not unique

Symptom

Two correct implementations print different items of the same length (up versus left in the production output).

Cause

When two moves tie, the tie rule picks one.

Fix

Specify the tie rule, or compare lengths only.

Tricky questions

"Common sequence and common substring are the same."
Most people say

They are interchangeable.

Actually

ORDER-17 and ORD-71 share a subsequence of 5 (ORD-1) but a common substring of only 3 (ORD). Substring needs contiguity and resets to zero on mismatch.

Scenario question

You're handed a diff tool that is right on short files and slow on 100,000-line files. What do you ask first?

Model answer

I ask what the output is: a length, a score or aligned lines. The table is 10^10 cells, so I strip the common prefix and suffix and anchor on stable lines. The trade-off: anchors can mis-align moved blocks; I accept that for a job that finishes.

Interview corner

CommonHow do you recognise a subsequence DP?
“I check that order is kept but skipping is allowed, then choose the state: ending at i for one sequence, a prefix pair for two.”
TrickWhat changes between strict and non-decreasing?
“I'd say only the comparison changes, but the answer can change completely on equal values, so I confirm the rule first.”
Experience checkWhere have you needed sequence comparison in a data job?
“I compared two exports for inserted rows with a sort-merge on keys, and would build a table only when rows had no stable key.”

Memory hook

For one row of stones ask "longest path ending here"; for two paths walk both, and zero stones is legal.

If you remember only one thing:

Pin the contract first (subsequence, strict, length or witness); the state and empty boundary follow.

Self-check

  1. Why is the ending-position scan O(n squared)?

    n states, each scanning up to n earlier positions.

  2. What do row 0 and column 0 of the prefix table represent?

    Empty prefixes.

  3. Does the tails array rebuild the chain?

    Not from the tails array alone; it needs extra predecessor bookkeeping.

Prove it

Run prefix_grid on ten string pairs, including an empty string and two equal strings, and paste the grid shapes. Then write cell for one contract and check two pairs by hand.

dsa-07-06Card 6 of 6

Space optimization without losing dependencies

HardP4 · DifferentiatorTalk about it8 min
dpspace-optimizationrolling-rowdiagonaltraversal-direction

Why you care

A 2D table that fits a laptop test can need gigabytes in production, and the job dies in an OOM kill with no audit row. Compression is valid only if every value the next cell reads is still available, so "use one row" cannot be memorised. Interviewers ask it to separate understanding from recalled loops.

Explain like I'm 5

You copy numbers by hand on one sheet. Each new number depends on the one above, the one to its left you just wrote, and the one above-left. Write over the sheet and the old above-left number is gone, so you jot it in the margin first.

Core concept

  1. List what each cell reads. The prefix-pair table reads up, left and diagonal.
  2. Find the oldest row read. Only the previous row means one row plus saved values.
  3. Check availability before overwriting. A write destroys the old value; if a later cell needs it (the diagonal), save it first.
  4. Choose direction from the dependency. Reading the previous row's smaller indices: high to low. Reading the current row: low to high.
  5. Report both costs: O(n x m) cells become O(min(n, m)). Time is unchanged.
  6. Reconstruction: a rolling row loses the path. Length-only is fine; the items need stored directions or a second pass. If the table fits, skip compression.

Under the hood

Measured with tracemalloc on 3.12.4, per million cells: 40.9 MB for distinct ints above 256, 31.9 MB for the mod-1009 table above, 8.9 MB if all stay at or below 256; a one-row version with 1,000 columns peaks near 34 KB. Time: 0.50 s full, 0.41 s one row.

Minimal example Save the diagonal before overwriting

PythonOne row, with and without the saved diagonalruns
def rolling(n, m, f, keep_diag=True):
    row = [0] * (m + 1)
    for _ in range(n):
        diag = 0                          # old row[j-1] = t[i-1][j-1]
        for j in range(1, m + 1):
            up, left = row[j], row[j - 1]
            row[j] = f(up, left, diag if keep_diag else left)
            diag = up                     # old up becomes the next diagonal
    return row[m]

f = lambda u, l, d: (u + 2 * l + 3 * d + 1) % 1009
print(rolling(4, 5, f), rolling(4, 5, f, keep_diag=False))
Output
774 578

The full table also gives 774.

In production Rolling row, checked against the full table

PythonSame abstract recurrence, one row, verified on edge casesruns
import tracemalloc

def grid(n, m, f):
    t = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            t[i][j] = f(t[i - 1][j], t[i][j - 1], t[i - 1][j - 1])
    return t[n][m]

def rolling(n, m, f):
    """Same recurrence in one row of min(n, m) + 1 cells. Value only: no path survives."""
    if n < 0 or m < 0:
        raise ValueError("lengths must be >= 0")
    if m > n:                             # transpose: up and left swap roles, so swap them in f
        n, m, g = m, n, f
        f = lambda u, l, d: g(l, u, d)
    row = [0] * (m + 1)
    for _ in range(n):
        diag = 0                          # t[i-1][j-1], saved before row[j-1] changes
        for j in range(1, m + 1):
            up, left = row[j], row[j - 1]
            row[j] = f(up, left, diag)
            diag = up
    return row[m]

def peak(fn, *args):
    tracemalloc.start()
    fn(*args)
    p = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    return p

fs = {"mixes all three": lambda u, l, d: (u + 2 * l + 3 * d + 1) % 1009,
      "ignores diag": lambda u, l, d: (u + 2 * l + 1) % 1009,
      "all equal inputs": lambda u, l, d: 7}
for name, f in fs.items():
    print(name, all(grid(n, m, f) == rolling(n, m, f) for n in range(7) for m in range(7)))
f = fs["mixes all three"]
print(grid(0, 5, f), rolling(0, 5, f), rolling(0, 0, f))
try:
    rolling(-1, 2, f)
except ValueError as e:
    print("ValueError:", e)
print(grid(300, 300, f) == rolling(300, 300, f), peak(rolling, 300, 300, f) < peak(grid, 300, 300, f) / 20)
print(301 * 301, "cells vs", 301, "row cells")
Output
mixes all three True
ignores diag True
all equal inputs True
0 0 0
ValueError: lengths must be >= 0
True True
90601 cells vs 301 row cells

See it happen Why the diagonal needs a margin note

single row while computing table row 202147
  1. At the start of row 2 the array still holds row 1 of the table: 0, 1, 3, 7.
  2. Column 1: up is 1, left is 0 and the saved diagonal is 0; the cell becomes 2 and the old 1 is kept aside as the next diagonal.
  3. Column 2 uses up 3, left 2 and the saved diagonal 1, so it becomes 3 + 4 + 3 + 1 = 11.
  4. Without the saved diagonal, column 2 would read the overwritten 2 instead of 1 and compute 14, not 11.
Notice: The overwritten cell is the one the next cell needs, so save it before the write.
Scenario A

In your world

The situation

A Jenkins stage diffs two settlement extracts to decide whether to skip a reload, using the full (n+1) x (m+1) table. The dev fixture has 1,500 lines per side; production extracts have 25,000. The agent has 2 GB.

What actually breaks

1,500 x 1,500 = 2.25 million cells, about 70-90 MB at 32-41 B/cell: fine. 25,000 x 25,000 = 6.25 x 10^8 cells, about 20-26 GB. The OOM killer ends the stage with exit code 137 and no audit row is written.

What you'd do on Monday

The gate needs only the length, so use the one-row version: 25,001 cells, about 1 MB. Time is still 6.25 x 10^8 cells, 250 s at an assumed 2.5M cells/s, so trim shared prefix and suffix first.

Python
score = rolling(len(a_lines), len(b_lines), your_cell_rule)
similar = score >= 0.98 * max(len(a_lines), len(b_lines))
Scenario B

Imagine you work at Figma

30,000-layer document versions

The numbers

Two versions with 30,000 layers each: 30,001 x 30,001 = 9.0 x 10^8 cells. A full table at 32-41 B/cell is 29-37 GB; one row is about 1.2 MB. At an assumed 2.5M cells/s, time is 9.0 x 10^8 / 2.5 x 10^6 = 360 s either way. Fifty an hour: 50 x 360 s = 5 CPU-hours per hour.

What the Scenario-A answer does here

The Monday fix, a rolling row for a length-only check, still solves memory. It does not fix time or say which layers moved: running it on every save is five CPU-hours per hour.

What flips at this scale

Compression changes memory, not work, so cut the work: skip when hashes match, trim the common prefix and suffix, and run the table on the changed middle only. Reconstruct moves on demand.

The trade-off you'd defend

I would defend trim plus a rolling-row score over a full table per save, trading default aligned output for far less memory and time.

Illustrative; layer count, comparison rate and 2.5M cells/s are assumptions, not Figma-published. Per-cell bytes (8.9, 31.9, 40.9 B) and 0.4-0.5 s per million cells were measured on CPython 3.12.4.

Gotchas

Lost diagonal

Symptom

Result 578 where the full table gives 774 (keep_diag=False above).

Cause

The in-place write destroyed the value the next cell reads as its diagonal.

Fix

Save up into diag before moving on, as in the minimal example.

Wrong direction after collapsing an axis

Symptom

Totals that need more copies than exist.

Cause

An ascending pass reads values already updated for this item.

Fix

Choose direction from what each cell reads; compare with the uncompressed version.

PythonAscending pass turns once-only into reusableruns
def totals(costs, budget, descending):
    ok = [True] + [False] * budget
    for c in costs:
        order = range(budget, c - 1, -1) if descending else range(c, budget + 1)
        for b in order:
            ok[b] = ok[b] or ok[b - c]
    return [b for b in range(budget + 1) if ok[b]]

print(totals([3], 9, True), totals([3], 9, False))
Output
[0, 3] [0, 3, 6, 9]

No path after compression

Symptom

The caller needs aligned items and receives only a number.

Cause

A rolling row keeps no history of choices.

Fix

Decide the contract first; keep the table for small inputs.

Tricky questions

"Two rows are always enough."
Most people say

Rolling arrays work for every DP.

Actually

Only if each cell reads at most the previous row; a recurrence reaching further back needs more rows.

Scenario question

A 2D version runs out of memory on large input and a colleague says "just keep the last row". Respond.

Model answer

I ask what the output is. For a score, I list what each cell reads (up, left, diagonal), keep one row plus a saved diagonal, and verify against the full table on small inputs including empty ones. The trade-off: I lose the aligned items and gain no time, so if items are needed I keep the full table for small inputs.

Interview corner

CommonHow do you reduce a 2D DP to 1D?
“I'd list what each cell reads, confirm it needs only the previous row, then update in place with a safe traversal order and saved variables for old values still needed.”
TrickWhat breaks if you forget the saved diagonal?
“I'd explain that the in-place write destroys the previous row's value at the left column, so the next cell reads a new value as old. On a 4 x 5 example it gave 578 instead of 774.”
DesignA caller needs a score and aligned rows for 30,000-row inputs. What do you build?
“I'd score with a rolling row after trimming the common prefix and suffix, and reconstruct on request on the trimmed middle, stating each path's cost.”

Memory hook

One sheet of paper works only if you jot the above-left number in the margin before writing over it.

If you remember only one thing:

Before overwriting a cell, check that no later cell still needs its old value, and remember time does not shrink.

Self-check

  1. What does a one-row prefix-pair table need besides the row?

    A saved copy of the previous row's value to the left (the diagonal).

  2. Does space compression change time complexity?

    No. The number of cell updates is the same.

  3. What is lost when you keep one row?

    The path, so aligned items cannot be rebuilt from it.

Prove it

Run the production block and paste its output. Then replace diag in the call with row[j - 1], rerun the first three lines and paste which functions now disagree.