A batch job runs out of memory filling a DP table over two 100,000-element sequences — what do you change?
answer
- count the cells before blaming the allocator
- ten to the fifth squared is ten to the tenth
- which rows does the transition still read
- two rows is two hundred thousand cells
- memory fixed, running time untouched
basics
~20 sTen billion cells is the problem, not the allocator. Keep only the rows the transition still reads — two rows is 200,000 cells — and the job fits. That fixes memory alone; ten billion cell computations still cost the same time.
solid answer
~50 sFirst do the arithmetic out loud: 10^5 by 10^5 is 10^10 cells, which at four bytes each is roughly 40 GB. No heap setting saves that, so the fix is structural. If the transition reads only the row behind it, keep two rows — 2 × 10^5 cells, well under a megabyte — and the memory failure disappears entirely. Before doing it, confirm what the job actually consumes: if it needs only the final value, rolling is free; if it has to report which choices produced that value, dropping the rows destroys exactly the evidence it needs, and that is a different design conversation. And be honest about what is *not* fixed: the same 10^10 cells still get computed, so at best you are looking at tens of seconds and realistically minutes. Memory and time are separate levers here.
go deeper
Recall that a DP table's size is the product of its two dimensions, and that 100,000 by 100,000 is ten billion cells. Knowing that number is not a tuning problem is the point.
Explain the fix mechanically: identify the recurrence's look-back depth, keep that many rows plus one, swap references each outer step. Be able to state the new resident cell count.
Sequence the diagnosis — count cells, name the structural fix, confirm nothing downstream reads the discarded rows — and then separate the memory result from the time budget out loud. Rejecting disk spilling with a reason belongs here too.
Own the framing that memory and time are different levers with different owners. Decide whether an exact answer at this input size is a requirement at all, and whether bounding the input is a cheaper contract change than rewriting the algorithm.
## Count cells before you touch configuration The instinct on an out-of-memory failure is to reach for a bigger allocation. Resist it long enough to multiply the table's dimensions. Two 100,000-element inputs give a grid of 10^5 × 10^5 = 10^10 cells. At four bytes per cell that is about 40 GB; at eight, about 80 GB. This is not a tuning problem — no realistic machine setting makes a 40 GB table appear, and even if one did, the job would spend its life fighting the memory hierarchy. Counting cells turns a vague failure into a number you can reason about, and it immediately tells you whether the fix is a setting, a structural change, or a different algorithm. ## The structural fix If the recurrence writes row `i` using only row `i-1`, the entire grid never needs to exist. Hold two rows, fill one from the other, swap the references each outer step. That is 2 × 10^5 cells, under a megabyte, and the memory failure is gone by a factor of a hundred thousand rather than by a factor of two. This is why cell counting matters: the answer is not "reduce memory somewhat" but "the resident set was never supposed to be quadratic in the first place". Before doing it, ask what consumes the result. If the job reports a single number, rolling costs nothing. If it must report *which* choices produced that number, the discarded rows were the evidence for that walk-back and the compression is not available for free — that is a separate design decision with its own options, not a detail to discover after the change ships. ## What rolling does not fix This is the part that separates a senior answer. Rolling changes storage, never work. All 10^10 cells are still computed. Even at a very optimistic 10^9 simple cell updates per second, that is around ten seconds of pure computation; with a branchy transition and real data movement, minutes is the honest expectation, and slower is common. So if the job was failing on memory, rolling fixes it; if the job is *also* outside its time budget, rolling has bought nothing at all, and you now need a different lever: - **Fewer states.** Restrict the grid to the band of cells that can plausibly matter and skip the rest. This changes the algorithm's shape and needs a correctness argument, but it is the only lever that attacks the 10^10. - **Smaller inputs.** Chunk, sample, or bound the sequences by a product-level rule. Often the real finding is that nobody actually needs an exact result over 10^5 × 10^5. - **A different method.** Accept an approximate or heuristic answer whose cost is closer to linear. ## What does not work Spilling the table to disk is the classic wrong turn. It converts an allocation failure into a job that runs for hours against storage, because 10^10 cells is far past the point where paging is a rescue. And the access pattern gives it away: the fill touches each row once, in order, which is precisely the pattern that says *do not materialize the rows*, rather than *write the rows somewhere slower*. Compressing the cell type is a real but limited lever. If cells hold a small bounded quantity, a narrower cell type shrinks the table by a constant factor. On a 40 GB table a factor of two or four does not reach a machine's memory, so treat it as a supplement to rolling, never a substitute. ## How to present the diagnosis A good answer sequences the reasoning: measure or compute the table size; state the number; identify the recurrence's look-back depth; propose the resident-row count that follows from it; confirm nothing downstream reads the discarded rows; then, separately, state what the change does not address and what the time budget looks like afterward. That sequencing is the actual skill being tested. The failure mode interviewers listen for is a candidate who jumps to "increase the memory limit" or "stream it to disk" without ever multiplying two numbers together. ## Two rows or one array At this scale, do not bother squeezing two rows into one. The difference is 2 × 10^5 versus 10^5 cells — noise against the original problem — while the one-array form imposes a sweep-order proof obligation that a future maintainer can silently break. Take the hundred-thousand-fold win and leave the factor of two on the table.
- After rolling, the job fits but now takes hours. What now?Rolling never touched the work, so the 10^10 cell computations are exactly where they were. The lever has to reduce states or input: restrict the fill to a band of cells that can plausibly matter and justify skipping the rest, chunk or bound the sequences by a product rule, or accept an approximate method with near-linear cost. Confirm first that an exact result at that size is genuinely required — often it is not.
- Would spilling the table to disk be a reasonable alternative?No. It converts an allocation failure into a job that grinds for hours, because 10^10 cells is far past the size where paging helps. The access pattern actually argues the other way: each row is touched once in order, which is the signal not to materialize rows at all. Streaming to storage is a fix for data you must keep, and here you must not keep it.
- Two rows or one array at this scale?Two rows. Going further buys a factor of two — 10^5 cells instead of 2 × 10^5 — which is noise once the resident set is already under a megabyte, and it costs a sweep-order proof obligation that a later cleanup can silently break. Take the hundred-thousand-fold win and skip the fragile constant-factor one.
saying these in an interview costs you the question
- Raises the memory limit instead of counting cells
- Claims rolling arrays also fix the running time
- Thinks spilling to disk makes ten billion cells workable
- Rolls the table without checking what reads it
- Treats a narrower cell type as a substitute for rolling