In-Memory Limit Order-Matching Engine (Limit Order Book)

Context

You are asked to design and implement an in-memory, single-instrument limit order book that supports live order matching at scale. Orders match on arrival using price–time priority, with support for partial fills, market orders, and cancellations. The system should be efficient enough to handle up to 1e6 live resting orders and ~1e5 operations per second.

To support self-trade prevention deterministically, assume each order includes a traderId (accountId). If traderId is omitted in your chosen interface, briefly justify an alternative.

Requirements

• Core APIs
  1. placeOrder(orderId, traderId, side, price, quantity, type)
     • side ∈ {BUY, SELL}
     • type ∈ {LIMIT, MARKET}
     • price is ignored for MARKET orders
  2. cancelOrder(orderId)
  3. topOfBook(): return best bid and best ask as (price, totalQuantity)
  4. depth(k): return top k price levels on each side as lists of (price, totalQuantity), best-first
• Matching Rules
  • Price–time priority within each price level (FIFO by arrival).
  • Match aggressively upon arrival; allow partial fills.
  • Unfilled remainder of a LIMIT order rests on the book; MARKET orders never rest.
  • MARKET orders sweep price levels until filled or the book is empty.
  • Prevent self-trade: the incoming order must not trade against resting orders from the same traderId. Define a clear policy (e.g., cancel resting, cancel incoming, or decrement incoming).
• Performance Targets
  • Up to 1e6 live resting orders, ~1e5 ops/sec.
  • Aim for O(log P) insert/cancel where P = number of price levels.
  • O(1) top-of-book read.
  • No linear scans over orders for cancel or best-price lookup.
• Concurrency
  • Single-threaded matching engine is acceptable.
  • Describe how to extend to multi-threading while preserving determinism.
• Deliverables
  • Specify data structures (e.g., price-indexed trees with FIFO queues per level).
  • Implement core APIs (clean, production-minded code is a plus).
  • Analyze time/space complexity.
  • Explain strategies to remain robust under adversarial input patterns.