skip to content

Over yesterday's finished orders a global top-10 by spend is one sort. Over an input with no end, what happens to that requirement?

level: middleimportance: must knowfreq 62%

answer

  1. no last record, no settled rank
  2. impose a boundary or revise
  3. running totals, one per key
  4. global sort has no running form

basics

~20 s

It has to be redefined. With no last record, no ranking is ever settled, so you either rank within a boundary the job imposes, or publish a running top-10 that is correct only as of the records already seen.

solid answer

~50 s

The requirement as written assumes an ending, because a rank is a claim about every record. Over an input with no end there are two honest repairs, and they answer different business questions. **Impose a boundary**: define the ranking over a fixed slice, compute it the way you would over any finite input, and publish one final answer per slice — the cost is waiting for the boundary to be reached. **Publish a running answer**: keep a per-key running total, emit a top-10 as of the records seen, and let it change — the cost is that the reader must handle a value that moves and an entry that drops out. A plain global sort, meaning every record emitted in order, has no equivalent at all: the first position is only certain once the smallest remaining record is known, and over an endless input it never is.

go deeper

for a junior

Recall that a rank, a sort and a total are claims about every record, so an input with no last record cannot settle them. Something in the requirement has to give.

for a middle

Name both repairs and their prices: a final answer per imposed boundary that is always a boundary old, or a running answer that stays fresh but can reorder and, where amounts reverse, fall.

for a senior

Show that you renegotiate the requirement rather than the machinery, and that you state how the revised answer reaches the destination, because engines differ in whether they emit per record, per boundary, or speculatively then corrected.

for a principal

Decide which shape is the default for figures leaving the organisation. A number that can move is fine on an internal dashboard and dangerous in a customer report, and that is a policy call, not a per-pipeline one.

## Which computations actually depend on the ending A ranking is not special; it is one member of a family. Any computation whose answer can still be changed by an unseen record needs the record set to be closed before it can be called done. | Computation | What the ending supplies | Over an endless input | |---|---|---| | Count or sum over everything | the assurance nothing more will be added | a running value, or a total within an imposed boundary | | Global sort, every record in order | certainty about the first position | unsatisfiable in its plain form; sorting within a boundary is fine | | Rank or top-N | certainty that no unseen record displaces an entry | a running list that may reorder | | Exact distinct count | the closed set to count members of | a running estimate or an exact count per boundary | | Median or a percentile | the whole distribution | a value per boundary, or an approximation that is revised | | Anything labelled "final" | the right to make the claim | "as of" a stated point | The common thread: these are computations where *no output is certain until the last input has been read*. Contrast a per-record transformation, or a filter, or a lookup: each output is complete the moment its input record is, and an endless input costs them nothing. ## Repair one — impose a boundary Define the ranking over a fixed slice instead of over everything. Inside that slice the computation is an ordinary finite one, and it produces a single final answer that a reader can quote. What it costs: - **Latency.** No answer exists until the boundary is reached, so the freshest figure is always at least one boundary old. - **A decision you now own.** Nothing in the data proposed the boundary, so its size and placement are your choices and they change the meaning of the number. The shapes such a boundary can take, and when a grouping emits, are a separate subject. - **A different question answered.** "Top customers this hour" is not "top customers ever", and stakeholders who asked for the second will keep reading the first as though it were. ## Repair two — publish a running answer Keep a per-key running total and emit the current top-10 as records arrive. What it costs: - **The reader must tolerate movement.** An entry can be displaced later, so a copy of the list saved this morning is a stale claim rather than a wrong one. - **The list is monotonic only under assumptions.** Where amounts are additive and never reversed, a per-key total only rises; introduce refunds, corrections or negative adjustments and a total can fall, which is exactly when a reader who assumed "it only goes up" gets a surprise. - **Retention has to be bounded.** You need one accumulator per key, not the records themselves — that is what makes the running form affordable. But if the key space keeps growing, the retained set grows with it, and keeping long-lived state bounded is its own subject with its own remedies. ## What varies between engines, and why you must say so How the revised answer reaches a reader is not uniform across this class of system, and an answer that assumes one shape is wrong on a rival: - Some runtimes emit an **updated running result on every input record**, so the destination sees a stream of revisions and must be able to replace by key. - Some emit **once per imposed boundary**, so the destination sees one value per slice and revisions are rare or absent. - Some emit **speculative results early and corrections afterwards**, so the destination sees the same logical answer more than once and must not add the copies together. Saying which of these the job is on is part of the answer, because the destination's write semantics have to match it. ## The judgment an interviewer is listening for The weak answer reaches for machinery — more memory, more machines, a bigger sort. The obstacle is not capacity; it is that the question as asked has no answer. The strong answer goes back to the requirement and offers the two shapes with their costs: a final number per boundary that is always a little stale, or a fresh number that can move. Then it names what the business actually needs, which is usually the second for a dashboard and the first for anything that leaves the company.

  • Why is a running top-10 affordable in memory when a global sort is not?
    The top-10 needs one accumulator per key plus a ten-entry list, so its footprint follows the number of distinct keys rather than the number of records. A sort has to be able to place any record relative to any other, so it must retain them all. That is also why a growing key space quietly reintroduces the problem.
  • A stakeholder insists on a single all-time ranking from an endless input. What do you offer?
    A running all-time ranking with an as-of marker, which is genuinely all-time up to a stated point, or a ranking over a closed slice republished each boundary. What cannot be offered is an all-time ranking that never changes — that is a claim about records nobody has seen yet.
  • Does sorting within an imposed boundary give a globally ordered output?
    No. Each slice is ordered internally, and slices are ordered relative to one another only by their boundaries, so a record in a later slice may sort below one in an earlier slice. If a reader needs a single ordered sequence across slices, that requirement still depends on an ending you do not have.

saying these in an interview costs you the question

  • Says a global sort just needs enough memory or machines
  • Assumes a per-key running total can only increase
  • Publishes a running rank as though it were settled
  • Thinks imposing a boundary answers the original question unchanged
  • Believes retaining every record is needed for a running top-N