This question evaluates a candidate's ability to design a high-throughput, low-latency in-memory limit order-matching engine, testing competencies in data structure selection, algorithmic complexity, deterministic concurrency, API design, and handling domain-specific constraints such as self-trade prevention.
Design and implement an in-memory order-matching engine for a limit order book.
Requirements:
- Operations:
- placeOrder(orderId, side, price, quantity, type) where side ∈ {BUY, SELL} and type ∈ {LIMIT, MARKET}
- cancelOrder(orderId)
- topOfBook(): return best bid and best ask (price, totalQuantity)
- depth(k): return top k price levels on each side
- Matching rules: price–time priority; match immediately on arrival; allow partial fills; leave remainders on the book; market orders sweep the book until filled or empty; prevent self-trade.
- Performance targets: support up to 1e6 live orders and ~1e5 ops/sec; aim for O(log P) insert/cancel and O(
1) top-of-book; avoid linear scans over orders.
- Concurrency: single-threaded matcher is acceptable; describe how you would extend to multi-threading without breaking determinism.
Deliverables: specify data structures (e.g., price-indexed maps with FIFO queues), implement core APIs, analyze time/space complexity, and explain strategies to prevent timeouts on adversarial inputs.
Quick Answer: This question evaluates a candidate's ability to design a high-throughput, low-latency in-memory limit order-matching engine, testing competencies in data structure selection, algorithmic complexity, deterministic concurrency, API design, and handling domain-specific constraints such as self-trade prevention.
In-Memory Limit Order-Matching Engine (Limit Order Book)
Context
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 engine must be efficient enough to sustain up to 106 live resting orders and roughly 105 operations per second.
To support self-trade prevention (STP) deterministically, assume every order carries a traderId (account id). If you choose an interface that omits traderId, briefly justify an alternative for identifying same-account liquidity.
This is a hands-on design-and-build exercise: you are expected to specify concrete data structures, implement the core APIs, and reason precisely about complexity and robustness — not just sketch boxes and arrows.
Constraints & Assumptions
Single instrument (one symbol) per engine instance.
Up to
106
live resting orders; target throughput ~
105
ops/sec.
price
and
quantity
are bounded positive integers (you may assume integer ticks and lots).
A single-threaded matcher is acceptable for the core; you will be asked separately how to scale out.
State whether you assume a bounded price domain — it changes the optimal data structure (see Part 5).
Clarifying Questions to Ask
Are prices and quantities integers (ticks/lots), or do I need to handle decimal prices? (This determines whether floating point can ever enter the matcher.)
At what price does a trade print — the resting (maker) price or the incoming (taker) price?
Is the price domain bounded to a known tick range, or effectively unbounded? (Bounded enables an array-of-levels design.)
What is the required behavior for an unfilled MARKET remainder and for an unfilled LIMIT remainder?
Which self-trade-prevention policy is expected by default (cancel resting, cancel incoming/taker, or decrement both), and is it per-account configurable?
Is
cancelOrder
on an unknown or already-filled id an error or a no-op?
What are the read-vs-write ratios and the latency SLO for
topOfBook
/
depth
queries relative to matching?
topOfBook()
— return the best bid and best ask as
(price, totalQuantity)
.
depth(k)
— return the top
k
price levels on each side as lists of
(price, totalQuantity)
, best-first.
Specify the return types (including how fills/trades are reported from placeOrder) and the behavior on invalid input (duplicate orderId, non-positive quantity/price, cancel of an unknown id).
Part 2 — Matching rules
Implement matching with these semantics:
Price–time priority
within each price level (FIFO by arrival).
Match
aggressively on arrival
; allow
partial fills
.
The unfilled remainder of a
LIMIT
order rests on the book;
MARKET
orders never rest.
A
MARKET
order sweeps price levels until filled or the book is empty.
State the price at which fills print and keep it consistent.
Part 3 — Self-trade prevention (STP)
The incoming order must not trade against resting orders from the same traderId. Choose and clearly define a policy (e.g., cancel resting, cancel incoming/taker, or decrement both), make it deterministic, and explain its trade-offs.
Part 4 — Performance targets & complexity
Meet these targets and justify them with analysis:
Up to
106
live resting orders, ~
105
ops/sec.
O(log P)
to insert or remove a
price level
, where
P
= number of distinct price levels.
O(1)
to locate and remove an individual order by id — the per-level cost of a cancel, with the
O(logP)
term applying only when a cancel (or insert) creates or empties a level.
O(1)
top-of-book read.
No linear scans
over orders for cancel or best-price lookup.
Be explicit about which operations are O(1), which are O(logP), and when each cost is incurred. Provide a time/space complexity table for each API, naming the variables you use.
Part 5 — Concurrency & determinism
A single-threaded matching engine is acceptable for the core. Describe how you would extend toward multi-threading while preserving determinism (i.e., the same ordered event stream always yields the same trades).
Part 6 — Robustness under adversarial input
Explain the strategies that keep the engine within its targets under hostile workloads, and name the specific failure modes you are defending against.
Deliverables
Specify your data structures (e.g., price-indexed ordered map with FIFO queues per level, plus an id index).
Implement the core APIs (clean, production-minded code is a plus).
Analyze time and space complexity (Part 4).
Explain your strategies for remaining robust under adversarial input (Part 6).
Follow-up Questions
How does the design change if the price domain is
bounded
to a known tick range? What data structure would you swap in, and what does it cost?
Under a deep market sweep against thousands of thin levels, a single event's work is proportional to the levels crossed. If you have a hard per-event latency SLO, how do you bound that work without corrupting the book?
How would you add
IOC / FOK
order types, iceberg/hidden quantity, or stop orders on top of this core without rewriting the matcher?
How do you make the engine
crash-recoverable and auditable
— i.e., reconstruct the exact book state after a restart?
Note: this interview loop also included a separate pair-coding exercise — implement a ring buffer. It is a distinct deliverable from the matching engine above, though the same structure underpins a single-producer/single-consumer ingress sequencer (Part 5).