What does a size-k heap commit you to on a memory-capped gateway ingesting an unbounded sensor stream?
answer
- Ask what leaves memory and never returns
- Who chooses k, and when?
- Bounded state buys the pass, costs the tail
- Can you answer a different question next quarter?
- Merging windows is exact for values, not counts
basics
~20 sA size-k heap commits you to one frozen question. Bounded state and a single pass let the job run under the cap, but every value that lost to the bar is destroyed, so a different k or metric means re-ingesting the stream.
solid answer
~40 sThe bargain is worth naming precisely. You get bounded resident state — k entries, sized before deployment — one forward pass, no spill to disk, and no dependence on knowing the stream's length. What you give up is the raw data: values that lost to the bar are gone, so the pipeline answers exactly the question it was configured for and nothing else. Raising k, adding a percentile, or redefining the metric are all re-ingest events, and on a live stream that means waiting for new data. So the decision is not heap-versus-sort; it is whether the product question is settled enough to freeze at ingest time. If it is not, buy a short rolling raw archive off the device — and that line item, not the algorithm, is what to argue about.
go deeper
Know the basic bargain: the structure keeps only k values in memory and throws every other value away permanently as it goes.
Explain what bounded state buys and costs — one forward pass, no need to know how much data is coming, no random access backwards, and no way to revisit a discarded value.
Show operational judgment: define the window, know that value results merge across windows exactly while frequency results do not, and plan for the day someone asks for a different k.
Own the commitment. You are freezing a product question at ingest time in exchange for running under a hard ceiling, so say out loud which future questions that forecloses and what a hedge would cost.
## What the cap actually buys A gateway with a hard memory ceiling and a feed that never ends is the setting where the size-k heap stops being a cleverness and becomes the only viable shape. Its properties line up exactly with the constraints: - **Θ(k) resident state**, chosen at design time and independent of how much data flows through. - **One forward pass**, so nothing is buffered and nothing spills. - **No known length** required; the structure has a correct answer for the prefix consumed so far at every instant. - **Amortised near-nothing per value**, because a value that fails to beat the root costs one comparison and no heap work. The alternative shape — buffer and rank offline — needs the whole dataset somewhere addressable. On a capped device that means writing to durable storage and paying the I/O, the operational surface, and the failure modes of a pipeline that ships raw data off the box. ## What the cap costs, stated as a commitment The important sentence for a lead is: **discarding is irreversible, and the discard rule is the product decision.** Concretely, choosing the heap freezes four things before the first reading arrives. 1. **k is frozen.** The (k+1)-th largest reading was destroyed the moment it lost. "Show me the top 500 instead" is not a query change; it is a redeploy plus a wait for enough new data. 2. **The metric is frozen.** The comparison used at the bar defines what "largest" means. Change the definition — a calibration offset, a different field, a filter on sensor health — and the historical outputs are not comparable with the new ones. 3. **Distributional questions are foreclosed.** Medians, percentiles, histograms and counts over the discarded tail need the tail. The heap keeps the extreme and destroys the distribution. 4. **You cannot recompute yesterday.** Verification, backfill after a bug, and "why did the dashboard show that" all depend on data the gateway no longer has. None of these are technical objections to the algorithm; they are the reason the choice belongs to whoever owns the product roadmap, not only to whoever writes the loop. ## Windows, and the merge property worth knowing On an endless stream you must define a window — per hour, per shift, per firmware epoch — because "the top 100 ever" is rarely what anyone wants. Two facts about windows are worth having ready. For **value-based** selection, per-window results merge exactly. Any value among the k largest of the union must also be among the k largest of its own window, since at most k−1 values in the whole union beat it, and therefore at most k−1 within its window do. So combining the 24 hourly top-100 lists and taking the largest 100 of that pool yields the exact daily top-100 — no approximation, and only 2,400 values need to travel. For **frequency-based** ranking, the same merge is **not** exact. A term that is just below the bar in every window can outrank, on the day's total, a term that spiked once. Merging per-window frequency top-k silently loses it. Candidates who learned the merge trick on values and apply it to counts produce a wrong answer that looks right, and this is precisely the kind of mistake a lead is expected to catch in review. ## Sizing k as a budget line, not a parameter "Just raise k to 10,000" reads like a config change and is not. Resident state grows by a factor of a hundred plus per-entry payload, against a ceiling that was the binding constraint in the first place. Per-value *time* barely moves — log2 goes from about 6.6 to about 13.3 — but the guard fires less often, because a larger heap has a lower bar, so more arrivals do real work. Treat the request as a capacity request with a number attached, and answer it in bytes on the device rather than in complexity classes. ## How to decide, and what to write down The question to put to the room is: *is the question we are answering settled?* - **Settled, and the cap is hard** — commit to the heap. Document that k and the comparison are part of the interface, that raw values are not retained, and what the reprocessing story is (there isn't one). - **Unsettled, or verification matters** — the algorithm is still the heap on the device, but you buy a hedge elsewhere: a short rolling archive of raw readings retained off the gateway for a bounded period, sized deliberately, so re-analysis under a new definition is possible without waiting for fresh data. That storage is a line item somebody must approve; surfacing it is the job. Either way, the failure mode to avoid is silent: shipping bounded-memory selection, letting the organisation forget that the tail was destroyed, and discovering it six months later when someone asks a question the pipeline structurally cannot answer.
- Do per-window top-k results merge into a correct top-k of the whole period?For value-based selection, yes and exactly: any value in the union's top k has at most k−1 values beating it overall, so it is in its own window's top k too. Pool the window results and take k. For frequency-based ranking it is not exact — a term just below the bar in every window can outrank a one-time spike on the total, and merging loses it.
- Product asks to raise k from 100 to 10,000. What actually changes?Resident state grows roughly a hundredfold plus payload, against the ceiling that constrained the design. Per-value time barely moves — log2 goes from about 6.6 to about 13.3 — but the bar is lower, so the guard rejects less and more arrivals do real heap work. Answer it as a capacity request in bytes on the device, not as an algorithm question.
- How do you hedge if the definition of the metric might change later?Keep the bounded selection on the gateway, but buy a short rolling archive of raw readings retained off the device for a bounded period. It lets you re-run under a new definition without waiting for fresh data. Size it deliberately and name it as a budget line — an unfunded hedge is the same as no hedge.
- What do you write into the interface documentation for this pipeline?That k and the comparison rule are part of the contract, not tunables; that raw readings are not retained, so no percentile, histogram or backfill can be derived downstream; and that outputs before and after any change to the comparison are not comparable. The point is to stop the organisation from assuming a reprocessing path exists.
Committing to the heap is like keeping only the leaderboard and shredding the score sheets: cheap to carry, and impossible to re-score once someone changes the rules.
saying these in an interview costs you the question
- Treats discarded values as recoverable later
- Assumes k can be changed after deployment
- Calls the memory ceiling an implementation detail
- Merges per-window frequency rankings as if exact
- Sees only the log-factor win, not the bounded state