blog-cover-image

Quant Assessment Question from Citadel

Quantitative assessment coding questions are a core component of interviews at top hedge funds and proprietary trading firms like Citadel. These questions test not only your coding skills but also your understanding of financial market concepts, efficiency in data structures, and problem-solving in real-world trading scenarios. In this article, we will solve and deeply explain a representative Citadel quant assessment question about constructing an order book and efficiently computing the Best Bid and Offer (BBO) and the National Best Bid and Offer (NBBO). We will go step by step through the concepts, data structures, and code implementation, as well as optimize for real-scale usage.

Understanding the Problem: Order Book and BBO/NBBO

Order Book Basics

In electronic trading, an order book is a real-time list of buy and sell orders for a specific financial instrument, organized by price level. Each order has:

exchange_id: The exchange where the order was placed.
price: The price at which the order is placed (integer).
quantity: The number of units (positive integer).
order_type: Bid (buy) or ask (sell).

The order book allows traders to see the current market depth and liquidity at various price points.

Best Bid and Offer (BBO)

For any single exchange, the best bid is the highest price someone is willing to pay (buy), and the best ask (offer) is the lowest price someone is willing to sell at. This pair is called the exchange's Best Bid and Offer (BBO):

Best Bid: \( \max\{\text{all bid prices on the exchange}\} \)
Best Ask: \( \min\{\text{all ask prices on the exchange}\} \)

National Best Bid and Offer (NBBO)

The NBBO is the best bid and best ask across all exchanges:

NBBO Best Bid: \( \max\{\text{best_bid on each exchange}\} \)
NBBO Best Ask: \( \min\{\text{best_ask on each exchange}\} \)

If there are no bids or asks, the best bid or ask is reported as None.

Problem Requirements & Constraints

You are given a stream of order records from multiple exchanges. Each record contains the following fields:

exchange_id (string): Identifier of the exchange
price (integer): Price of the order
quantity (positive integer): Quantity of the order
order_type (string): Either "bid" or "ask"

Task

Implement a class OrderBook that supports the following operations:

1. `add(exchange_id, price, quantity, order_type)`

Adds a new order to the system.

2. `get_exchange_bbo(exchange_id)`

Returns the Best Bid and Offer (BBO) for a given exchange as:

(best_bid, best_ask)

best_bid: Highest bid price on the exchange, or None if no bids exist
best_ask: Lowest ask price on the exchange, or None if no asks exist

3. `get_nbbo()`

Returns the National Best Bid and Offer (NBBO) across all exchanges:

(best_bid, best_ask)

best_bid: Maximum of all exchanges’ best bids, or None if no bids exist
best_ask: Minimum of all exchanges’ best asks, or None if no asks exist

Constraints

Up to 200,000 add operations: High performance is required.
Up to 10,000 exchanges: Data structures must scale efficiently.
Efficient BBO/NBBO queries: Avoid full scans; use summary structures.
Order quantities are stored for extensibility, but do not affect BBO calculation here.
I/O Format: Each query is either:
- ADD exchange_id price quantity order_type
- EXBBO exchange_id
- NBBO
Output for EXBBO and NBBO must be: best_bid best_ask (with None for missing).

Conceptual Solution Approach

Key Data Structures

Given the constraints, we need data structures that handle frequent updates and queries efficiently:

Per exchange:
- Maintain a multiset or heap of bid prices and ask prices for each exchange.
- We only care about the max (for bids) and min (for asks) per exchange.
Across all exchanges:
- Maintain a summary of each exchange's current best bid/ask.
- Use a heap for all best bids and best asks (to compute NBBO efficiently).

Why Heaps?

Heaps allow for O(1) access to max/min and O(log N) updates.
We need to dynamically update best prices and quickly answer best bid/ask queries.
We must also efficiently update the NBBO when any exchange's BBO changes.

Important Considerations

We do not need to support deletion or modification of orders in this problem.
Multiple orders at the same price are allowed (hence, a multiset or counter is needed per price).
Quantity is only stored, not used in BBO/NBBO calculation.
Be careful with None cases—if an exchange has no bids or asks.
For large N/E, avoid O(N) or O(E) operations in query paths.

Step-by-Step Solution

1. Data Structures for Per-Exchange Order Book

