# The limit order book question every trading interview reaches

Source: https://www.techinterview.org/post/3233477310/limit-order-book-matching-engine-interview/
Updated: 2026-08-11 · techinterview.org

Sit through enough onsite loops at Optiver, IMC, Da Vinci, Citadel Securities, or Jane Street and one problem shows up in some form: build an in-memory limit order book that accepts orders, matches them, and lets you cancel fast. The prompt sounds like a warmup. It isn't. The interviewer is watching whether you reach for a TreeMap because it's the textbook answer, or because you actually thought about where the time goes.

The rules of the book are simple enough to state in a sentence. Buy orders (bids) and sell orders (asks) rest at price levels. An incoming order matches against the opposite side, best price first, and within a single price level the oldest resting order fills first. That's price-time priority, and almost every lit equity and futures venue runs some version of it. Get the two-line spec wrong and nothing after it matters, so say it back to the interviewer before you touch a data structure.

## The structure interviewers expect you to land on

Start with the shape of the data. Each side of the book is a collection of price levels, and each price level holds a queue of resting orders in arrival order. So you need something that keeps price levels sorted, to find the best bid and best ask, and something that preserves time order inside a level, to know who fills first.

The answer most people give: a sorted map from price to a level, with a FIFO queue at each level. In C++ that's `std::map<Price, Level>`; in Java a `TreeMap`. Best bid is the last key, best ask is the first key, both reachable in O(log P) where P is the number of distinct price levels. Appending to a level is O(1) at the tail. That answer is correct, and at a lot of firms it clears the first cut.

Then the interviewer asks about cancels, and the textbook answer starts to wobble. In a real book, cancels and modifies outnumber trades by an order of magnitude. Most resting orders never fill; they get pulled. If a cancel means scanning a queue to find the order, you've built something that degrades exactly where the load is. So you add a hash map from order id to the order's node, and you make each per-level queue an intrusive doubly linked list. Now a cancel is a hash lookup plus an O(1) unlink. That one follow-up, how do you cancel, is the whole point of the question at most desks.

## Why an array beats the tree for equities

Once you have the map-based version working, a sharp interviewer pushes on latency. `std::map` is a red-black tree: pointer chasing, cache misses, a node allocation every time a new price level appears. On a hot path measured in hundreds of nanoseconds, that hurts.

For instruments with a fixed tick size and a bounded price range, which covers most equities and futures, you don't need a tree at all. Prices are discrete. Convert price to an integer number of ticks and index a flat array of price levels directly. Best bid and best ask become a pair of moving indices you nudge as levels empty and fill. Lookup and insert are O(1), the memory is contiguous, and both the cache and the branch predictor like it. The tradeoff is memory: you pre-allocate levels across a range you mostly won't touch, and a name that can gap hard needs a plan for prices outside the array, usually a slower map as a fallback or a rebasing scheme. Saying that tradeoff out loud is what separates a memorized answer from an understood one.

This is also the moment to admit what a plain array can't do. Options with thousands of strikes, or crypto pairs with no tick constraint and prices spanning many orders of magnitude, break the flat-array assumption. There the map, or a hybrid that keeps a dense array near the touch and a map for the tails, earns its place.

## The matching loop, and the order types that complicate it

Matching is a loop, not a lookup. An aggressive order walks the opposite side from the best price inward, filling resting orders until it runs out of quantity or the price no longer crosses. A resting order that fully fills gets unlinked; one that partially fills has its remaining quantity decremented in place, keeping its time priority. If the incoming order still has quantity left and it's a limit order, whatever remains rests in the book as passive liquidity.

Order types are where interviewers probe whether you've seen a real venue:

- Market order: take the best available price and keep walking levels until filled, never rest.

- Limit order: match up to your limit price or better, rest the remainder.

- Immediate-or-cancel (IOC): fill what's available right now, drop the rest instead of resting it.

- Fill-or-kill (FOK): fill the entire quantity in one shot or do nothing, which means you confirm available size before committing any fill.

