Requirements checklist

• Priority is PRICE-TIME, both halves said: better price first; same price, earlier arrival first → forces a FIFO queue per price level.
• Limit orders v1; market orders follow-up — the empty-book remainder is YOUR defended call (reject vs convert-to-limit).
• Partial fills are the norm: fill best-level-first; remainder rests at its limit price. One order → many trades.
• Cancel by id must be CHEAP → forces an order-id index into the book (the free-takes-no-size move of this problem).
• Single-threaded hot path, one sequenced input stream. Latency bar: tens of thousands of orders/sec, worst case is the bar.
• Out of scope: risk, fees, auctions, multi-instrument; ids arrive on orders.

The model

book = two sides
  side  = sorted map: price -> level   (bids desc, asks asc)
  level = FIFO queue of resting orders (intrusive doubly-linked)
  index = order id -> node in its level   (O(1) cancel)
match: while incoming crosses best opposite level:
  fill min(qtys) vs level HEAD -> emit immutable trade
  resting exhausted -> unlink; partial -> shrink IN PLACE (keeps spot)
remainder rests at tail of its own side; gets indexed
trade price = the RESTING order's price (maker sets the price)

Invariants (say them)

• Levels strictly price-ordered; within a level, strictly arrival-ordered.
• The index maps exactly the resting orders — no more, no less.
• Level's cached total equals the sum of its orders' remainders.
• Trades append-only, priced at the resting order's price.
• The book never crosses after any operation: best bid < best ask.

Complexity facts

• Fill O(1); submit consuming k orders across m levels: O(k + m log L). Cancel O(1). Prices in integer ticks, never floats.
• The claim that matters: no operation ever scans orders it doesn't touch — cost is proportional to trades produced.
• Single-threaded because matching semantics require a total order: the sequencer, not a lock, is the concurrency answer; outputs are a pure function of the input sequence.

What earns points, per report dimension

• Requirements & interface — extracted both halves of price-time; pinned the market-remainder rule as a choice; caught what cheap-cancel implies at requirements time.
• Core design & invariants — derived sides/levels/queues/index from the rules; partial fills keep queue position; stated the uncrossed-book invariant.
• Extension probe — locate the new demand at a seam (loop policy, operation boundary, pre-fill guard); narrate what changes and what provably doesn't.
• Complexity honesty — worst-case framing, not average; per-operation costs tied to trades produced; the no-scan claim defended.
• Communication — definitions said back exactly; the maker-sets-the-price rule narrated; choices presented as choices.

Ready? Sit the live mock → — the interviewer will run a twist this chapter deliberately hasn't shown you.