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.

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.

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.

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.