Compute BBO and NBBO from order data
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
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'
Examples
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.
Input: ([('A', 50, 2, 'ask'), ('A', 50, 3, 'ask'), ('C', 49, 7, 'bid')], [('exchange_bbo', 'A'), ('exchange_bbo', 'B'), ('nbbo',)])
Expected Output: [(None, (50, 5)), (None, None), ((49, 7), (50, 5))]
Explanation: Exchange A has only asks at 50, so its bid side is None. Exchange B does not exist, so both sides are None. The global best bid is 49 with quantity 7, and the global best ask is 50 with quantity 5.
Input: ([], [('nbbo',), ('exchange_bbo', 'X')])
Expected Output: [(None, None), (None, None)]
Explanation: With no orders, neither the national book nor any exchange has a bid or ask.
Input: ([('E1', 10, 1, 'bid'), ('E1', 12, 2, 'ask'), ('E2', 11, 4, 'bid'), ('E2', 12, 3, 'ask'), ('E3', 11, 1, 'bid')], [('nbbo',), ('exchange_bbo', 'E2')])
Expected Output: [((11, 5), (12, 5)), ((11, 4), (12, 3))]
Explanation: The best bid price globally is 11, shared by E2 and E3 for a total quantity of 5. The best ask price globally is 12, shared by E1 and E2 for a total quantity of 5.
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).
Hints
- Aggregate quantities by exchange, side, and price before trying to find the best quote.
- Because the input data is static, you can precompute each exchange BBO and the overall NBBO once, then answer each query in O(1).