How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Citadel during technical interviews.

Compute BBO and NBBO from order data | Citadel Coding Question

Quick Overview

This question evaluates a candidate's skill in designing efficient data structures and algorithms for aggregating and querying order-book data, including computing best bid/ask prices and summing quantities at those prices.

Compute BBO and NBBO from order data

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list `data` of order records. Each record is a 4-tuple: ``` (exchange_id, price, quantity, order_type) ``` - `exchange_id`: string/int identifying the exchange - `price`: positive number - `quantity`: positive integer - `order_type`: either `"B"` (bid/buy) or `"A"` (ask/sell) Implement a class `QuoteBook` initialized with `data`, supporting: 1. `get_exchange_bbo(exchange_id) -> (best_bid, best_ask)` - Returns the **best bid** and **best ask** for that exchange. 2. `get_nbbo() -> (best_bid, best_ask)` - Returns the **national best bid and offer (NBBO)** across *all* exchanges. Definitions: - **Best bid**: highest bid price. - **Best ask**: lowest ask price. - If there are multiple orders at the same best price on the relevant scope (exchange or all exchanges), treat the displayed quantity as the **sum of quantities at that best price**. - If a side does not exist (no bids or no asks), return `None` for that side. Return format: - `best_bid` and `best_ask` should each be either `None` or a tuple `(price, total_quantity_at_price)`. Constraints/expectations: - `len(data)` can be large (e.g., up to 10^5 or more), so repeated calls to these methods should be efficient.

Quick Answer: This question evaluates a candidate's skill in designing efficient data structures and algorithms for aggregating and querying order-book data, including computing best bid/ask prices and summing quantities at those prices.

You are given a static list of order records. Each record is a tuple (exchange_id, price, quantity, order_type), where order_type is either 'bid' or 'ask'. For each exchange, the BBO (Best Bid and Offer) is defined as the highest bid price and the lowest ask price on that exchange. If multiple orders exist at the same best price, their quantities must be summed. The NBBO (National Best Bid and Offer) is computed across all exchanges in the same way: highest bid price overall and lowest ask price overall, with quantities summed across all exchanges that share the winning price. For this problem, implement a function that builds the book once and answers a list of queries. A query is either ('exchange_bbo', exchange_id) or ('nbbo',). For each query, return a tuple (best_bid, best_ask), where each side is either (price, total_quantity) or None if that side does not exist.

Constraints

0 <= len(data) <= 200000
0 <= len(queries) <= 200000
exchange_id is a non-empty string
1 <= price <= 10^9
1 <= quantity <= 10^9
order_type is either 'bid' or 'ask'

Loading coding console...

Input: ([('X1', 100, 2, 'bid'), ('X1', 101, 3, 'bid'), ('X1', 101, 2, 'bid'), ('X1', 104, 1, 'ask'), ('X1', 103, 4, 'ask'), ('X1', 103, 5, 'ask'), ('X2', 99, 1, 'bid'), ('X2', 101, 6, 'bid'), ('X2', 102, 4, 'ask'), ('X2', 105, 2, 'ask'), ('X3', 101, 3, 'bid'), ('X3', 106, 1, 'ask')], [('exchange_bbo', 'X1'), ('exchange_bbo', 'X2'), ('nbbo',)])

Expected Output: [((101, 5), (103, 9)), ((101, 6), (102, 4)), ((101, 14), (102, 4))]

Explanation: X1 has best bid 101 with total quantity 5 and best ask 103 with total quantity 9. X2 has best bid 101 with quantity 6 and best ask 102 with quantity 4. Globally, the best bid price is 101 with quantities 5 + 6 + 3 = 14, and the best ask price is 102 with quantity 4.

Solution

def solution(orders, queries):
    from collections import defaultdict

    exchange_books = defaultdict(lambda: {'bid': defaultdict(int), 'ask': defaultdict(int)})
    global_books = {'bid': defaultdict(int), 'ask': defaultdict(int)}

    for exchange_id, price, quantity, order_type in orders:
        exchange_books[exchange_id][order_type][price] += quantity
        global_books[order_type][price] += quantity

    def best_level(levels, side):
        if not levels:
            return None
        best_price = max(levels) if side == 'bid' else min(levels)
        return (best_price, levels[best_price])

    exchange_bbo = {}
    for exchange_id, sides in exchange_books.items():
        exchange_bbo[exchange_id] = (
            best_level(sides['bid'], 'bid'),
            best_level(sides['ask'], 'ask')
        )

    nbbo = (
        best_level(global_books['bid'], 'bid'),
        best_level(global_books['ask'], 'ask')
    )

    result = []
    for query in queries:
        if query[0] == 'exchange_bbo':
            result.append(exchange_bbo.get(query[1], (None, None)))
        elif query[0] == 'nbbo':
            result.append(nbbo)
        else:
            raise ValueError(f'Unknown query type: {query[0]}')

    return result

Time complexity: O(n + q), where n is the number of orders and q is the number of queries. Space complexity: O(n).

Quick Overview

Examples

Solution

Hints