A matching engine must support add, cancel and match at the best price for a limit order book with price-time priority. State the data structure you would use for the price levels and for the queue inside a level, and give the complexity of each of the three operations under your choice.

A matching engine must support add, cancel and match at the best price for a limit order book with price-time priority. State the data structure you would use for the price levels and for the queue inside a level, and give the complexity of each of the three operations under your choice.

Approach: Separate the two access patterns: finding the best price, and finding one resting order by id. Then use the fact that traded prices live in a narrow band around the touch.

An array indexed by price tick holding one intrusive doubly linked list per level, plus a hash map from order id to node, giving O(1) add, O(1) cancel and O(1) amortised best-price lookup. Prices sit on a fixed integer tick grid, so the price level array turns a level lookup into a single offset computation rather than a tree descent. Each level holds a FIFO list, so adding at the back and matching from the front preserve price time priority in constant time. Cancel finds the node through the hash map and unlinks it in constant time, which is why the list must be doubly linked and intrusive. The best bid and offer are cached, and when a level empties the cached pointer walks outward one tick at a time, which is O(1) amortised because the touch moves a bounded number of ticks per event in a liquid book. A balanced tree of levels gives O(log n) everywhere and is the fallback when the tick range is too wide to index directly.

Follow-up: What changes when the instrument has no fixed tick grid and prices are arbitrary decimals?

Key concepts: price level array, intrusive doubly linked list, price time priority, hash map.