In-Memory Order Book with Price-Time Order, Level Aggregation and Order Cancel

Implement an in-memory order book for a single instrument. Orders arrive one at a time, each with a unique order id, a side (bid or ask), a price and a quantity. The book must: - keep the orders at each price in the order in which they arrived; - maintain the aggregated quantity resting at each price level on each side; - cancel any individual order by its id without disturbing any other order, including the arrival order of the orders around it. Treat the interface below as a starting point to confirm with the interviewer: ```cpp enum class Side { Bid, Ask }; class OrderBook { public: bool add(uint64_t order_id, Side side, int64_t price, uint64_t qty); bool cancel(uint64_t order_id); uint64_t level_quantity(Side side, int64_t price) const; // 0 if the level is empty std::vector<std::pair<int64_t, uint64_t>> depth(Side side, std::size_t levels) const; // best price first }; ``` The discussion is in C++ and goes into container choice, how the standard containers are implemented, and where memory is allocated. ### Clarifying Questions - Should an incoming order that crosses the spread (a bid at or above the best ask) trade against resting orders, or does the book only store orders? - Can an order's quantity be changed after it is added, and does a change lose its place in line? - How are prices represented: integer ticks or decimals? - What should `add` do with a duplicate id or a zero quantity, and what should `cancel` do with an unknown id? - How many price levels and resting orders should the book handle, and are there latency targets per operation? ### Part 1 — Add orders and aggregate levels Implement `add`, `level_quantity` and `depth`. Orders at the same price keep their arrival order, each side is ordered from its best price, and aggregated quantities are available without delay. ```hint Two orderings Orders need one ordering across prices and another within a price. Choose a container for each, and decide where the aggregated quantity lives so that a query does not have to walk every order. ``` #### What This Part Should Cover - Containers for price order and arrival order, with the complexity of each operation. - Incremental maintenance of each level's aggregated quantity. - A correct best-first order for bids and for asks. ### Part 2 — Cancel an order Implement `cancel`. It receives only an order id; it must remove that order, update the aggregate, and leave every other order exactly where it was. ```hint Find it without searching A cancel names only the order id. Think about what you would need to record at add time so that a cancel reaches the order directly and removes it without shifting its neighbors. ``` #### What This Part Should Cover - An index from order id to the order, and which handles stay valid as other orders come and go. - Removal without moving or invalidating other orders, and clean-up of levels that become empty. - The cost of cancel compared with the cost of add. ### What a Strong Answer Covers - Per-operation complexity for add, cancel, level queries and depth. - Invariants that hold after every operation: level totals, no empty levels, and a consistent id index. - Where memory is allocated on each operation, and how to reduce allocation and improve cache locality. - Input validation and behavior for duplicate or unknown ids. ### Follow-up Questions - Add matching: how does an aggressive order consume resting liquidity in price-time priority with your structures? - Where does your design allocate memory on each operation, and how would you take allocation off the hot path? - If prices always fall within a narrow band of ticks, what could replace the ordered map, and how would you track the best price? - How would you support reducing an order's quantity without losing its place in line?