An exact median over a 40 GB file cannot be answered from summaries of pieces, but a total can — why?
answer
- does a combine step exist
- can an unread record still move it
- fixed state, or state per distinct value
- seeing everything is not holding everything
basics
~20 sA total is determined by the records already read, but an exact median is not: a record still unread can move the middle value. Only the total has a combine step that absorbs whatever arrives later.
solid answer
~50 sRunning a job over a bounded input a piece of rows at a time works only when a **combine step** exists — a function that takes the state from the records read so far and the state from the rest and yields exactly the answer you would have got by reading everything at once. A total has one: add the two partial totals. An exact median has none over fixed-size state, because which value sits at the middle position depends on how many records fall on each side of it, and no prefix of the input settles that. Read 39 of 40 gigabytes and the last gigabyte can still displace the middle. The test is not "is this expensive" but "can a record I have not read yet still change the answer, and is there a bounded summary that absorbs it".
go deeper
Recall the test: can a record you have not read yet still change the answer? A total says no, an exact median says yes. Be able to give one example of each.
Explain the combine step by mechanism — what the carried state holds, and why combining two partial totals is exact while combining two partial medians is not. Say what the state is proportional to.
Show that "must see every record" does not imply "must hold every record", and move straight to what buying that reach costs. Diagnose a job by naming what its carried state grows with.
Frame it as a commitment: whether a figure is required to be exact decides the whole execution shape of the job, and that decision is cheapest before the pipeline is written rather than after someone reconciles the number.
## What "answerable from pieces" actually means A computation over a large input can be run a piece of rows at a time — read a portion, fold it into some carried state, discard the portion, read the next — **only if a combine step exists**. A combine step is a function that takes the state accumulated from the records read so far and the state accumulated from all the rest, and produces exactly the answer you would have got by reading everything at once. Where that function exists, the size of the carried state is what decides whether the job survives, and it is often tiny: a running total is one number, a running extremum is one value. An exact median has no such function over fixed-size state. The value you want occupies the middle position once the values are placed in order, and which value occupies that position is decided by **how many records fall on each side of it** — a quantity no prefix of the input can settle. An exact count of distinct identifiers has the same problem from the other direction: to decide whether the identifier in front of you is new, you must be able to consult every identifier already seen, so the carried state grows with the number of distinct values instead of staying fixed. Putting the whole input in order, and removing repeats across the whole input, show the property in its starkest form — neither can emit its first output record until the last input record has been read. ## The property, stated once > **A record you have not read yet can still change the answer, and no fixed-size summary of the records already read is enough to absorb it.** That one sentence is what the question is testing. It is not "the operation is slow" and it is not "the dataset is big". Both of those can be true of a plain total, which is perfectly happy a piece at a time. | Operation | What one piece can contribute | Why a later record can still change it | |---|---|---| | Total, count, extremum | A complete partial answer of fixed size | It cannot — the combine step absorbs whatever arrives later | | Exact distinct count | The set of values that piece saw | A value in a later piece may or may not already be in that set | | Exact median | Nothing of fixed size | The middle position shifts as records land on either side of it | | Whole-input ordering or de-duplication | Nothing final | The first output is undecided until the last input is read | ## "Must see everything" is not "must hold everything" The common overcorrection is to hear "it has to see every record" and conclude "so it has to hold every record in memory at once". It does not. It only has to be able to **reach** every record, and there are established ways to buy that reach without holding the input resident: read the input more than once, or accept an answer that carries a stated error bound instead of an exact one. Each of those charges something. Naming the property is the first half of the subject; knowing which charge a given requirement permits is the second. ## Where designs genuinely differ Two sentences that sound like laws hold only for some designs, and saying which is the difference between a candidate who has read one manual and one who understands the model. - **"Processing in pieces bounds the memory."** True where the carried state is fixed in size — a total, a count, a running extremum, a variance carried as three numbers. False where the state is keyed by values in the data: one entry per distinct key, multiplied by however many distinct keys the data turns out to hold, can reach the size of the whole in-memory computation. The piece size bounds the piece and bounds nothing else. - **"If it does not fit, you have to rewrite the job as a hand-written loop over pieces with your own combine step."** True of a fully in-memory model, where the entire dataset must be resident before any operation runs, so shredding the job by hand is the author's only move. False where the tool's own execution can work through the input a portion at a time and hold intermediates on this machine's disk: there the expression the author wrote is unchanged, and what is left to reason about is exactly the operations that still have no combine step. ## What the interviewer is listening for A strong answer names the combine step, shows one operation that has one and one that does not, says what the carried state is proportional to in each case, and then declines to conclude that the job is impossible. It is not impossible. It costs something, and the honest follow-up is always which cost you are willing to pay.
- The carried state for an exact distinct count is not fixed in size — what is it proportional to, and why does that make the piece size irrelevant?It is proportional to the number of **distinct** values seen, not to the number of records. Every new value must be retained so the next occurrence can be recognised as a repeat. Shrinking the piece bounds how much input is resident at once, but the retained set of distinct values survives every piece boundary, so it keeps growing regardless.
- Does an exact minimum over a column that also has absent cells still have a combine step?Yes. The combine step is still "take the smaller of the two partials", and absence only changes what a piece contributes: a piece whose values are all absent yields no candidate rather than a wrong one. The state stays one value plus a flag for "nothing seen yet".
- Why is "it takes a long time" not evidence that an operation cannot be answered from pieces?Runtime and carried state are separate axes. Summing a trillion numbers takes a long time and still needs one accumulator; an exact distinct count over a much smaller input may finish quickly and still retain every distinct value. The question is whether a later record can invalidate a fixed-size partial answer, not how long the traversal takes.
At any moment during a road race you can state exactly how many runners have finished, because each arrival just increments a counter. You cannot state who the middle-placed finisher is until the last runner crosses, because anyone still on the course changes which place is the middle one.
saying these in an interview costs you the question
- Says the operation is simply impossible without more machines
- Claims processing in pieces always bounds memory, whatever is being computed
- Treats "needs every record" as identical to "needs every record in memory"
- Says the difference is that the median is a harder calculation
- Assumes the average of each piece's median approximates the real median