For each exchange_id, we need to maintain:

A Counter (multiset) for all bid prices and all ask prices.
A max-heap for bid prices (to quickly get max).
A min-heap for ask prices (to quickly get min).

Each time we add an order, we insert its price into the appropriate heap and update the counter.

Python Implementation (Per Exchange)


from collections import defaultdict, Counter
import heapq

class ExchangeOrderBook:
    def __init__(self):
        self.bids = Counter()
        self.asks = Counter()
        self.bid_heap = []  # max-heap (use negative prices)
        self.ask_heap = []  # min-heap

    def add_bid(self, price):
        self.bids[price] += 1
        heapq.heappush(self.bid_heap, -price)
    
    def add_ask(self, price):
        self.asks[price] += 1
        heapq.heappush(self.ask_heap, price)

    def get_best_bid(self):
        # Remove stale prices (with count 0)
        while self.bid_heap and self.bids[-self.bid_heap[0]] == 0:
            heapq.heappop(self.bid_heap)
        if not self.bid_heap:
            return None
        return -self.bid_heap[0]

    def get_best_ask(self):
        while self.ask_heap and self.asks[self.ask_heap[0]] == 0:
            heapq.heappop(self.ask_heap)
        if not self.ask_heap:
            return None
        return self.ask_heap[0]

This structure ensures that adding an order and getting best bid/ask is O(log K), where K is the number of price levels currently in the book for that exchange.

2. Market-Wide BBO/NBBO Calculation

To efficiently compute the NBBO (National Best Bid and Offer), we need to track the current best bid and best ask for each exchange. When an exchange’s best price changes, we need to update the market-wide bests.

We can use two heaps:

Bid Max-Heap: Each entry is (-price, exchange_id).
Ask Min-Heap: Each entry is (price, exchange_id).

Whenever an exchange’s best bid or ask changes, push its new best price into the heap. When querying NBBO, pop stale entries (where the price does not match the current best for that exchange).

Python Implementation for NBBO


class OrderBook:
    def __init__(self):
        self.exchanges = defaultdict(ExchangeOrderBook)
        self.nbbo_bid_heap = []  # (-price, exchange_id)
        self.nbbo_ask_heap = []  # (price, exchange_id)
        self.exchange_best_bid = {}  # exchange_id -> price or None
        self.exchange_best_ask = {}

    def add(self, exchange_id, price, quantity, order_type):
        book = self.exchanges[exchange_id]
        if order_type == 'bid':
            book.add_bid(price)
        else:
            book.add_ask(price)
        # After adding, update the exchange's best bid/ask
        new_best_bid = book.get_best_bid()
        new_best_ask = book.get_best_ask()
        # If best bid changed, push the new best to NBBO heap
        if self.exchange_best_bid.get(exchange_id) != new_best_bid:
            self.exchange_best_bid[exchange_id] = new_best_bid
            if new_best_bid is not None:
                heapq.heappush(self.nbbo_bid_heap, (-new_best_bid, exchange_id))
        # If best ask changed, push to ask heap
        if self.exchange_best_ask.get(exchange_id) != new_best_ask:
            self.exchange_best_ask[exchange_id] = new_best_ask
            if new_best_ask is not None:
                heapq.heappush(self.nbbo_ask_heap, (new_best_ask, exchange_id))

    def get_exchange_bbo(self, exchange_id):
        book = self.exchanges[exchange_id]
        return (book.get_best_bid(), book.get_best_ask())

    def get_nbbo(self):
        # Best bid across all exchanges
        while self.nbbo_bid_heap:
            price, exid = self.nbbo_bid_heap[0]
            current = self.exchange_best_bid.get(exid)
            if current is not None and -price == current:
                return (current, self._get_nbbo_ask())
            # Stale entry
            heapq.heappop(self.nbbo_bid_heap)
        return (None, self._get_nbbo_ask())

    def _get_nbbo_ask(self):
        while self.nbbo_ask_heap:
            price, exid = self.nbbo_ask_heap[0]
            current = self.exchange_best_ask.get(exid)
            if current is not None and price == current:
                return price
            heapq.heappop(self.nbbo_ask_heap)
        return None

Full End-to-End Solution

