Limit Order Book & Matching Engine

You already received the conceptual brief earlier — what an order book is, the two sides, price-time priority, the three operations, matching, market orders, integer prices. This page turns that into a precise, buildable specification. Keep it open in one pane and your editor in the other.

1 · The data model

Define plain structs for the data and a class for the book (Module 04: structs for data, class for invariants).

enum class Side { Buy, Sell };
enum class OrderType { Limit, Market };

struct Order {
    uint64_t   id;          // unique
    Side       side;
    OrderType  type;
    int64_t    price;       // in ticks/cents; 0 for market
    uint32_t   quantity;    // original size
    uint32_t   filled;      // amount executed so far
    uint64_t   timestamp;   // for time priority
    uint32_t remaining() const;   // quantity - filled
};

struct Trade {
    uint64_t buy_order_id;
    uint64_t sell_order_id;
    int64_t  price;         // the RESTING order's price
    uint32_t quantity;
    uint64_t timestamp;
};

2 · The container choices (justify each)

These are the decisions an interviewer will drill you on. You must be able to defend every one (Module 07).

• Bids: std::map<int64_t, PriceLevel, std::greater<int64_t>> — highest price at begin().
• Asks: std::map<int64_t, PriceLevel> — lowest price at begin().
• Each price level: a FIFO queue of resting orders in a std::list — stable addresses, O(1) erase.
• ID index: std::unordered_map<uint64_t, /*location*/> — O(1) cancel-by-id.

3 · The three operations

add_order

1. If it's a limit order, first try to match it against the opposite side (see below).
2. If any quantity remains after matching, insert the remainder as a resting order: find/create its price level, append to the level's list, and record its location in the id index.
3. A market order matches greedily against the opposite side and is never rested; if the opposite side empties first, the unfilled remainder is cancelled/rejected (your choice — document it).

cancel_order

1. Look up the id in the index (O(1)). If absent, return false.
2. Erase the order from its price level's list (O(1) via the stored iterator/pointer).
3. If the level is now empty, erase the level from the map. Remove the id from the index.

match (the engine)

1. A buy at price P can trade against asks with price ≤ P; a sell at price P against bids with price ≥ P.
2. Walk the opposite side from begin() (best price). At each level, fill orders front-to-back (time priority).
3. Each fill: quantity = min(incoming.remaining(), resting.remaining()). Emit a Trade at the resting order's price. Update both filled counts.
4. Remove fully filled resting orders (and empty levels). Stop when the incoming order is filled or no acceptable price remains.

4 · Market-data interface

After any operation the book must answer, cheaply:

• best_bid(), best_ask() — begin() of each map (or empty).
• spread() — best_ask − best_bid.
• depth_at(price) — total resting quantity at a level.
• top_n(n) — the top N levels per side for a snapshot.

5 · Project layout

orderbook/
├── CMakeLists.txt
├── include/
│   ├── order.h          // Order, Trade, enums
│   ├── price_level.h    // FIFO list at one price
│   └── order_book.h     // the book + matching engine
├── src/
│   ├── order_book.cpp
│   └── main.cpp         // hardcoded scenarios that print trades
├── test/
│   └── test_order_book.cpp   // correctness checks
└── bench/
    └── benchmark.cpp    // throughput + p50/p95/p99

6 · Test plan (prove it's correct before you optimize)

• Add a resting buy, then a crossing sell → one trade at the resting price, correct quantities.
• Partial fill: incoming larger than resting → resting removed, incoming rests with remainder.
• Multiple levels: a large order sweeps several price levels in the right order.
• Time priority: two orders at the same price fill in arrival order.
• Cancel: add then cancel; confirm it no longer matches and the level is cleaned up.
• Empty-book market order: handled per your documented policy.
• Run the whole suite under -fsanitize=address,undefined — zero errors.

7 · The benchmark

• Generate 1,000,000 random operations (mostly adds, some crossing, some cancels).
• Time the batch: report ns/op and ops/sec.
• Record per-op latencies, sort, and print p50/p95/p99.
• Put the numbers and your CPU/OS/compiler flags in the README.

8 · README checklist (what the recruiter reads)

• One-paragraph description: what it is, what it does.
• Build instructions (cmake -S . -B build && cmake --build build).
• The design decisions section: why map, why list, why unordered_map — in your words.
• Benchmark results with hardware.
• "Verified under AddressSanitizer and UBSan."