Citadel Intern Software Engineer Interview Experience — A Deep Dive on the Classic Orderbook Problem

This was my second round for the Citadel SWE intern process. The technical part was the classic orderbook problem.

The question was the classic orderbook problem.

Problem description: Design and implement an order book data structure that maintains order records containing the exchange name, price, quantity, and side (bid or ask). It needs to support three core APIs:

• add(exchange, price, quantity, side): add a new order record.
• get_exchange_bbo(exchange): get the BBO (Best Bid and Offer) for a given exchange — the best bid and best ask within that exchange.
• get_nbbo(): get the NBBO (National Best Bid and Offer) across the whole market — the best bid and best ask across all exchanges.

Data structure design and complexity analysis (my Python implementation approach):

Per-exchange order book design: Each exchange maintains two hash tables and two heaps.

A hash table (price_counts) tracks the total quantity at each price level within that exchange. A max-heap for bids (max_heap_bids) stores negative prices so the highest bid can be read off the top. A min-heap for asks (min_heap_asks) stores prices directly so the lowest ask can be read off the top.

Lazy deletion: When the quantity at a price level drops to 0, I don't do an expensive O(N) linear search-and-delete on the heap — I just update the count in the hash table. When get_exchange_bbo() looks at the top of the heap, if the price there has a count of 0 in the hash table, it keeps popping until it finds the first valid price.

Global NBBO maintenance: I keep two global heaps (global_max_heap_bids and global_min_heap_asks) holding (price, exchange) tuples. Whenever an exchange's local BBO (best bid or best ask) updates, the new (price, exchange) pair gets pushed onto the corresponding global heap.

Global lazy deletion: When get_nbbo() is called, it checks whether the (price, exchange) at the top of the global heap still matches that exchange's current local best price. If it's been superseded by a newer, better price, the stale top gets popped off, so the read comes back O(1) once the cleanup is amortized.

Time complexity:

• add(): O(1) for the hash table update, O(log K) for the heap push, where K is the number of price levels.
• get_exchange_bbo() and get_nbbo(): O(1) on average for the heap-top read, amortized over the lazy cleanup.