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

Problem Description

Design and implement an in-memory, single-instrument limit order book that supports live order matching at scale. Orders must match upon arrival using price–time priority, with support for partial fills, market orders, and cancellations. The system should be efficient enough to handle up to 1 million (1e6) live resting orders and approximately 100,000 (1e5) operations per second.

To support deterministic self-trade prevention, assume each order includes a traderId (accountId). If your chosen interface omits traderId, 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(): Returns the best bid and best ask as (price, totalQuantity).
4. depth(k): Returns the top k price levels on each side as lists of (price, totalQuantity), best-first.

Matching Rules

• Price–time priority: Within each price level, orders are matched on a First-In, First-Out (FIFO) basis by arrival time.
• Aggressive matching: Incoming orders must match aggressively upon arrival.
• Partial fills: The system must support partial fills for orders.
• Order resting: The unfilled remainder of a LIMIT order rests on the book. MARKET orders never rest on the book.
• Market order sweep: MARKET orders sweep price levels until fully filled or the book is empty.
• Self-trade prevention: The incoming order must not trade against resting orders from the same traderId. Define a clear policy for this scenario (e.g., cancel resting order, cancel incoming order, or decrement incoming order).

Performance Targets

• Support up to 1 million (1e6) live resting orders.
• Handle approximately 100,000 (1e5) operations per second.
• Aim for O(log P) time complexity for placeOrder and cancelOrder, where P is the number of price levels.
• Achieve O(1) time complexity for topOfBook reads.
• No linear scans over orders for cancelOrder or best-price lookups.

Concurrency

• A single-threaded matching engine is acceptable for the initial design.
• Describe how to extend the design to multi-threading while preserving determinism.

Deliverables

• Specify the chosen data structures (e.g., price-indexed trees with FIFO queues per level).
• Implement the core APIs (clean, production-minded code is a plus).
• Analyze the time and space complexity of your solution.
• Explain strategies to remain robust under adversarial input patterns.