A report asks for the ten largest rows and then prints them as ranked — what assumption can fail?
answer
- two operations, not one
- membership is not arrangement
- the saving is the rows left unarranged
- the boundary tie decides the count
basics
~20 sThat asking for the ten largest also put them in order. A top-n pass answers membership, not arrangement: some designs hand the n rows back unordered, and which of several tied rows takes the last place is unspecified unless a tie-break is given.
solid answer
~50 sAsking for the n highest rows and ordering the whole table are two different operations, and only the second promises an arrangement. The top-n pass — asking only for the n highest or lowest rows — exists precisely so that the remaining rows need not be put in order, and that is where its saving comes from. What varies across designs is the rest of the story: some return the n rows arranged as a convenience, some return them in whatever order the pass left them, and some say nothing. Membership at the boundary varies too: when several rows tie for the last place, a design may take an arbitrary one, or keep them all and return more than n. So order the n explicitly afterwards if the report ranks them, and give the pass a tie-break if it must contain exactly ten.
go deeper
Know that there is a separate way to ask for the n highest or lowest rows, and that it is not the same request as putting the whole table in order, even though the answer looks similar.
Explain what the pass buys — the rows outside the n are never arranged — and that this is exactly why it is under no obligation to hand back its own n arranged either.
Diagnose it in a shipped report: the ranking was right on one dataset and scrambled on another, with no code change and nothing raised, because arrangement was never requested. Order the n explicitly and pin the boundary tie with a further key.
The standing rule worth setting is that any published top-n specifies both a tie-break and an explicit ordering of its result, so the artefact is reproducible across runs and tools rather than depending on which internal pass the tool happened to choose.
## Two different requests "Put this table into amount order" and "give me the ten largest by amount" look like the same request with a limit bolted on. They are not. The first is an **ordering step**: the operation that puts rows into an order you specify, taking one or more keys each with its own direction. The second is a **top-n pass**: asking only for the n highest or lowest rows, which is a different operation because it is allowed to leave everything else alone. That permission is the entire point. An ordering step owes an answer about every pair of rows. A top-n pass owes an answer about one thing only: **which rows are in the ten and which are not**. Everything it does not have to decide is work it does not have to do. ## What the pass promises, and what it does not - **Membership is promised.** The rows you get back are the ten largest by the key you gave, and no row outside the ten is larger than a row inside it. - **Arrangement within the n is not promised in general.** Some designs arrange them as a convenience, some hand them back in whatever order the pass produced. Both exist, and the call site looks the same. - **The order of the rows outside the n is not promised at all** — and in most designs those rows are not returned anyway. - **The count is not always exactly n.** Where several rows tie for the last place, a design may take one of them arbitrarily, or keep all of them and hand you more than you asked for. - **Nothing raises when you get this wrong.** A scrambled ranking is a well-formed table of ten rows. ## The boundary tie Suppose eleven rows share the tenth-largest amount. The request "the ten largest" now has no single right answer, and the design has to pick a policy: | Policy | Rows returned | Consequence for a report | |---|---|---| | Take an arbitrary subset of the tied rows | Exactly ten | Membership can differ between runs | | Keep every tied row | More than ten | A layout expecting ten rows overflows | | Break the tie by a further key you supplied | Exactly ten, decided by data | Reproducible, and reviewable | Only the third is something you can defend in a review, and it is the only one that stays the same if the tool changes. ## Why the report looked right for months This is the shape of the production incident. The report was written against a dataset where the top ten happened to come back arranged, and where no two rows tied near the boundary. Both of those are properties of the data, not of the request, and both stopped holding when the data grew or shifted. The symptom is a ranking that is out of order, or a row that appears and disappears between runs, with no code change and no error anywhere. The reason it survives review is that the code reads as if it says what the author meant. "Take the ten largest, then display them in order" is what the author thought they wrote; what they wrote was only the first half. ## What to write instead 1. **Ask for membership and arrangement separately.** Run the top-n pass to cut the table down, then apply an explicit ordering step to the ten rows you kept. Ordering ten rows costs nothing measurable, and the intent is now on the page. 2. **Give the pass a tie-break.** Add a further key so the boundary is decided by data rather than by whichever row the pass reached first. This is what makes the membership reproducible. 3. **Do not replace the pass with a full ordering just to be safe.** The saving is real and grows with the table, because the work skipped is the arrangement of every row you are throwing away. Keep the pass; add the ordering afterwards on the small result. 4. **Assert the count where the layout depends on it.** If the output must be exactly ten rows, check that it is, rather than assuming the pass guaranteed it. ## The sentence to have ready If an interviewer asks you to summarise it: *a top-n pass answers a membership question and an ordering step answers an arrangement question, and a ranked report needs both — so ask for both, and decide the boundary tie yourself rather than letting the pass decide it for you.*
- Why can a top-n pass be substantially cheaper than ordering the whole table and keeping the first n?It only has to separate the n highest from everything else, not arrange everything else among itself. Every row is still examined, but the work skipped grows with the table while n stays small, so the gap widens as the input grows. The work it skips is exactly the arrangement you then cannot rely on.
- Eleven rows tie for tenth place. What outcomes are possible, and how do you get a defined one?Depending on the design you get ten rows chosen arbitrarily from the eleven, or all eleven and therefore more rows than you asked for. Add a tie-breaking key to the pass so the boundary is decided by data. Then the membership is reproducible and the count is what you specified.
- Should you ever skip the pass and just order the whole table?Only when the table is small enough that the difference does not matter, or when you need the full arrangement anyway. On a large table the pass is doing strictly less work for the same membership answer, so the right shape is pass first, then an explicit ordering of the small result.
saying these in an interview costs you the question
- Assumes the n returned rows always come back arranged.
- Thinks a top-n pass is an ordering with the tail discarded.
- Expects exactly n rows when several tie at the boundary.
- Dismisses the cost difference between a full ordering and the pass.
- Believes the rows outside the n are left in a known order.