Rebuilding The Book From A Message Feed

A reconstructor is a small state machine: keep a map from order ID to (side, price, size), and a map from price to total size, and update both as messages arrive. The hard part is not the logic — it's getting every edge case bit-for-bit right, because one dropped cancel silently corrupts the book forever after.

Building it step by step

Start empty. The feed sends:

1. ADD id=1001 side=B price=99.98 size=400
2. ADD id=1002 side=B price=99.98 size=200
3. ADD id=1003 side=S price=99.99 size=300
4. EXECUTE id=1003 size=150 (a buy order, not shown, lifted part of the offer)
5. CANCEL id=1001 size=400 (fully cancelled)
6. ADD id=1004 side=B price=99.97 size=600

Processing each: after (1)-(2) the bid at 99.98 is 600, held by orders 1001 and 1002 in that arrival order. After (3) the offer at 99.99 is 300. Event (4) reduces order 1003's size to 150, and the offer level to 150 — the order is not removed, since it still has 150 left. Event (5) removes order 1001 entirely; the bid at 99.98 drops from 600 to 200, leaving only order 1002. Event (6) opens a new price level, 99.97, at 600.

Final book:

Side	Price	Size	Orders
Bid	99.98	200	1002
Bid	99.97	600	1004
Ask	99.99	150	1003

The single most common bug: treating step 4 as "delete order 1003" instead of "shrink it by 150." An execute message carries the filled quantity, not the remaining one — you subtract, you don't replace.

Two things ruin a reconstructor in production. First, sequence gaps — if the feed drops or reorders a packet, every level built after it is wrong until the next full snapshot; production systems checkpoint against periodic snapshots for exactly this reason. Second, auction and halt messages, which don't fit the add/cancel/execute pattern and need special-casing or the book silently freezes with stale state.

In an interview, the fastest way to show you understand this is to trace a five-message sequence like the one above by hand and get the final depth right, not to recite the state-machine diagram.