Why this matters: everything the requirements demanded — price priority, time priority, cheap cancels, worst-case latency — maps onto one composite structure, and the interviewer is watching whether you derive that structure from the rules or reach for a generic container and patch it. The book's shape is the answer to this round.

The model in words

Say it whole: "The book is two sides. Each side is a sorted map from price to a level, and each level is a FIFO queue of resting orders. Price priority is the map's sort order; time priority is the queue. An incoming order matches against the opposite side's best level while it still crosses, filling head-of-queue first; whatever remains rests on its own side. A separate id-to-order index makes cancel a lookup, not a search. Every fill emits an immutable trade event."

Each sentence there is a requirement wearing a data structure. That's the correspondence to make explicit — this design isn't clever, it's derived, and saying so is the strongest thing a candidate can do in this act.

The structures

Sides and levels. Bids sorted descending (best = highest), asks ascending (best = lowest). A sorted map — tree map or skip list — gives ordered levels with logarithmic inserts when a new price level appears; the hot operations peek only at the best level, which is constant-ish. Inside a level, resting orders form a FIFO queue — arrival order is time priority, no timestamps needed on the hot path.

The intrusive queue. The level's queue is best built as an intrusive doubly-linked list: each order carries its own prev/next links. The reason is the next structure.

The order-id index. A hash map from order id straight to the order's node in its level queue. This is what cheap-cancel forced: cancel becomes look up, unlink in place, decrement the level's total, delete the level if it empties — constant time, no searching, and the intrusive links are exactly what make in-place unlinking possible. If the level queue were an array, cancel would shift elements; if it were a non-intrusive list, the index couldn't unlink without a traversal. The three structures are one design decision, not three.

Trade events. Every fill appends an immutable trade record — taker id, maker id, price (the resting order's price — the maker sets the price, say it), quantity, sequence. Append-only, never edited: downstream consumers, and eventually auditors, treat trades as facts. This is the ledger discipline from the payments chapter, at microsecond scale.

The match loop, in words

An incoming buy crosses while best_ask <= incoming.price and quantity remains: fill against the ask head — the minimum of the two quantities — emit a trade, pop the resting order if it's exhausted, and repeat down the queue and then down the levels. A partially-filled resting order shrinks in place and keeps its queue position — it was there first and still is; re-inserting it would silently break time priority, and that bug is exactly what interviewers construct two-order scenarios to catch. When the incoming order stops crossing, any remainder is added to its own side (new level or tail of an existing one) and indexed.

Single-threaded, on purpose

The hot path is one thread eating one sequenced stream, and this is a design position, not a limitation to apologize for. Two reasons, both worth saying. Correctness: matching is a serial dependency chain — each order's outcome depends on the exact book state the previous order left — so parallelism inside one instrument's book buys races against a total order that must exist anyway; the sequencer, not a lock, is the concurrency answer. Performance: no locks, no contention, no cache lines bouncing between cores — the fastest known shape for this workload is a single core doing nothing else. If asked "why not threads for speed," the answer is that the workload's semantics require a total order of operations, and once you must sequence, a lock-free single thread beats a locked pool at both latency and determinism — the engine's outputs are a pure function of its input sequence, which makes every bug reproducible from its inputs.

The invariants

• Levels on each side are strictly price-ordered; within a level, strictly arrival-ordered.
• The index maps exactly the resting orders — every resting order is indexed, nothing else is.
• A level's cached total quantity equals the sum of its orders' remainders.
• Trades are append-only; a trade's price is the resting order's price.
• After every operation, the book never crosses: best bid < best ask.

That last one is the self-check invariant: if matching is correct, it holds by construction; asserting it after every operation is how the engine catches its own bugs in test.

What we rejected, and why

One big priority queue of all orders per side (price-then-time comparator): cancel becomes a search or a lazy tombstone flood, and level-based operations — "how much is bid at 100?" — require scans. The two-tier shape exists because levels are real in this domain.

Timestamps for time priority: arrival order in a FIFO already encodes it; timestamps add bytes and a comparator where a queue position suffices.