Now, let's put together the complete code, including parsing the specified input/output format. We'll ensure that the solution is readable, efficient, and extensible for further trading simulation.


from collections import defaultdict, Counter
import heapq
import sys

class ExchangeOrderBook:
    def __init__(self):
        self.bids = Counter()
        self.asks = Counter()
        self.bid_heap = []  # max-heap (use negative price)
        self.ask_heap = []  # min-heap

    def add_bid(self, price):
        self.bids[price] += 1
        heapq.heappush(self.bid_heap, -price)

    def add_ask(self, price):
        self.asks[price] += 1
        heapq.heappush(self.ask_heap, price)

    def get_best_bid(self):
        while self.bid_heap and self.bids[-self.bid_heap[0]] == 0:
            heapq.heappop(self.bid_heap)
        return -self.bid_heap[0] if self.bid_heap else None

    def get_best_ask(self):
        while self.ask_heap and self.asks[self.ask_heap[0]] == 0:
            heapq.heappop(self.ask_heap)
        return self.ask_heap[0] if self.ask_heap else None

class OrderBook:
    def __init__(self):
        self.exchanges = defaultdict(ExchangeOrderBook)
        self.nbbo_bid_heap = []  # (-price, exchange_id)
        self.nbbo_ask_heap = []  # (price, exchange_id)
        self.exchange_best_bid = {}  # exchange_id -> price or None
        self.exchange_best_ask = {}

    def add(self, exchange_id, price, quantity, order_type):
        book = self.exchanges[exchange_id]
        if order_type == 'bid':
            book.add_bid(price)
        else:
            book.add_ask(price)
        # After adding, update the exchange's best bid/ask
        new_best_bid = book.get_best_bid()
        new_best_ask = book.get_best_ask()
        # If best bid changed, push the new best to NBBO heap
        if self.exchange_best_bid.get(exchange_id) != new_best_bid:
            self.exchange_best_bid[exchange_id] = new_best_bid
            if new_best_bid is not None:
                heapq.heappush(self.nbbo_bid_heap, (-new_best_bid, exchange_id))
        # If best ask changed, push to ask heap
        if self.exchange_best_ask.get(exchange_id) != new_best_ask:
            self.exchange_best_ask[exchange_id] = new_best_ask
            if new_best_ask is not None:
                heapq.heappush(self.nbbo_ask_heap, (new_best_ask, exchange_id))

    def get_exchange_bbo(self, exchange_id):
        book = self.exchanges[exchange_id]
        return (book.get_best_bid(), book.get_best_ask())

    def get_nbbo(self):
        # Best bid across all exchanges
        best_bid = None
        while self.nbbo_bid_heap:
            price, exid = self.nbbo_bid_heap[0]
            current = self.exchange_best_bid.get(exid)
            if current is not None and -price == current:
                best_bid = current
                break
            # Stale entry
            heapq.heappop(self.nbbo_bid_heap)
        best_ask = None
        while self.nbbo_ask_heap:
            price, exid = self.nbbo_ask_heap[0]
            current = self.exchange_best_ask.get(exid)
            if current is not None and price == current:
                best_ask = current
                break
            heapq.heappop(self.nbbo_ask_heap)
        return (best_bid, best_ask)

def main():
    input = sys.stdin.readline
    Q = int(input())
    ob = OrderBook()
    for _ in range(Q):
        parts = input().strip().split()
        if not parts:
            continue
        if parts[0] == 'ADD':
            _, exchange_id, price, quantity, order_type = parts
            ob.add(exchange_id, int(price), int(quantity), order_type)
        elif parts[0] == 'EXBBO':
            _, exchange_id = parts
            best_bid, best_ask = ob.get_exchange_bbo(exchange_id)
            print(f'{best_bid if best_bid is not None else "None"} {best_ask if best_ask is not None else "None"}')
        elif parts[0] == 'NBBO':
            best```python
            best_bid, best_ask = ob.get_nbbo()
            print(f'{best_bid if best_bid is not None else "None"} {best_ask if best_ask is not None else "None"}')

if __name__ == "__main__":
    main()
```

Explanation of the Complete Solution

Let’s break down the design choices and efficiency of this solution:

