Order Book Data Structure and Arbitrage Detection

Coding · Hard · Free problem

Design and implement an order book data structure that supports the following operations:

  1. Add order -- insert a new limit order (buy or sell) at a given price with a given quantity.
  2. Cancel order -- remove an existing order by its ID.
  3. Match orders -- when a new order arrives, match it against resting orders on the opposite side using price-time priority.
  4. Query best bid/ask -- return the current top-of-book on each side.

Your implementation should be optimized for low-latency trading. Discuss the time complexity of each operation and explain what data structures you would use.

Then extend the design to handle multi-venue arbitrage detection. Suppose you maintain order books for the same instrument across $N$ exchanges. How do you efficiently detect when $\text{best\_ask}_i < \text{best\_bid}_j$ for some pair of venues $i \neq j$, and what data structures or caching strategies make this fast?

Provide working code for the core single-venue order book, and describe the multi-venue extension in detail.

---

Required function: implement run_order_book(ops). ops is a list of ["add", id, side, price, qty], ["cancel", id], ["best_bid"], and ["best_ask"] commands. Return a list with one result per op: add returns the list of fills [maker_id, maker_price, qty], cancel returns a bool, and the best-bid/ask queries return a price or None.

Example

run_order_book([["add", 1, "sell", 100, 3], ["add", 2, "sell", 100, 2], ["add", 3, "buy", 100, 4], ["best_ask"]]) -> [[], [], [[1, 100, 3], [2, 100, 1]], 100]

The buy for 4 sweeps sell order 1 fully (3) then sell order 2 partially (1), producing the two fills; sell order 2 still rests with 1 unit left, so the best ask is 100.

Hints

  1. Think about what queries the order book must support: sorted-order access (best bid/ask, matching) and random-access mutation (cancel by ID). What combination of data structures gives you both?
  2. A sorted map (red-black tree or skip list) of price levels, each containing a FIFO queue, plus a hash map from order ID to its location, covers all the operations. Consider what further tricks exploit the discrete tick grid.
  3. For multi-venue arbitrage detection, you do not need to check all $O(N^2)$ pairs. Track the global minimum ask and global maximum bid -- an arbitrage exists if and only if the global best ask is below the global best bid from a different venue.

Worked Solution

How to Think About It: An order book balances two needs: sorted-order queries (best bid/ask, matching by price-time priority) and fast random-access mutation (cancel by order ID). The production answer pairs a sorted price-level structure with a hash map from order ID to order. For this problem the tape is small, so a single order dictionary scanned per operation is clear and correct.

The contract (what run_order_book(ops) must return). ops is a list of commands. The function returns a list with one result per op, in order:

  • ["add", id, side, price, qty] -> a list of fills. Each fill is [maker_id, maker_price, traded_qty], where maker_id/maker_price are the *resting* (maker) order that was hit. A buy crosses asks priced <= price; a sell crosses bids priced >= price. Matching uses price-time priority (best price first, earliest order first within a price) and trades execute at the resting order's price. Any unmatched incoming quantity rests on the book. No fills -> [].
  • ["cancel", id] -> True if a resting order with that id was removed, else False (unknown id, or an order that already fully filled).
  • ["best_bid"] -> the highest resting buy price, or None.
  • ["best_ask"] -> the lowest resting sell price, or None.

Code:

```python def run_order_book(ops): # Single-venue limit order book. Replays a tape of operations and returns # a list with one result per op. # # Ops: # ["add", id, side, price, qty] -> list of fills [maker_id, maker_price, qty] # ["cancel", id] -> bool (True if a resting order was removed) # ["best_bid"] -> highest resting buy price or None # ["best_ask"] -> lowest resting sell price or None # # Matching: an incoming order crosses the opposite side using price-time # priority (best price first, earliest order first within a price). Trades # execute at the RESTING (maker) order's price. Leftover incoming qty rests. orders = {} # id -> {"side","price","qty","seq"} seq = 0 results = []

def best_bid(): prices = [o["price"] for o in orders.values() if o["side"] == "buy"] return max(prices) if prices else None

def best_ask(): prices = [o["price"] for o in orders.values() if o["side"] == "sell"] return min(prices) if prices else None

for op in ops: kind = op[0]

if kind == "add": _, oid, side, price, qty = op seq += 1 fills = [] remaining = qty

if side == "buy": # match against asks with price <= incoming price def resting_asks(): return sorted( (o for o in orders.values() if o["side"] == "sell"), key=lambda o: (o["price"], o["seq"]), ) while remaining > 0: candidates = [o for o in resting_asks() if o["price"] <= price] if not candidates: break maker = candidates[0] traded = min(remaining, maker["qty"]) fills.append([maker["id"], maker["price"], traded]) maker["qty"] -= traded remaining -= traded if maker["qty"] == 0: del orders[maker["id"]] else: # sell def resting_bids(): return sorted( (o for o in orders.values() if o["side"] == "buy"), key=lambda o: (-o["price"], o["seq"]), ) while remaining > 0: candidates = [o for o in resting_bids() if o["price"] >= price] if not candidates: break maker = candidates[0] traded = min(remaining, maker["qty"]) fills.append([maker["id"], maker["price"], traded]) maker["qty"] -= traded remaining -= traded if maker["qty"] == 0: del orders[maker["id"]]

if remaining > 0: orders[oid] = { "id": oid, "side": side, "price": price, "qty": remaining, "seq": seq, } results.append(fills)

elif kind == "cancel": oid = op[1] if oid in orders: del orders[oid] results.append(True) else: results.append(False)

elif kind == "best_bid": results.append(best_bid())

elif kind == "best_ask": results.append(best_ask())

else: raise ValueError("unknown op: %r" % (kind,))

return results ```

Intuition

The order book problem is really about combining two incompatible access patterns into one structure. Sorted containers are great for price-priority matching but terrible for cancel-by-ID. Hash maps are great for cancel-by-ID but have no ordering. The classic solution -- a tree of queues plus a hash map -- is the textbook answer, but the real insight for production systems is that financial prices are discrete. When prices live on a tick grid, you can replace the $O(\log P)$ tree with an $O(1)$ array lookup, which is a massive win at the latency scales that matter in HFT.

The multi-venue arbitrage extension illustrates a general principle in systems design: reduce a seemingly $O(N^2)$ problem to $O(1)$ by maintaining sufficient statistics (the global best bid and ask). This same pattern shows up everywhere in trading -- you rarely need to compare all pairs of anything if you track the right extremes. In practice, the hard part is not the data structure design but the engineering: lock-free concurrency, cache-line alignment, kernel bypass networking, and managing the gap between when you detect an arbitrage and when you can actually execute it.

Related problems

Open the full interactive solver →