In frequency top-50 over 10 million distinct terms, where does the memory actually go?
answer
- Cost the two phases separately
- How many entries live in each structure?
- Fifty against ten million
- The heap is not the expensive half
- Exact ranking forces every distinct key resident
basics
~20 sAlmost all of it goes to the counting phase. Ranking terms by frequency needs a count for every one of the 10 million distinct terms held at once; the size-50 heap adds fifty entries. The heap bounds the output, not the memory.
solid answer
~50 sThe pattern is two phases and only one of them is expensive. Phase one walks the event stream once and builds a term-to-count structure: `O(N)` time in the number of events, and memory proportional to `D`, the number of *distinct* terms — 10 million entries here. Phase two walks those D counted entries through a size-50 min-heap keyed on count: `O(D log k)` time and `O(k)` resident. Totals are `O(N + D log k)` time and `Θ(D + k)` memory, which is `Θ(D)` — fifty heap slots are invisible beside ten million counters. So the common claim "the heap makes this O(k) memory" is wrong: bounded output does not mean bounded state. If the footprint is a problem, the lever is the counting structure — key encoding, counter width, or negotiating away exactness — never the heap.
go deeper
Recall the two phases in order: count every distinct term once, then push the counted entries through a size-k heap ordered on count. Say which structure holds what.
Cost each phase on its own — counting is linear in the number of events and holds one entry per distinct term, while the selection pass is O(D log k) with only k entries resident.
Diagnose where the budget actually goes: ten million counters dwarf fifty heap slots, so tuning the heap is premature and the counting structure's per-entry footprint is the thing to attack.
Own the exactness negotiation. An exact frequency ranking requires every distinct key to be resident at once, so if that does not fit the budget, the real decision is which approximation the product is willing to publish.
## Two phases, two very different bills Ranking things by how often they occur — trending terms, hottest error signatures, most-requested identifiers — is the composition question interviewers use to see whether a candidate can cost a *pipeline* rather than an algorithm. It decomposes into: 1. **Count.** One pass over the N raw events, incrementing a counter per term in a lookup structure keyed by term. 2. **Select.** One pass over the D distinct counted entries, feeding each into a size-k min-heap ordered by count, keeping an entry only when its count beats the root's. Write the bill for each phase separately, because they are wildly asymmetric. | phase | time | resident state | |---|---|---| | count | O(N) expected, hashing per event | Θ(D) — one entry per distinct term | | select | O(D log k), most entries one comparison | Θ(k) | | total | O(N + D log k) | Θ(D + k) = Θ(D) | With D = 10^7 and k = 50, the heap is 0.0005% of the entries in play. Whatever the memory problem is, the heap is not it. ## Why "the heap bounds memory" is the wrong instinct The size-k heap genuinely bounds memory *when the thing being ranked is the raw values themselves* — then each value is judged on arrival and discarded forever. Frequency ranking breaks that property, because a term's rank is not a property of any single event. You cannot decide whether a term belongs in the top 50 until you know its final count, and you do not know its final count until the stream ends. So exact frequency ranking is inherently two-phase, and phase one has to remember every distinct key. That is the structural point worth saying out loud: **bounded output is not bounded state.** The heap caps what you emit, not what you must retain to compute it. ## Why you cannot run the heap while counting The natural "optimisation" — push each term into the size-50 heap as its count changes — is wrong in two directions at once. - **Stale keys.** An entry sitting in the heap has its count incremented later, but the heap ordered itself using the old value. The structure's invariant is now false, and the root no longer identifies the weakest member. - **Premature eviction.** A term evicted at minute one because it had two occurrences may end the hour with a million. Once evicted, nothing brings it back, and the answer is silently wrong. Only *final* counts are comparable, so the selection pass has to come after counting is finished, or after a window is sealed. ## The levers that actually exist If Θ(D) does not fit the budget, these are the real options, and they are all about phase one: - **Shrink the entry.** The dominant cost is per-entry overhead multiplied by ten million: the key bytes, the counter width, and the per-slot bookkeeping of the lookup structure. Compact key encoding and a right-sized counter are pure wins with no correctness cost. - **Shrink D honestly.** Canonicalise before counting — case folding, normalisation, trimming — so that variants collapse into one entry instead of five. This is a definitional change, and it must be agreed with whoever consumes the ranking. - **Shrink D dishonestly, on purpose.** Discarding terms whose running count stays below a threshold caps memory but makes the result *approximate*: a term that accumulates slowly and steadily can be dropped early and never counted again. That may be perfectly acceptable — say so explicitly, and never present the output as exact afterwards. What is *not* a lever: tuning the heap. Halving the cost of fifty entries buys nothing, and the selection pass's O(D log k) has log2(50) ≈ 5.6 as its multiplier, with the guard reducing most of the ten million entries to a single comparison anyway. Counting's hashing over N events is the dominant time cost. ## Determinism at the bar One more production detail: counts tie constantly in the tail, and the boundary of a top-50 list is exactly where the tail lives. The guard keeps a newcomer only when it strictly beats the root, so whichever term arrived first wins — and iteration order over the counted entries is not something you should assume is stable. If the ranking is user-visible and must be reproducible run to run, order on the pair (count, term) with an explicit total-order tiebreak, rather than relying on how the entries happen to be enumerated. ## The summary to give "Time is O(N) for counting plus O(D log 50) for selection; memory is Θ(D). The heap is the cheap half. If we have a memory problem it is the ten million counters, and fixing it means either shrinking each entry or accepting an approximate answer — I would want to know which the product can live with before I pick." That answer shows you costed the composition rather than reciting the pattern.
- Why not maintain the size-50 heap while the counts are still being incremented?Because a term's rank is not final until the stream is. Entries already in the heap have their counts grow underneath the ordering, so the root stops identifying the weakest member; and a term evicted early can later exceed the bar with no way back in. Only final counts are comparable, so selection has to follow a sealed counting phase.
- How does the selection pass's time compare with the counting pass's?Selection is O(D log k) with log2(50) ≈ 5.6, and the guard reduces most of the ten million counted entries to a single failed comparison. Counting is O(N) over every raw event with a hash per event. Unless events barely outnumber distinct terms, counting dominates, which is another reason tuning the heap is premature.
- The ranking must be identical across reruns of the same data. What do you change?Order on an explicit pair rather than on count alone — count first, then a total order on the term itself. Otherwise ties at the boundary are resolved by whichever entry was enumerated first, and enumeration order over the counted entries is not something to rely on. The tiebreak costs nothing and makes the output reproducible.
Counting is a census of everyone in the city; the heap is a podium with fifty places. The podium costs nothing — the census is what fills the building.
saying these in an interview costs you the question
- Says memory is O(k) because the heap holds only k
- Optimizes the heap while ten million counters dominate
- Drops rare terms early and still calls the result exact
- Maintains the heap over counts that are still changing
- Confuses the distinct-term count with the event count