Systems design round for trading engineers.
Design a limit order book
The question
What data structures would you use for a limit order book that must add, cancel and match quickly?
Have a go before you open the solution. If you are stuck after a few minutes, the first paragraph below is usually enough of a nudge.
Show the worked solution
The answer
Price levels in a sorted structure or an array indexed by tick, each level a doubly linked list of orders, plus a hash map from order id to node.
Most activity happens at or near the best bid and offer, so the structure must make best-price access and cancellation O(1) rather than optimise the general case.
Represent each price level as a FIFO doubly linked list so a match takes from the head in constant time and price-time priority is preserved.
Hold a hash map from order id to its list node so a cancel is a constant-time unlink instead of a search.
For the price levels themselves, a fixed array indexed by tick beats a tree when the price range is bounded, because it turns level lookup into an index. Mention memory layout and cache behaviour: it is a large part of why real books are built this way.
What it is testing
Whether you optimise for the real access pattern rather than asymptotics alone.
Try these next
Maximum drawdown in one pass
Warm-upGiven an array of prices in time order, compute the maximum drawdown in a single pass.
Rolling median of a stream
HardMaintain the median of the last k values of a stream efficiently.
Sample from a stream of unknown length
StandardPick one element uniformly at random from a stream whose length you do not know in advance, using constant memory.
Why the loop order matters
StandardTwo implementations of matrix multiplication have identical complexity but one runs several times faster. Why?
Preparing properly
Live opportunities
Interviewing soon? See who is hiring
Open vacancies we track at quant firms, grouped by role and city. Adverts are anonymised.
Hiring for these roles? Brief the desk on a hire or check your fit for a role.
Research desk
Speak to a quant market specialist
Ask what a firm really pays, how a desk hires, or where your profile sits. One reply from the research desk, in confidence, no obligation.