skip to content

A diff inserts each match result into a sorted score array per event — what do you flag in review?

level: seniorimportance: should knowfreq 45%

answer

  1. Cost the whole handler, not the search
  2. Per event versus across all events
  3. The shift is the half that dominates
  4. Sum 1 + 2 + ... + m
  5. Ask what bounds the table size

basics

~20 s

Each insert opens a hole mid-array, so it costs linear time in the scores already stored. Across m events that compounds to quadratic total work — invisible at fifty players, a stall at fifty thousand.

solid answer

~50 s

Flag that the per-event cost is Θ(n), not Θ(1). The handler walks the array to find the rank position, then shifts every lower-ranked entry one slot right; both halves are linear in the entries already stored. Run that per match and the totals compound: as the table grows towards m entries the accumulated moves are on the order of m², so ten times the traffic is a hundred times the work. Two points beyond the label. Making the position search faster does not fix it — the shift is still linear, so the class does not move. And whether it needs fixing depends on the bound: capped at a few hundred rows with something enforcing the cap, this is fine and I would only ask for the bound to be stated; unbounded and traffic-driven, I would move the ordering off the write path.

code

pseudocode · 14 lines
pseudocode
// scores[0..n-1] kept in descending points order

on match_finished(entry):
    p = 0
    while p < n and scores[p].points > entry.points:
        p = p + 1                  // locate rank: O(n)

    for i in n-1 down to p:
        scores[i+1] = scores[i]    // open the hole: O(n - p)

    scores[p] = entry
    n = n + 1

// called once per finished match, with n growing every time

go deeper

for a junior

Be ready to see that inserting into the middle of a sorted array moves the entries below it, so the operation is linear rather than a single write.

for a middle

Explain both linear halves of the handler and sum the cost across many events to reach the quadratic total. Know why a faster position search leaves the class unchanged.

for a senior

Show proportionate review judgment: name the growth shape, ask what bounds the table and the event rate, and propose the cheapest fix that removes the ordering work from the write path.

for a principal

Own the framing that quadratic behaviour fails exactly when the product succeeds, and decide when writing the bound down beats paying for a rewrite the team then has to maintain.

## What the code actually costs The handler does two linear things per event, and the second is the one that gets missed. 1. **Locate the rank position.** Scanning down the array until the new score outranks the entry there is Θ(n) in the worst case. 2. **Open the hole.** Inserting at position `p` moves entries `p … n−1` one slot right — `n − p` moves. A last-place finisher moves nothing; a leader moves everything; the mid-table finisher the scenario is built around moves roughly half the table. So the per-event cost is Θ(n): linear in how many scores are already stored, on an array whose size is the very thing the feature grows. ## From per-event to total One linear operation is unremarkable. The defect is that it runs on every event while `n` climbs. Insert m results one at a time into an initially empty table and the moves accumulate roughly as 0 + 1 + 2 + … + (m−1) in the worst case, which is about m²/2 — **Θ(m²)**. With mid-table positions rather than always-first ones the constant softens to around m²/4, and the class does not change. Quadratic is the property to name. That shape is what makes the bug survive testing. The relationship is not linear in traffic: doubling the season's match volume quadruples the work, and a table that keeps up comfortably at 500 players can miss its deadline entirely at 20,000. Nothing in staging, running with a seeded handful of players, will show it. ## The correction reviewers get wrong The reflex suggestion is to speed up step 1 — find the insertion point faster instead of walking. That is worth almost nothing here: step 2 is untouched, the shift is still Θ(n) per event, and the total stays quadratic. Removing the cheaper half of a two-part linear cost leaves a linear cost. Saying this in review is a strong signal, because it shows you costed the operation that dominates rather than the one that was easiest to see. What actually changes the class is not maintaining sorted order on the write path: - **Append and rank on read.** Store results as they arrive — constant time per event — and produce the ordering when the table is actually displayed. If the leaderboard renders once a minute and matches finish continuously, this converts thousands of linear inserts into one ordering pass per render. - **Keep only what is displayed.** If the page shows a top-k, maintaining a bounded top-k structure caps the per-event cost by a constant you chose, independent of how many players exist. - **Batch.** Accumulate arrivals and fold them into the ordered table periodically, so the linear work is paid once per batch rather than once per event. Each of these is a trade against read cost or freshness, and the right one depends on the read-to-write ratio, which is a question to ask the author rather than a fact to assume. ## The review judgment, which is the real question A senior review is not "this is O(n²), rewrite it". It is proportionate: - **Ask what bounds n.** Table capped at 200 by product rules and enforced somewhere? Then the quadratic term is bounded by a constant and the code is fine as written. Ask for the bound to be visible at the code — a stated limit near the array, not folklore — so the next person to lift the cap knows what they are lifting. - **Ask what drives the event rate.** Per-match on a hobby league is nothing; per-match across every concurrent lobby is a different system. - **Say where it will show up.** Not "it will be slow" but "the handler's cost per event rises with table size, so latency degrades as the population grows, which is the worst possible failure timing — it arrives exactly when the product succeeds." - **Price the fix.** Append-and-sort-on-read is usually a small, local change with no new invariant to maintain. When the fix is that cheap, arguing about whether n will really get large is more expensive than doing it. ## Stating the costs precisely Be careful with the directions of these claims, because a review is where imprecision gets quoted back at you. Θ(n) per insert is a statement about growth, not about milliseconds — a linear shift over a small contiguous block is a fast block move, and at n = 200 it will not register on any profile. Θ(m²) total is a worst-case-shaped statement about a sequence of operations, not a promise that the service is currently slow. And "quadratic" is not an argument that the code is wrong; it is an argument about what happens at 10x, which is exactly the conversation a review is for.

  • Would keeping the array unsorted and ordering it only when the leaderboard is displayed be better?
    It depends on the read-to-write ratio, which is the question I would put to the author. Appending is constant time per event, and ordering costs one Θ(n log n) pass per render. If matches finish continuously and the table renders once a minute, that is a large win. If every single write is immediately followed by a read, you have moved the cost rather than removed it, and a bounded top-k structure serves better.
  • The author says the table is capped at 200 rows, so the quadratic term does not matter. How do you respond?
    I agree, provided the cap is real and enforced rather than assumed. I would ask what enforces it and make it visible next to the array, so whoever raises the limit later sees what they are changing. Quadratic behaviour bounded by a small constant is not a defect; a quadratic loop guarded only by an undocumented belief about size is, because the belief is what changes first.
  • Does making the search for the insert position faster fix the per-event cost?
    No. Locating the position and opening the hole are both linear in the entries already stored, so removing one of them leaves a Θ(n) insert and a quadratic total. This is the most common wrong fix for this shape of code, and it is worth saying explicitly in the review, because it looks like progress and lets the real cost ship unchanged.
  • How would you demonstrate the problem rather than argue about it?
    Time the handler at a few table sizes — say 1,000, 4,000 and 16,000 entries — and show the per-event cost rising in step with size while the event rate is held constant. A curve that quadruples when the size quadruples settles the discussion in a way that a complexity label rarely does, and it also establishes the size at which the current design stops meeting the latency target.

saying these in an interview costs you the question

  • Calls the insert constant time because only one record was added
  • Blames the position scan and leaves the shift untouched
  • Reports O(n) per event without summing across events
  • Demands a rewrite without asking what bounds the table
  • Assumes the contiguous block move makes the linear cost irrelevant
  • Claims quadratic code is always a defect regardless of input size

context

resolving links…