Maintain Price Levels For A Single-Symbol Order Book

Problem Statement

Design a data structure for maintaining active price levels in an order book for a single financial instrument. The order book supports two sides: BUY (bids) and SELL (asks).

Each order has a unique integer order_id, a side ('BUY' or 'SELL'), a positive integer price, and a positive integer quantity.

Implement the OrderBook class with the following methods:

• __init__(): Initializes an empty order book.
• add_order(order_id: int, side: str, price: int, quantity: int) -> bool: Inserts a new order into the book. Returns True if successfully inserted, or False if an order with order_id already exists.
• modify_order(order_id: int, new_quantity: int) -> bool: Updates the remaining quantity of an existing order. If new_quantity bool: Removes the order with the given order_id. Returns True if removed, or False if order_id does not exist.
• get_volume_at_price(side: str, price: int) -> int: Returns the total aggregate quantity currently available at the specified side and price. Returns 0 if there are no active orders at that level.
• get_best_bid() -> int | None: Returns the highest price among active BUY orders, or None if there are no buy orders.
• get_best_ask() -> int | None: Returns the lowest price among active SELL orders, or None if there are no sell orders.

Constraints

• 1 <= order_id <= 10^9
• side is either 'BUY' or 'SELL'
• 1 <= price <= 10^6
• 1 <= quantity, new_quantity <= 10^6
• At most 2 * 10^5 calls will be made in total across all methods.
• Operations should achieve O(log P) or O(1) time complexity, where P is the number of distinct price levels.

Example

book = OrderBook()
book.add_order(1, "BUY", 100, 10)    # Returns True
book.add_order(2, "BUY", 100, 15)    # Returns True
book.add_order(3, "BUY", 99, 20)     # Returns True
book.add_order(4, "SELL", 105, 5)    # Returns True

book.get_best_bid()                  # Returns 100
book.get_best_ask()                  # Returns 105
book.get_volume_at_price("BUY", 100) # Returns 25 (10 + 15)

book.modify_order(1, 5)              # Returns True (quantity reduced to 5)
book.get_volume_at_price("BUY", 100) # Returns 20 (5 + 15)

book.cancel_order(2)                 # Returns True
book.get_volume_at_price("BUY", 100) # Returns 5

book.cancel_order(1)                 # Returns True (100 price level now empty)
book.get_best_bid()                  # Returns 99

Edge Cases

• Canceling or modifying an order that does not exist should return False and not alter state.
• Adding an order with an ID that already exists should be rejected.
• When the last order at a price level is canceled or reduced to 0, that price level must be completely cleared so it no longer affects get_best_bid or get_best_ask.
• Book may be completely empty on one or both sides.