Number of Orders in the Backlog

Number of Orders in the Backlog

What is this problem about?

The Number of Orders in the Backlog problem simulates a stock exchange order book. You receive a sequence of orders: each is either a buy order (at most some price) or a sell order (at least some price). Matching orders execute immediately; unmatched orders go into a backlog. Return the total number of unmatched orders after all orders are processed. This coding problem uses two heaps for buy and sell backlogs.

Why is this asked in interviews?

Citadel, Coinbase, Jane Street, and Robinhood ask this because stock exchange simulation is directly relevant to their business. It tests heap-based order matching simulation — a practical algorithm used in financial trading systems. The array, heap, and simulation interview pattern is directly exercised.

Algorithmic pattern used

Max-heap for buy orders + min-heap for sell orders. For a new buy order at price p: match against the cheapest sell order in the sell backlog (min-heap top) while sell_top ≤ p and there are sell orders. Process quantity. Remaining unmatched quantity goes into the buy backlog (max-heap). Vice versa for sell orders. Return sum of all remaining quantities in both backlogs, mod 10^9+7.

Example explanation

Orders: [(10,5,"buy"),(15,2,"sell"),(25,1,"buy"),(30,4,"sell"),(5,6,"sell")].

• Buy 5@10: no sell ≤ 10. Buy backlog: [(10,5)].
• Sell 2@15: no buy ≥ 15. Sell backlog: [(15,2)].
• Buy 1@25: sell@15 ≤ 25 → match 1 unit. Sell backlog: [(15,1)].
• Sell 4@30: no buy ≥ 30. Sell backlog: [(15,1),(30,4)].
• Sell 6@5: no buy ≥ 5 that's cheaper? Buy backlog has (10,5) ≥ 5. Match 5 units. Remaining sell qty=1. Sell backlog: [(5,1),(15,1),(30,4)]. Total remaining = 0+0+1+1+4 = 6.

Common mistakes candidates make

• Using a list instead of a heap (O(n) matching instead of O(log n)).
• Not handling partial quantity matching (one order can partially match another).
• Forgetting to apply modulo to the final sum.
• Using min-heap for buy orders (should be max-heap — highest buy price matches first).

Interview preparation tip

Order book simulation is a classic heap problem where buy orders use a max-heap (match highest buy first) and sell orders use a min-heap (match cheapest sell first). Practice this pattern in the context of "priority matching" simulations — it appears in scheduling, resource allocation, and financial system design questions. Understanding why the heap type differs for buy vs sell is the key conceptual insight.