Order Book Data Structures And Market Data Aggregation

What's being tested

These problems test whether you can model an order book with the right data structures, preserve price-time priority, and answer best-price and quantity queries efficiently. You must reason about updates—add, cancel, replace, and trade—rather than only computing a snapshot from static rows. Citadel cares because market-data and execution components require predictable `p99` latency, deterministic behavior, correct handling of stale state, and clear complexity tradeoffs under high event rates.

Core knowledge

• A price level aggregates all live orders sharing (side, price): bids maximize price, asks minimize price. The BBO is $(\max \text{ bid prices}, \min \text{ ask prices})$, with missing sides represented explicitly.

• Use an ordered map such as `std::map` or a balanced red-black tree from price to level. Each insert, cancel-induced cleanup, and best-price lookup costs $O(\log P)$, where $P$ is the number of active price levels.

• For faster best-price access, combine a hash map of `order_id` → order with a price-level map. The hash map gives expected $O(1)$ cancellation lookup; the ordered structure locates and removes empty levels in $O(\log P)$.

• A price-time priority queue stores orders at each level in FIFO sequence, commonly with a linked list or deque. The level’s aggregate quantity is maintained incrementally, so total_quantity(price) is $O(1)$ rather than rescanning every order.

• A heap can provide fast best-price access, but cancellation is awkward because arbitrary removal is not efficient. Use lazy deletion: mark or remove orders in the authoritative map, then discard invalid heap tops while querying; understand possible memory growth and periodic rebuilding.

• For per-exchange aggregation, maintain state keyed by (exchange, side, price) and derive exchange BBOs separately. The NBBO is $\max_e(\text{best bid}_e)$ and $\min_e(\text{best ask}_e)$, while quantity is summed only across venues at the selected NBBO price.

• Cancellation requires an authoritative `order_id` index, not a scan through price levels. Store side, price, remaining quantity, exchange, and an iterator or node handle when possible; this supports $O(1)$ expected lookup and avoids disturbing neighboring orders.

• Event sequencing is part of correctness: apply add, cancel, replace, and execution events in feed sequence order. A duplicate or out-of-order event can double-count quantity unless sequence numbers, session resets, and idempotency rules are defined.

• Separate authoritative state from derived indexes. The order record or node owns lifecycle state; price totals, best-price caches, and heaps are derived structures that must be updated atomically with the mutation or rebuilt deterministically.

• In a single-writer design, one thread owns a symbol’s book and processes events sequentially, avoiding locks and making replay deterministic. Shard by symbol or instrument, not arbitrary events, because one book’s ordering must remain serialized.

• Define semantics before optimizing: whether quantities are integer lots or decimal values, whether prices use fixed-point ticks, how zero or negative quantities are rejected, and whether replace preserves time priority or receives a new timestamp.

Worked example

For “Compute BBO and NBBO from order data”, I would first clarify whether records are a snapshot or an event stream, whether orders can be canceled, whether exchange identity matters, and whether the output needs only prices or also aggregated quantities. I would declare fixed-point integer prices, nonnegative quantities, one sequential pass, and explicit behavior for an empty bid or ask side. I would organize the answer around parsing and validation, per-side/per-venue aggregation, best-price selection, and complexity plus edge-case handling. For a static snapshot, a hash map keyed by (venue, side, price) can accumulate quantities, followed by a best-price scan; for streaming updates, I would retain order IDs and incrementally maintain levels. The global NBBO would select the highest bid and lowest ask across venue-level BBOs, then sum quantities at the winning price where the specification requires it. A key tradeoff is a simple scan—$O(N)$ per query and low implementation risk—versus an ordered map or heap, which costs more state but supports frequent queries in $O(\log P)$ or near $O(1)$ best lookup. I would explicitly test duplicate IDs, zero quantities, empty books, multiple venues at one price, and a crossed book if validation forbids it. If I had more time, I would add property-based tests comparing the incremental implementation with a slow reference recomputation.

A second angle

For “In-Memory Order Book with Price-Time Order, Level Aggregation and Order Cancel”, the central challenge shifts from aggregating a completed dataset to preserving mutable lifecycle state. The design needs a sorted bid/ask view, FIFO order queues within each price, aggregate quantities, and direct cancellation by ID without changing other orders’ priority. A linked list plus ID-to-node index gives efficient arbitrary cancellation, while a tree or sorted map handles price levels. The interviewer may probe replace semantics, partial fills, empty-level deletion, and whether a canceled order can accidentally remain at the head of a lazy heap.

Common pitfalls

Pitfall: Analytical mistake. A tempting answer is “use a heap for each side and sum the top level when queried,” without explaining cancellation or stale entries. That can return incorrect BBOs or repeatedly scan dead orders; identify the authoritative record, lazy-deletion invariant, and worst-case cleanup behavior.

Pitfall: Communication mistake. Jumping straight to `TreeMap` or `unordered_map` obscures the required semantics. State assumptions first—snapshot versus stream, update types, price representation, and latency target—then map each requirement to a structure and give operation complexities.

Pitfall: Depth mistake. Saying “make it concurrent for low latency” is not enough and can introduce races in aggregate quantity and best-price state. Prefer a single-writer-per-symbol model, explain sharding and publication boundaries, and mention replay, sequence gaps, and deterministic recovery when persistence or failover is discussed.

Connections

The interviewer may pivot to matching-engine algorithms, event sourcing and replay, lock-free or single-writer concurrency, and market-data normalization. Be ready to distinguish an order book’s live derived state from an append-only audit log and to discuss fixed-point arithmetic, sequence gaps, and recovery snapshots.

Further reading

• Nasdaq TotalView-ITCH 5.0 — concrete feed-message semantics, sequence handling, order lifecycle events, and replay considerations.

• Designing Data-Intensive Applications by Martin Kleppmann — useful background on logs, deterministic processing, state reconstruction, and consistency tradeoffs.