AdvancedMultiple choice
Designing an order book · Part 3 of 3
You are writing a limit order book for one instrument. It must add orders, cancel them by order id, and publish the best bid and offer after every event. There are L occupied price levels and N resting orders, and each level keeps its orders in time priority.
Prices stay within a known band, and nearly all activity is within a few ticks of the touch. When the best bid level empties, how do you find the new best bid fastest in practice?
- AKeep levels in an array indexed by tick and scan down from the old best to the next occupied slot
- BLook it up in a hash map from price to level
- CRe-sort the list of occupied prices after each change
- DPop from a binary heap of bid prices, which returns the new maximum in constant time with no upkeep
The worked solution is in Premium
The answer, the full working and the one idea to take away – for this and all 1,322 questions in the bank. Answer it in practice and your working is marked, with a known mistake named when you make one.
More systems and low latency questions
- An array-based book pre-allocates one slot per price tick.Foundation
- You join a price level behind 800 shares.Foundation
- You keep one million live orders in a hash map at 48 bytes an entry.Applied
- A buy order for 500 at a limit of $100.02 meets offers of 200 at $100.00, 100…Applied
- What data structure best supports a limit order book that must add, cancel and…Advanced
- A busy matching engine, part 1 of 3Foundation