Design a limit order book / matching engine

Question

Design a single-instrument matching engine supporting:

limit_order(side, price, qty), submit a buy or sell; it matches immediately against the opposite side at prices as good or better (price-time priority), and any unfilled remainder rests in the book. Return the new order id and the list of trades it generated.
cancel(order_id), remove a resting order.
best_bid() / best_ask(), the top of each book, or None.

b1 = ob.limit_order("sell", 101, 5)   # rests: ask 101 x5
b2 = ob.limit_order("sell", 102, 5)   # rests: ask 102 x5
ob.limit_order("buy", 103, 8)         # trades 5@101, 3@102; 0 remainder
ob.best_ask()  -> 102                 # 102 has 2 left

Every operation should be $O(\log n)$ amortized.

Accepted Answer

Keep asks in a min-heap keyed by (price, seq) and bids in a max-heap keyed by (-price, seq), where seq is a global counter giving time priority within a price level (smaller seq = earlier = matched first). Remaining quantity lives in a side dict qty[orderid]; a resting order is "cancelled" or "filled" simply by setting its quantity to 0. Because heaps can't remove interior elements, we clean lazily: whenever we peek the top, we first pop off any entries whose quantity is now 0. Matching a buy walks the ask heap while the best ask price is <= limit, trading min(incoming, resting) each step; th…

Design a limit order book / matching engine

Your answer

More Coding questions