The Order Book Engine

How it works

You are given starter JavaScript for createBook(), a limit order book with four operations: add(id, side, price, qty) returns an array of trades and rests any unfilled quantity; cancel(id) returns true if the order was removed and false if it is unknown or already gone; bestBid() and bestAsk() return a price or null for an empty side. Matching follows price-time priority - best price first, then oldest at that price - and every fill prints at the resting (maker) order's price, not the incoming taker's. The starter stub rests orders without matching, scans on cancel, and returns null for both best-price queries; you edit it in the on-page editor.

Run the feed executes your code in a sandboxed Web Worker against a fixed 11-step script: three sells rest (5 and 3 at 101, 10 at 102), a buy at 100 rests without crossing, a buy of 6 at 101 must sweep the first ask for 5 then the second for 1, a cancel of the partially filled ask must return true, cancelling it again and cancelling an unknown id must both return false, a buy of 5 at 102 must trade with the 102 ask while skipping the cancelled order, and best bid and best ask must read 100 and 102. Each step shows PASS or FAIL with the expected and actual values on a failure. A run that hangs is killed after a timeout with a hint that a scanning cancel is the usual cause.

Only once all 11 checks pass does the latency benchmark run: 6,000 orders are rested across 20 price levels and then every one is cancelled, timed for both your engine and a reference O(1) implementation in the same worker (both JIT-warmed, medians of repeated runs), so a slow machine moves both numbers together rather than changing the verdict. You pass the gate if your time is at most 5x the reference. A Reveal solution button swaps in the full reference code at the cost of a revealed mark on your progress record, and Reset restores the starter stub.

How scoring works

Two separate grades. Correctness: all 11 script checks pass. This records a correct or incorrect attempt against the data-structures skill on every run.

Latency: candidate time divided by reference time must be at most 5. The latency grade is only recorded - against the complexity skill - when correctness already passes, so a correct-but-slow engine is scored as exactly that: right on data structures, wrong on complexity.

Revealing the solution records a revealed attempt on data-structures - it costs accuracy in your progress record and earns nothing. There are no points otherwise; the win state is all checks green plus the latency gate cleared.

Get price-time priority and maker pricing exact

The matching loop for an incoming order is: while quantity remains, find the best opposite price that still crosses (lowest ask at or below a buy's limit; highest bid at or above a sell's limit), fill against the oldest order at that price, and print the trade at the resting order's price. The script tests each clause separately. The 6-at-101 buy checks time priority within a level: it must fill 5 from the first-rested ask before touching the second. The 5-at-102 buy checks price priority across levels and maker pricing - it trades at 102 because that is where the resting order sits.

Partial fills need care on both sides of the trade. The taker's remainder rests in the book at its own limit (the 4-at-100 buy that never crosses must be there for bestBid to return 100 at the end). The maker's remainder stays resting with reduced quantity - the second ask keeps 2 of its 3 after being swept for 1, which is what the subsequent cancel of it must return true against.

Keep the two sides of the book as separate structures keyed by price with a FIFO list per level. One combined map keyed by side-and-price strings, as the starter hints at, works for resting but makes finding the best crossing price awkward - separating bids from asks makes the crossing scan a sorted walk over one map's keys.

O(1) cancel means a tombstone, not just a hash map

The starter cancel scans every price level and splices - linear in the book size, and the benchmark of 6,000 rested orders each cancelled makes that quadratic overall, which is what the timeout hint and the 5x gate exist to catch. The first half of the fix is an index: a map from order id to the order object, so cancel finds its target in one lookup.

The second half is the one most people miss, and the game's own failure message calls it out: splice is still O(n) even when a map told you exactly where to look, because the array shifts every element after the removal point. The full fix is lazy deletion - mark the order cancelled (a tombstone), zero its quantity, drop it from the id index, and return. The matching and best-price paths then skip tombstones when they encounter them at the front of a level's queue, pruning them at that moment for free.

This lazy-deletion pattern - pay nothing at delete time, pay a deferred constant at read time - is a general data-structure tool worth owning beyond this game. It is how heaps handle arbitrary deletion, and it is the standard answer whenever a hot path cannot afford structural surgery on a container.

Match the cost model to the message flow

The brief states the design premise: an exchange feed carries far more cancels than fills, because most resting orders never trade. That flow dictates where the constant-time budget goes. Cancel is the hot path, so it gets the O(1) treatment. Add does a sorted scan over price keys per fill - fine here, because adds are rarer and the level count in the benchmark is small (20 levels), and the reference solution itself sorts keys on each pass.

This is the transferable engineering lesson: complexity budgets are set by message frequency, not by which operation feels most important. A book with a beautiful O(log n) add and an O(n) cancel dies in a cancel/replace storm; the inverse survives. When the latency readout shows your ratio, a large number with all checks green almost always means cancel is still touching the size of the book - via a scan, a splice, or a per-cancel rebuild.

Cheap edge-case discipline closes out the last checks: cancel must return false for an unknown id and false again for an id already cancelled or fully filled - which falls out naturally if a fill removes the maker from the id index and a cancel checks the tombstone flag.

A worked example

Walk the script against a correct book. Asks rest: a1 5@101, a2 3@101, a3 10@102 - the 101 level's FIFO holds a1 then a2. Buy b1 4@100 does not cross the 101 best ask; it rests, and it is the entire bid side from here on.

Buy b2 6@101 arrives. Best crossing ask is 101; the oldest order there is a1, so trade 5@101 with maker a1 (a1 is now filled and leaves the id index). One lot remains; still crossing at 101, next in queue is a2, so trade 1@101 with maker a2, leaving a2 resting with quantity 2. Expected output, in order: [{101, 5, a1, b2}, {101, 1, a2, b2}]. Then cancel a2: found in the id index, tombstoned, true. Cancel a2 again: tombstone flag says gone, false. Cancel zz: never existed, false.

Buy b3 5@102: the 101 level's front is a2's tombstone - prune it, the level is empty, so the best crossing ask is 102. Trade 5@102 with maker a3, who keeps 5 resting. Finally bestBid walks bid prices high to low and finds b1's 100; bestAsk walks asks low to high, sees 101 empty after pruning, and returns 102. All 11 checks pass, the benchmark rests 6,000 orders and cancels them all, and a tombstone cancel lands well inside the 5x budget.

Common mistakes

• Printing fills at the taker's price. Trades execute at the resting maker's price - the b3 sweep trades at 102, and the script's expected trade objects check the price field exactly.

• Breaking time priority within a level. The first-rested order at a price fills first; any structure that loses arrival order at a level fails the b2 sweep.

• Adding an id-to-order map but keeping splice. The scan is gone but the array shift is still O(n) - tombstone the order instead of removing it, and prune lazily.

• Letting cancelled orders trade. The b3 step exists precisely to catch a book that matches against a2's corpse - matching must skip tombstones.

• Wrong cancel return values on the edge cases. Unknown id, already-cancelled, and already-filled must all return false; double-cancel returning true fails a dedicated check.

Why interviews test this

Build me a limit order book is arguably the signature quant developer interview question - it tests data-structure selection, exact spec adherence (price-time priority, maker pricing, partial fills), and cost reasoning in one problem. As the game's brief notes, nearly everyone writes a working book; the follow-up about what cancel costs on the hot path is what actually separates candidates.

The two-grade structure mirrors how the real interview is scored: correctness gets you to the follow-up, and the follow-up is a complexity conversation. Being able to say cancel is O(1) via an id index plus tombstones, and why splice would quietly reintroduce O(n), is a prepared answer to the exact question the interviewer is holding.