Adding Orders: For each ADD operation, we add the price to the appropriate heap and counter in O(log K), where K is the number of price levels for that order type (bid/ask) on the exchange.
Per-Exchange Best Bid/Ask: get_best_bid() and get_best_ask() pop any stale prices (prices with count 0—should not happen in this problem as we don't support deletions, but is extensible). This ensures the heap root always reflects the current best.
Exchange BBO Query: get_exchange_bbo() simply returns the best bid and ask for that exchange in constant time, after any stale entries are purged.
NBBO Query: We keep a global heap of all exchanges’ best bids and best asks, updating them when new orders change an exchange’s BBO. To answer NBBO, we pop stale entries until we find a price that matches the current best for that exchange.
Output: All BBO and NBBO outputs are formatted to print None where appropriate, as required.

This approach guarantees efficient operation even at the largest constraints (200,000 operations, 10,000 exchanges).

Sample Input and Output

Let’s see how the system works with an example:

Input	Output
7 ADD X1 100 10 bid ADD X1 105 5 ask ADD X2 101 7 bid ADD X2 106 8 ask EXBBO X1 EXBBO X2 NBBO	100 105 101 106 101 105

Let’s walk through the steps:

ADD X1 100 10 bid: X1’s best bid becomes 100
ADD X1 105 5 ask: X1’s best ask becomes 105
ADD X2 101 7 bid: X2’s best bid becomes 101 (higher than X1)
ADD X2 106 8 ask: X2’s best ask becomes 106
EXBBO X1: Output is 100 105
EXBBO X2: Output is 101 106
NBBO: Output is 101 105 (101 is max of best bids, 105 is min of best asks)

Math and Market Concepts in Depth

Why Use Max/Min for BBO/NBBO?

Best Bid:
- Represents the highest price a buyer is willing to pay.
- In trading, if you want to sell instantly, you “hit the bid” at this price.
- Hence, the BBO bid is: best_bid = max(bid_prices)
Best Ask:
- Represents the lowest price a seller is willing to accept.
- To buy instantly, you “lift the ask” at this price.
- BBO ask is: best_ask = min(ask_prices)
NBBO:
- Aggregates the best bids and asks from all exchanges.
- Mathematically:
  \( \text{NBBO best bid} = \max_{e \in \text{exchanges}} \{\text{best_bid on } e\} \)
  \( \text{NBBO best ask} = \min_{e \in \text{exchanges}} \{\text{best_ask on } e\} \)

Extensibility and Real-World Use

Quantities: We store order quantities for each price. In real trading, BBO might also depend on total size available at best price (e.g., depth), but for this problem, we only care about price.
Extending to Deletions: If supporting order cancellations, we’d decrement the counter, and pop stale heap entries as shown.
Order Matching: In a matching engine, we’d also need to remove matched quantities, but here, we just accumulate.

Time and Space Complexity Analysis

Time Complexity:
- ADD: O(log K) per heap insertion (K = unique price levels per exchange per side, typically very small).
- EXBBO: O(1) amortized (occasional heap pops, but only for stale entries).
- NBBO: O(log E) amortized (E = number of exchanges, as heaps may contain up to E stale entries).
Space Complexity:
- O(N) for all orders (N = number of adds), but only O(E) for exchange-level summaries and heaps.
- Each heap can have at most as many elements as price levels or exchanges.

Common Pitfalls and Optimizations

Stale Heap Entries: Since we can have multiple entries per exchange in the NBBO heaps, always check if the top of the heap matches the current best in the exchange’s BBO map before returning it.
Handling No Orders: Ensure None is returned/printed when there are no bids or asks (empty heaps).
Efficient Parsing: For large input sizes, use sys.stdin.readline for fast input.
Extensibility: Supporting deletions or more advanced order types (e.g., limit vs market) is straightforward by extending the counters and heap logic.

Conclusion

This Citadel quant assessment question tests your understanding of both financial markets (order books, BBO, NBBO) and efficient coding/data structure use (heaps, counters, maps). The solution combines these concepts to handle high-frequency, real-time order and price queries in a scalable way. Understanding and implementing such a system is key for quant trading, and the techniques here are directly applicable to real-world trading infrastructure.

By carefully structuring the order book with per-exchange heaps and counters, and market-wide summary heaps, we achieve both correctness and high performance—critical for competitive finance interview problems and real trading systems alike.