Order Book And Matching Engine Data Structures

What's being tested

These problems test building an efficient, order book and matching engine for a single symbol: maintaining side-specific best prices, aggregating quantities, and deterministic tie-breaking. Interviewers probe algorithmic choices, data-structure invariants, and correctness under inserts, cancels, modifies, and matches.

Patterns & templates

• Use a price-level map implemented with a balanced tree (std::map) for best-price lookup — best bid/ask in O(log P) where P is active price levels.
• Maintain a per-price FIFO queue (e.g., deque or linked list) to enforce price-time priority and O(1) head pops for fills.
• Keep an unordered_map<orderId, Node*> for direct cancel/modify in O(1) to the order's node and price-level.
• Store aggregated volume per price-level and update on every insert/modify/cancel to answer quantity-at-price in O(1).
• Matching loop: while best-opposite-price exists and top-order.qty > 0, consume min(taker.qty, maker.qty); operations are O(matches * 1) amortized.
• For order modification, treat as cancel+reinsert if price changes to preserve time priority; otherwise update quantity in-place.
• Memory is linear: orders -> O(N); price-levels typically << N; consider node pooling to avoid GC/allocator overhead.

Common pitfalls

Pitfall: Forgetting to decrement the price-level aggregated quantity on cancel leads to incorrect depth and stale best-price decisions.

Pitfall: Using a binary heap for best-price with mutable orders complicates modify/cancel operations and makes O(n) removal common.

Pitfall: Re-inserting a modified order without clarifying whether it should preserve original time priority — always state the assumption and implement accordingly.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.