FOK is the one people trip on, because it forces a two-pass mindset: you can't start filling and then discover you can't complete. Either you scan first to confirm the size is there, or you stage the fills and roll them back if the total comes up short. Interviewers like it because it exposes whether you're thinking transactionally.

## Complexity, stated so it's quotable

| Order book operation | Backing structure | Time complexity | Why it's built that way |
| --- | --- | --- | --- |
| Find best bid or best ask | Moving index into a price-tick array, or a sorted map of price levels | O(1) with the array; O(log P) with a tree | The touch is read on every incoming order, so it has to stay cheap |
| Add a resting limit order | Append to the tail of that level's FIFO queue | O(1) amortized | Preserves time priority within the price level |
| Cancel a resting order | Hash map from order id to node, then unlink from an intrusive doubly linked list | O(1) | Cancels dominate volume; a linear scan would fall over under load |
| Match an aggressive order | Walk opposite-side levels from the touch inward | O(levels crossed + orders filled) | Cost tracks how far the order sweeps, not the size of the book |
| Reduce quantity on a resting order | Decrement in place at the existing node | O(1) | Shrinking keeps queue position; raising quantity does not |

P is the number of distinct price levels. Notice cancel is the operation that has to be O(1); it's the most frequent thing the book does. A candidate who tunes match throughput but leaves cancel as a linear scan has optimized the wrong end.

## The follow-ups that actually decide the score

Concurrency is the big one. The instinct is to reach for locks so multiple threads can hit the book. The production answer at most low-latency shops is the opposite: one book per symbol, one thread, no shared mutable state on the hot path. A single matching thread per instrument sidesteps a whole category of ordering bugs, and it makes the sequence of events deterministic, which matters for replay and audit. You scale out by sharding symbols across cores and machines, not by piling threads onto one book. Propose a giant lock around a shared book and you signal you haven't seen how these systems get built.

Self-trade prevention comes up next. If the same participant has a resting bid and sends a crossing ask, exchanges won't let them trade with themselves; the engine cancels one side or skips it. Small rule, real consequences for how the match loop treats the order it's about to fill.

Order modification is a quiet trap. Changing price, or increasing quantity, loses time priority: the venue treats it as cancel-and-new, so the order goes to the back of the new level's queue. Reducing quantity usually keeps your place. If a candidate models a modify as an in-place edit that preserves priority for a price change, that's a correctness bug an interviewer will catch.

The last recurring thread is sequencing. Every order gets a monotonic sequence number on entry, and that number, not the wall clock, is what breaks ties and drives replay. Wall clocks drift and don't have the resolution you need at these rates. Grounding time priority in a sequence counter rather than a timestamp is a small detail that tells an experienced interviewer you've thought about the machine the code runs on, not only the algorithm.

## How the question is actually staffed

At a market maker like Optiver or IMC the order book tends to be a 45-to-60-minute coding round where you build a working version in C++ or Python, and the grade lands about half on correctness and half on the follow-up discussion about cancels and latency. At Citadel Securities or Jane Street it's more often folded into a systems design conversation where the coding is lighter but the questions on concurrency, sharding, and market-data fan-out go deeper. HRT and Jump lean hardware and kernel bypass, so the book itself can be a stepping stone into how the match result gets published to a multicast feed with minimal jitter.

A few of the prompts, phrased close to how they land in the room:

- "Implement add, cancel, and match for a single-symbol book. Now make cancel O(1)."

- "Your book uses std::map and we're seeing p99 latency spikes on busy names. What changes?"

- "Two orders arrive at the same price in the same microsecond. Which fills first, and how does your code decide?"

- "A market order sweeps five levels. Walk me through every allocation and cache miss on that path."

The people who do well treat the book as a living system with a clear hot path, not a puzzle to solve once and forget. They name the tradeoff behind every structure they pick, they know cancel is the operation under load, and when asked to make it faster they reach for contiguous memory and a single thread before they reach for anything clever. Build it that way and the follow-ups stop being traps and start being a conversation you're leading.