Order Book With Per-Exchange BBO and Cross-Exchange NBBO Queries

Design and implement an in-memory order book that aggregates resting quantity from several exchanges. Every record has an exchange name, a price, a quantity, and a side (bid or ask). The book must support three operations: - `add(exchange, price, quantity, side)` records quantity at one price level on one side of one exchange. - `get_exchange_bbo(exchange)` returns that exchange's best bid and offer (BBO): its highest bid price and its lowest ask price. - `get_nbbo()` returns the national best bid and offer (NBBO): the highest bid price and the lowest ask price across all exchanges. Implement the book in Python, then analyze the time complexity of every operation. ### Constraints and Clarifications - Quantity is aggregated per `(exchange, side, price)` level. Individual orders do not need their own identity. - A price level whose total quantity has dropped to zero is no longer part of the book and must not be reported as a best price. Unless the interviewer specifies another mechanism, assume `add` receives a signed quantity change, so a negative quantity reduces an existing level. - A side with no active levels has no best price; return `None` for that side. ### Clarifying Questions - How are cancellations and fills expressed: a negative quantity passed to `add`, a separate removal call, or an absolute quantity that overwrites the level? - May a level's total ever go below zero, and if not, should that input be rejected? - Should the BBO and NBBO include the aggregated size at the best price or the exchange quoting it, or only the prices? - Are prices exact tick values, or arbitrary floating-point numbers? - Roughly how many exchanges and active price levels per exchange should the design expect? ### Part 1 — Per-Exchange Book and BBO Design the structure kept for each exchange and implement `add` and `get_exchange_bbo`. A price level can empty long after other levels were added above or below it, so explain how you avoid a linear search to remove it from whatever structure orders the prices. ```hint Separate quantities from ordering Keep one structure that is authoritative for how much quantity rests at each price and another that only orders prices. Ask whether the ordering structure must be cleaned immediately when a level empties. ``` #### What This Part Should Cover - The data structures per exchange and side, and how the highest bid and lowest ask are each obtained. - Correct behavior for a level that empties and later becomes active again. - Behavior for an unknown exchange or an empty side. ### Part 2 — Cross-Exchange NBBO Implement `get_nbbo()` without rescanning every price level of every exchange on each call. Explain exactly which changes on one exchange must be reflected in the global view, and how the global view recognizes information that is out of date. ```hint Track only each exchange's top The NBBO depends only on each exchange's current best prices, and an exchange's best price can move in either direction. Think about what a global entry must store so it can be checked against the exchange it came from. ``` #### What This Part Should Cover - The global structure and what each of its entries stores. - When global entries are added, and how stale entries are detected and discarded. - A comparison with scanning every exchange's BBO on each query. ### Part 3 — Complexity Analysis Give the time complexity of `add`, `get_exchange_bbo`, and `get_nbbo`, and the space used by the whole book. Be precise about which bounds are worst-case and which are amortized. ```hint Follow one entry's lifetime Consider how many times a single ordering entry can be inserted and removed, and which operation should pay for its removal. ``` #### What This Part Should Cover - Worst-case versus amortized costs, with the argument behind the amortized bound. - How stale entries affect memory and how that growth could be bounded. - An alternative ordered structure and the situations in which it is preferable. ### What a Strong Answer Covers - Correct BBO and NBBO results for empty sides, levels that empty and refill, and equal prices on several exchanges. - Working, readable code in which the authoritative quantities and the ordering structures cannot produce inconsistent answers. - Complexity claims that match the code, with the amortization argument stated. - Attention to input problems such as floating-point price keys and invalid quantity changes. ### Follow-up Questions 1. How would you support cancelling or modifying individual orders identified by an order id? 2. How would you return the total size available at the NBBO price, aggregated across all exchanges quoting that price? 3. What changes if one thread updates the book while many threads query it? 4. How would you detect and report a locked or crossed market, where the NBBO bid is greater than or equal to the NBBO ask?