Your plan for a packet stream under a hard memory ceiling is single-pass; how do you defend it against "just sort it"?
answer
- which constraint is actually binding
- sorting needs every record resident
- the input may never be re-read
- a plan that cannot run has no speed
- name what the single pass gives up
basics
~20 sArgue admissibility before speed: sorting needs the whole stream resident, and the stream has no known length and a hard ceiling, so that plan cannot run regardless of its time class. Then name what a single pass gives up.
solid answer
~50 sThe binding constraint here is space and pass count, not time. A sorting plan needs every record resident at once — and on an inspection feature the stream arrives with no known length and cannot be rewound — so it is *inadmissible*, not merely slower or faster. Asymptotic ranking only compares plans that can actually run; a linearithmic plan that exceeds the ceiling loses to a linear one that fits, and "faster" was never the comparison being made. I defend it by stating what the ceiling permits: bounded per-record state — counters, fixed-size summaries, rolling aggregates, a bounded window — and by being explicit about the price: a single bounded pass cannot answer arbitrary order-dependent questions exactly. If the requirement genuinely demands an exact whole-stream answer, I say so and escalate the conflict rather than quietly shipping something that violates the ceiling.
go deeper
Be ready to say what a plan needs resident in memory at its peak, and to notice that sorting requires the entire input at once while a running count does not.
Explain why a memory ceiling and a single-pass input eliminate whole classes of approach before any time comparison happens, and what state can legitimately be kept when the state must not grow with the stream.
Demonstrate the admissibility-first argument on a real constraint, volunteer the accuracy you give up, and show how you present two candidate plans so the reviewer can overrule you on stated facts rather than on authority.
Own the case where the requirement and the ceiling cannot both hold: decide whether to buy headroom, accept a bounded approximation with a stated error, or renegotiate the question — and make sure that choice is written down where the next team can find it.
## Identify which constraint is binding Every plan is judged on two separate axes: is it *admissible* under the stated constraints, and among admissible plans, is it fast. Candidates are trained hard on the second and skip the first. On an inspection feature that sees a packet stream on a small device with a fixed memory ceiling, three constraints appear in the statement before any performance question does — the ceiling is hard, the stream length is unknown at start, and the data is not re-readable once it has passed. Those three decide the plan. Time is the tiebreak afterwards. ## Why "just sort it" fails here Sorting a collection requires the collection to exist. A sort that must see every record before emitting the first one holds the entire input, so its space is proportional to the number of records. With no bound on that number and a hard ceiling, the plan has no admissible execution; it does not run slowly, it runs until it dies. Two secondary problems compound it. The stream cannot be re-read, so a plan that consumes the input to build an ordering has destroyed the only copy. And an inspection feature is usually expected to produce results as data arrives, which any whole-input sort forbids by construction. Saying this out loud is the defence. The reviewer is not wrong that sorting is a good general tool; they are applying it without checking the admissibility gate. ## What single-pass buys, and at what price A bounded single pass keeps state that does not grow with the stream: running counts per category, minimum and maximum, sums and derived averages, a fixed-size window of recent records, a small set of candidate values, a bounded summary of the distribution. Anything that grows with the number of *distinct* values seen is only admissible if that count is bounded, which is a separate promise you must extract from the statement rather than assume. The price is real, and volunteering it is what makes the defence credible rather than defensive. Exact answers to questions that depend on the whole ordering — an exact median, an exact count of distinct values, arbitrary ranked queries over everything seen — are not available from bounded state. Bounded-memory versions of those questions are approximate, with an error you should be able to state. Say this before the reviewer finds it. ## The wrong answer this aims at "Always pick the asymptotically fastest approach" is the reflex, and it is wrong in two directions at once. First, big-O ranks *time* among plans that run; it says nothing about whether a plan fits its box. Second, big-O is an upper bound on growth, not a promise about behaviour at the sizes you actually see — constants and memory behaviour dominate at small n, which is exactly why a plan should carry a measured or reasoned claim rather than only a class. A plan that is optimal on the time axis and inadmissible on the space axis has not won a tradeoff; it has failed a requirement. ## How to present it so the reviewer can overrule you Good defence is not winning the argument, it is handing over a decision. Put both candidates side by side with three columns: time class, peak resident space, and admissibility under the stated ceiling. Then name the condition under which the reviewer's plan becomes correct — "if the stream is bounded to a size we can enforce, sorting is simpler and I would prefer it" — and ask whether that bound exists and can be enforced. If they can produce it, you have a simpler plan and a documented assumption. If they cannot, the single-pass plan stands on the record rather than on your insistence. ## When nothing fits Occasionally the requirement and the ceiling are jointly unsatisfiable: an exact whole-stream answer is demanded and no bounded-state approach can produce it. The senior move is to surface that conflict explicitly and get one side changed — a raised ceiling, an accepted approximation with a stated error bound, or a narrower question that is answerable in bounded state. What you do not do is pick the exact plan and hope the ceiling is soft, or pick the bounded plan and report an approximation as though it were exact. Both are ways of moving a known conflict off the design discussion and into an incident.
- The reviewer says the stream is "probably only a few thousand records". Does that change your plan?It changes the question, not the answer yet. An unstated bound is an assumption, and a plan that is only admissible while a guess holds is a latent outage. Ask whether the bound is real and whether anything enforces it. If it is documented and enforced, the sorting plan becomes admissible and is simpler, so I would take it and record the dependency.
- What can a bounded single pass genuinely not answer?Anything requiring arbitrary re-examination of everything seen: exact order statistics such as a true median, an exact count of distinct values when that count is unbounded, and ad-hoc ranked queries over the whole stream. Bounded-memory versions of these exist but are approximate, and the plan should state the approximation and its error rather than let a reader assume exactness.
- How do you show the tradeoff so the reviewer can overrule you on data?Present both plans with time class, peak resident space, and admissibility against the stated ceiling, then name the condition that flips the decision — a proven and enforced bound on stream length, or a raised ceiling. That turns a disagreement into a question with an answer somebody can look up, and it makes the final call theirs.
You cannot alphabetise a parade from a doorway. The suggestion is not slow, it is impossible from where you are standing; the answerable questions are the ones you can settle by counting as the floats go past.
saying these in an interview costs you the question
- Ranks plans by time class and stops there
- Assumes the input can be traversed twice
- Treats an unstated input bound as small
- Calls a plan that cannot fit the faster one
- Hides the accuracy a single pass gives up
- Ships an approximation described as exact