Designing an Order Book Data Structure in an Interview

An order book answer needs constant-time best price, constant-time cancel by order id, and ordered price-level iteration, in one design.

An order book design question asks a candidate to build one container that answers three operations at speeds a naive structure cannot deliver together: reading the current best bid and best offer in constant time, cancelling or amending any resting order by its id in constant time, and walking the book from the best price outward in price order when a strategy needs depth rather than just the top. The answer that satisfies all three is an array of price levels indexed directly by a tick, with an intrusive linked list of orders inside each level and a hash map from order id to a node pointer.

Reading the best bid and best offer happens on every tick and every strategy decision, so it has to be O(1), not O(log n) and certainly not a scan. Cancelling and amending an order by id happens constantly as market makers requote, and if that operation costs anything more than O(1) the whole book slows down under the exact load a busy trading session produces. Iterating price levels in order, from the best price outward, is needed to compute the depth a strategy would actually get filled at, and that iteration has to visit levels in price order without a sort step in the middle of a hot path.

No single common structure satisfies all three by itself. A sorted array gives ordered iteration and O(log n) lookup by price but O(n) insertion and deletion as elements shift. A balanced tree gives O(log n) for everything but never O(1) for anything, and the constant factor behind tree pointer chasing is worse in practice than the tick-indexed array design below achieves. A plain hash map gives O(1) lookup by order id but no ordering at all, which is why it appears as one piece of the design rather than the whole answer.

The core idea is to stop treating price as a floating point number to be sorted and instead treat it as an integer tick index into a fixed-size array, since every exchange quotes in discrete increments, a tick size, rather than continuously. If the tick size is one cent and the instrument trades in a band of one hundred dollars around its current price, the array needs ten thousand slots, one per possible cent, and the array index for a given price is simply that price divided by the tick size, an O(1) computation with no comparison or search involved.

Each slot in the array holds a summary of that price level, typically the total resting size, and a pointer to a doubly linked list of the individual orders resting there in arrival order. Best bid and best offer become a small cached index into this array that is updated only when the best level empties out or a better level receives its first order, which is why reading them is O(1): the answer is already sitting in a variable, not computed by scanning.