While a five-minute grouping computes a running total per key, what must the job hold, and what changes for a median?
answer
- two ways to hold an open group
- carry a value or carry the records
- do two partial values merge
- total folds, exact median keeps everything
basics
~20 sA running total needs one number per key while the group is open. A median needs every value in the group, because no single carried value can be merged into the answer. Same interval, very different memory.
solid answer
~50 sThere are only two ways to hold a group that is still open. You can **fold** each arriving record into a per-group value that already carries everything the answer needs and then discard the record — for a total, one running number — or you can **keep the records themselves** until the group is declared finished and compute the answer from all of them. A total folds: add the amount, drop the record, and two partial totals add together. A median does not: which value ends up in the middle depends on records that have not arrived yet, so every value stays. That is the whole cost difference — `one value per open group` against `every record in every open group`. Most aggregates people actually ask for fold; the ones that do not are the ones that need the group's whole distribution.
go deeper
Recall the two options for an open group: carry one value folded from the records, or keep the records themselves. Know that a running total is the first and an exact median is the second.
Explain the property that separates them — whether two partial values merge into one without growing — and show that a mean folds when carried as a total and a count.
Show the production consequence: per-group size times open groups, and that the aggregate chosen, not the boundary chosen, is often what decides whether the job fits at all.
Treat it as a requirements question. An exact median asked casually is worth challenging when an approximate one costs a constant per group and the decision it feeds tolerates the error.
## Two ways to hold a group that is open An endless input has no end of its own, so a computation over it finishes only when the author imposes a boundary — for example a boundary that cuts the input into back-to-back spans of equal length, so that every record falls in exactly one group. Between the arrival of a group's first record and the moment the group is declared finished, that group is **open**: more records for it are expected, and its answer cannot be handed downstream yet. While a group is open there are only two things the job can do with an arriving record. 1. **Fold it.** Combine the record into a single per-group value that already carries everything the final answer needs, then discard the record. A value like this is a **foldable accumulator**, and it has two properties that matter: any two of them, built over different records of the same group, merge into one; and its size does not grow with how many records have been folded into it. 2. **Keep it.** Add the record to the group's **retained record set**, and compute the answer from the whole set when the group is declared finished. Real jobs sometimes do both side by side — a folded total next to a retained set for a second output that genuinely needs the records — but there is no third mechanism. ## Why a total folds and a median does not A running total's carried value is one number. When a record arrives you add its amount, and the record is then worthless to the answer: nothing about it can change the total again. Count, smallest and largest behave the same way. A mean behaves the same way too, once you carry a total **and** a count as a pair rather than carrying the average itself. A median is different in kind. The middle value is a property of the whole set's shape, and which record turns out to be the middle one depends on every record that arrives afterwards. There is no fixed-size value you can carry such that the next record folds into it and the exact middle is still recoverable, so every value is kept until the group closes. Exact distinct counting fails for a related reason — to know whether an arriving identifier is new, you must have kept the identifiers — and an exact top-k by frequency needs a count for every distinct key, not only for the k that end up ranked. | Computation | Carried while the group is open | Cost per open group | |---|---|---| | running total, count | one number | constant | | smallest, largest | one value | constant | | mean | a total and a count | constant | | exact median or percentile | every value in the group | grows with records | | exact distinct count | every distinct identifier | grows with distinct values | | exact top-k by frequency | a count per distinct identifier | grows with distinct values | ## The arithmetic that follows The memory a grouping costs is what one open group holds, multiplied by how many groups are open at the same time. Folding collapses the first factor to a constant. That is why the same boundary over the same input can be a job that runs comfortably or a job that cannot be made to fit: the difference is the aggregate, not the interval. What a runtime does when the total will not fit in a worker's memory, and where those bytes physically live, is a separate subject from this one. ## Where engines of this class differ The fold-or-keep distinction is universal. Three things around it are not, and an answer that states one runtime's behaviour as the model will be wrong for a candidate whose next job uses a different one: - **Where the carried value lives between records.** Where each record advances individually through long-lived operators, the accumulator sits in the operator and is updated per arrival. Where arrivals are instead collected for a short span and one finite job runs over the collected set, the accumulator is handed from one such job to the next. In the oldest model in this family — a finite pass that materialises its intermediate result to disk between phases — no group persists at all, and a windowed result is produced by re-running the pass. - **When the group's value is read out.** Some runtimes hand a value downstream once, when the group is declared finished. Others emit an early value and corrections afterwards. Others restate the group's current value on every input. A group that may still re-emit has released nothing, so output appearing is not the same event as memory falling. - **Whether your computation is recognised as foldable.** A declarative aggregate expression is usually compiled into a fold. A hand-written per-record function that appends to a collection is usually executed literally as written and folds nothing, however foldable the underlying mathematics is. ## What an interviewer is listening for Not "a median is expensive". The mechanism: name what is carried, say whether two partial values merge into one without growing, and then state the memory as a product of per-group size and open-group count. A candidate who jumps straight to giving the workers more memory has skipped the only question that was asked.
- Does a mean fold, given that an average of averages is usually wrong?Yes, provided the carried value is a total and a count rather than the average itself. Merging adds total to total and count to count, and the division happens once, when the group's value is produced. Carrying the average alone is exactly what breaks, because two averages cannot be combined without knowing how many records each covered.
- A group emits its value and memory does not fall. What happened?Emission and release are different moments. Where the runtime allows corrections, a group that has been declared finished still holds its carried value through a stated extra span, so it can accept a record that turns up afterwards and re-emit. Memory falls when the carried value is dropped, not when output appears.
A shopkeeper can keep a running till total on one slip of paper and throw each receipt away, and still answer how much the shop took today. To answer what the middle-sized sale was, every receipt has to stay in the box until closing time.
saying these in an interview costs you the question
- Assumes every aggregate can be carried as one running number.
- Says a median can be folded by carrying a running average.
- Thinks the interval's length alone decides what the grouping costs.
- Believes records are always discarded once counted, whatever the aggregate.
- Treats the memory question as answered by giving workers more memory.