Ask a candidate to build an order book and you learn more in twenty minutes than a week of LeetCode grinding would tell you. The task sounds small: add an order, cancel an order, report the best bid and offer. The version that gets an offer at Jane Street, Hudson River Trading, or Citadel Securities looks almost nothing like the version that passes at a normal tech company, and the distance between them is the whole interview.
A big tech loop cares that your solution is correct and runs in the right big-O. A trading firm assumes that, then asks the questions you were hoping to skip. How many times do you touch the heap? What happens to your cache when the book has ten thousand price levels? Cancel the current best bid, now what? An O(n log n) answer is the price of admission, not the thing being graded.
The question under the question
Strip it down and an order book keeps two sorted collections of resting limit orders: bids descending by price, asks ascending, with orders at the same price filled in arrival order. The interface is usually three calls. Add a limit order, cancel by order id, read the top of book. Sometimes a fourth shows up, a marketable order that crosses the spread and matches against what’s resting.
The trap is reaching for the obvious answer and stopping there. A std::map<Price, ...> keyed by price, with a list at each level, is correct. It is also the answer that invites every follow-up the interviewer has been saving. They want to see whether you know why that structure costs you, and what you would pick instead.
A layout that survives the follow-ups
Three pieces do most of the work. Price levels need an ordering so you can find the best price and walk outward from it. Each level holds its resting orders in FIFO order. And cancellation has to be fast, which means a direct handle from an order id to wherever that order lives, so you never scan a level looking for it.
The handle is the part people forget. Cancels are common, often more common than fills, and a cancel that walks a list is the difference between a book that keeps up during a burst and one that falls behind. A hash map from order id to a node, plus an intrusive list at each price level, gives you O(1) cancel with no search.
struct Order { OrderId id; Qty qty; Order* prev; Order* next; }; // intrusive
struct Level { Order* head; Order* tail; Qty total; }; // FIFO at a price
std::unordered_map<OrderId, Order*> index; // cancel in O(1), no scan
// price levels: tree vs array, see belowA tree or an array of price buckets
This is where firm-specific taste shows up. A balanced tree gives you ordered prices and O(log n) inserts without assuming anything about the price range. An array indexed by price tick gives you O(1) on everything, but only because the instrument trades inside a bounded band of ticks and you are willing to spend memory on the empty levels.
| Approach | Top of book | Insert | Memory | Cache behavior |
|---|---|---|---|---|
| Balanced tree (std::map) | O(log n), or O(1) with a tracked best pointer | O(log n) | Scales with live levels | Pointer chasing, poor locality |
| Array indexed by tick | O(1) with a tracked best index | O(1) | The whole price band, empty levels included | Flat, predictable, cache friendly |
Most general engineers default to the tree. The trading answer is usually the array, because the prices an instrument can reach over a session are bounded and known, the constant factors crush the tree, and a flat array treats the cache and the branch predictor far better than a pointer-heavy red-black tree ever will. Naming that tradeoff out loud, with the caveat about memory and price bands, is most of the signal they want.
Allocation is the real exam
Here is what catches people from a pure algorithms background. On a hot path, calling new or delete per order is disqualifying at a latency-sensitive shop, even when the complexity is perfect. An allocation can take a lock, can fault, can jitter your tail latency at the exact moment the market moves. The interviewer is reading your add and cancel for heap traffic.
The fix is to own your memory. Preallocate a pool of order nodes and hand them out by index. Recycle freed nodes onto a free list. Keep the links intrusive, so a node and its pointers sit in one cache line instead of three separate allocations. None of this is exotic, but a candidate who reaches for it without being asked is saying they have written code that had to be fast for real, not fast on a slide.
The follow-ups that sort people
Top of book in O(1) comes first. Reading the best bid and ask should never search. Track the best level and fix it up on add and cancel. The mean version is cancelling the order sitting alone at the best price, because now you need the next-best level in a hurry, which a tree gives you for free and a bucket array needs a little care to do well.
Then matching. A marketable buy walks the ask side, taking liquidity at each level until it is filled or no crossing price is left, throwing off partial fills along the way. After that they push on the parts that actually hurt: locality across levels, what your branches do during a sweep, and how you would measure any of it instead of guessing.
Prompts you will actually hear
- Design an order book with add, cancel, and top-of-book, all better than O(n).
- Make cancel O(1). Now make top-of-book O(1) too.
- Walk me through what allocates in your add path, then remove it.
- The best bid is a single resting order and it cancels. What is your next read?
- Add marketable orders that match and produce partial fills.
Saying it well out loud
The candidates who do best narrate the cost model as they go. They state the complexity of each operation, call out where memory comes from, name the structure they would choose and why the alternative loses, and flag what they would profile before committing in production. They also own the shortcuts they take on a whiteboard, like skipping integer price scaling or self-trade checks, so the interviewer reads the omission as a decision rather than a gap.
That habit carries more weight than any single data structure. A trading firm is hiring someone who will reason about latency and memory under pressure, with real money on the other side of every choice. The order book is just the cleanest way they have found to watch you do it.