Maintain Price Levels For A Single-Symbol Order Book
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a simplified NASDAQ market data book for one symbol. You receive callbacks when orders are inserted, modified, or canceled. Each order has an id, side, price, and quantity. Implement `GetPriceLevel(side, level_index)`, where level 0 is the best price: highest price for buy orders and lowest price for sell orders. Return the price and total quantity at that price level.
Function signature:
```python
class OrderBook:
def on_order_insert(self, order_id: int, side: str, price: int, qty: int) -> None:
pass
def on_order_modify(self, order_id: int, price: int, qty: int) -> None:
pass
def on_order_cancel(self, order_id: int) -> None:
pass
def get_price_level(self, side: str, level_index: int) -> tuple[int, int] | None:
pass
```
Constraints:
- `side` is either `'buy'` or `'sell'`.
- Order ids are unique while active.
- Modifying an order may change both price and quantity.
- Canceling an unknown order should be handled gracefully or specified as invalid.
- If the requested level does not exist, return `None`.
Examples:
```text
Insert buy id 1 price 100 qty 5; insert buy id 2 price 101 qty 3. get_price_level('buy', 0) returns (101, 3).
```
```text
Insert sell id 3 price 105 qty 2; insert sell id 4 price 105 qty 7. get_price_level('sell', 0) returns (105, 9).
```
Quick Answer: Review a single-symbol order book implementation prompt with insert, modify, cancel, and price-level lookup callbacks. The interview topic focuses on side-specific best prices, aggregating quantities by price, active order tracking, and stateful API design.
Implement `simulate_order_book(operations)` for one symbol. Process the operations in order:
- `["insert", order_id, side, price, qty]` adds an active order.
- `["modify", order_id, price, qty]` changes an active order's price and quantity without changing its side.
- `["cancel", order_id]` removes an active order; an unknown id is ignored.
- `["get", side, level_index]` queries a price level. Level 0 is the best level: the highest buy price or lowest sell price.
For every `get`, append `[price, total_quantity]` for all active orders on that side and price. Append `None` when the level does not exist. Return the query results in order.
Constraints
- 0 <= len(operations) <= 200,000.
- Each side is either "buy" or "sell".
- Prices and quantities are positive integers.
- An inserted order id is unique among active orders; an id may be reused after cancellation.
- Every modify operation targets an active order and does not change its side.
- Canceling an unknown order id has no effect.
- level_index is a non-negative integer; return None when that level does not exist.
- Orders at the same side and price form one level whose quantity is their sum.
Examples
Input: ([["get", "buy", 0], ["get", "sell", 0]],)
Expected Output: [None, None]
Input: ([["insert", 1, "buy", 100, 5], ["insert", 2, "buy", 101, 3], ["get", "buy", 0], ["get", "buy", 1]],)
Expected Output: [[101, 3], [100, 5]]
Hints
- Keep enough per-order state to undo an order's old contribution during modify or cancel.
- Maintain buy and sell aggregates independently, and remove a price level when its total reaches zero.
- The ranking direction differs by side: descending for buys and ascending for sells.
- Consider the update/query trade-off of the structure that stores distinct active prices.