An exact median over a column that will not fit is computed in two traversals of the input. What does the first traversal buy?
answer
- fixed-size counters, then a narrow slice
- the summary chooses what the second read keeps
- the offset is known, so nothing is rescanned
- re-readable and unchanged, or silently wrong
basics
~20 sThe first traversal computes a small fixed-size summary — counts per value range — identifying the one narrow range that holds the answer. The second traversal retains only that range, which fits, so an exact answer comes from a bounded footprint.
solid answer
~50 sThe first traversal never retains a record. It folds each value into a counter for the range it falls in, so its state is one small array whatever the input size. From those counts you can say exactly which range contains the middle-positioned value, and exactly how many records lie below that range. The second traversal reads the input again and keeps only the values inside that one range — a small fraction of the input, which fits — and the answer is found at a known offset inside it, because the count of everything below is already known. What this buys is **exactness with a bounded footprint**. What it charges is one extra read of the whole input, and two preconditions: the input must be re-readable at all, and unchanged between the reads, or the first traversal's counts no longer describe what the second one sees.
code
pseudocode · 24 lines# traversal 1: state is one counter per value range, fixed in size
counts = new array of zeros, one entry per range
total = 0
for record in read_input():
counts[range_of(record.amount)] += 1
total += 1
# choose the range holding the middle-positioned value
target = total / 2 # 0-indexed position we want
cum = 0 # records lying entirely below the chosen range
for r in ranges_in_order:
if cum + counts[r] > target:
chosen = r
break
cum += counts[r]
# traversal 2: retain only the values inside the chosen range
kept = new empty list
for record in read_input(): # the input is read again
if range_of(record.amount) == chosen:
kept.append(record.amount)
put kept in ascending order # small enough to hold
answer = kept[target - cum]go deeper
Recall the shape: one cheap read that counts, then a second read that keeps only the narrow part that matters. The answer stays exact.
Explain why the first traversal's state is fixed in size regardless of the data, and how the offset in the second traversal is derived without rescanning.
Bring the failure modes unprompted: concentrated values leaving the chosen range too large, and an input that changes between the two reads and produces a wrong answer with no error raised.
Weigh the standing cost of two hand-written steps that must agree about their range boundaries against simply renting a machine with enough memory to avoid the technique entirely.
## The shape of the technique The third escape from an operation whose answer a later record can still change is the one people rediscover rather than learn. Instead of holding the data, or accepting an error bound, you spend **one extra traversal of the input** to make the work of the next traversal small enough to hold. It has three parts: 1. **A first traversal with fixed-size state.** Each value is folded into a counter for the range it falls in. Nothing is retained, nothing is written out, and the state is one small array of counters no matter how large the input is. 2. **An arithmetic step in between.** Walking the counters in order and accumulating them tells you which range contains the value at the middle position, and how many records lie entirely below that range. Both are exact, because the counters are exact. 3. **A second traversal that retains almost nothing.** Read the input again, keep only values inside the chosen range, and finish in memory. The offset inside the retained values is known from the count of everything below, so no further scanning is needed. ## Why the first traversal is cheap It is cheap for a specific reason worth naming: the state does not depend on the data. A counter per range is fixed in size, so it does not matter whether the column holds ten distinct values or a billion. That is precisely the property the original computation lacked — and the technique works by putting a computation that *does* have it in front of one that does not. ## What it charges | Charge | Detail | |---|---| | One extra read of the input | The input is read twice; the second read is usually cheaper, since it retains almost nothing, but it is not free | | A re-readable input | A feed that can be consumed only once forecloses the technique entirely | | An unchanged input | If records arrive or change between the reads, the first traversal's counts no longer describe what the second sees, and the answer is silently wrong | | A guess at the ranges | Range boundaries are chosen before the data is seen; a bad choice can leave one range still too large to retain | ## When it fails, and what you do about it The honest failure is **concentration**. If the values cluster inside one range, the chosen range may still hold most of the input, and the second traversal will not fit either. Two responses, and the first is usually right: - Apply the technique again to that range alone, with finer boundaries inside it — a third traversal, exact, still bounded. Each repetition narrows the survivors sharply. - Choose the boundaries from something you already know about the distribution: the bounds of the column and a rough sense of its shape, gathered in the same first traversal, cost nothing extra to collect. The second real failure is the **mutating input**, and it is worse because nothing raises an error. The two traversals see different data, the counts and the retained slice disagree, and the answer that comes out is wrong by an amount nobody can bound. If the input can change, either snapshot it first or abandon this escape. ## How this differs from the other two escapes It is easy to file all three under "read it more than once", and they are not the same trade. - A **spilled multi-pass run** keeps exactness by letting the execution write intermediates to this machine's disk and read them back. It charges storage as well as reads, and in many designs it is the tool's job rather than the author's — the expression is unchanged. - A **bounded-error answer** keeps a single traversal and a constant footprint and charges exactness itself, which is a decision about the figure rather than about the machine. - The **cheap first traversal** writes nothing, keeps exactness, and charges only reads. It is always the author's own code, in two steps, and that is its real cost — someone has to maintain two steps that must agree about the range boundaries. ## What an interviewer is listening for The candidate who has only heard of the technique says "you do two passes". The candidate who has used it says what the first traversal's state is proportional to, how the offset in the second is computed without rescanning, what happens when the values are concentrated, and what goes wrong when the input moves underneath the two reads. That last one is the question behind the question.
- The values turn out to be concentrated, and the chosen range still holds 70% of the input. What now?Apply the same technique to that range alone with finer boundaries inside it — a third traversal, still exact, still bounded, and each repetition narrows the survivors sharply. Better, collect the column's bounds and a rough sense of its shape during the first traversal, which costs nothing extra, and choose boundaries from that instead of guessing.
- Records are appended to the input between the two traversals. What goes wrong, and would anything tell you?The counts from the first traversal no longer describe what the second one reads, so the offset into the retained values points at the wrong element. Nothing raises an error: a plausible value is returned and it is wrong by an unbounded amount. Either snapshot the input first, or choose a different escape.
- Why does the second traversal not need to scan the values it keeps in order to find the answer?Because the count of everything below the chosen range is already known exactly from the first traversal. Subtracting it from the target position gives the offset inside the retained values directly, so once those are placed in order the answer is read off at that offset.
saying these in an interview costs you the question
- Believes the first traversal has to retain the values it counts
- Assumes the second read is free because the file is already on disk
- Ignores that the input must be unchanged between the two reads
- Thinks the technique gives an approximate answer
- Cannot say what the first traversal's state is proportional to