Challenge
Process limit orders [side,price,quantity] in arrival order. side is "buy" or "sell" and the zero-based row index is its order ID. An incoming buy matches the cheapest resting sells priced ≤ its limit; an incoming sell matches the highest resting buys priced ≥ its limit. At equal prices, match the earliest arriving resting order first. Each fill executes at the resting order’s price. Partial fills retain the resting order’s original time priority. Any incoming remainder rests at its own limit. Return fills in execution order as [buy_id,sell_id,execution_price,quantity].
Input and output contract
0 ≤ n ≤ 1,000; integer prices 1..1,000,000 and quantities 1..100,000. No cancellations, amendments, fees, auctions, self-trade restrictions or market orders. An empty trade history returns []. The output requires order IDs, not just aggregate volume.
All tests follow this contract. You do not need to validate malformed input. Return the requested result from order_book_matching; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.
Target complexity: O(n log(n + 1)) time; O(n) space including trades
Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.
Public examples
Arguments
[[['sell', 100, 4], ['sell', 100, 3], ['buy', 101, 5], ['buy', 99, 2], ['sell', 98, 3]]]
Expected return
[[2, 0, 100, 4], [2, 1, 100, 1], [3, 4, 99, 2]]
Arguments
[[['buy', 99, 3], ['sell', 100, 2]]]
Expected return
[]
Arguments
[[['buy', 105, 2], ['sell', 101, 1]]]
Expected return
[[0, 1, 105, 1]]
Hint
Use a min-heap for sells and a max-heap for buys. Include arrival ID after price as the tie-breaker, and carry remaining quantity.
The worked solution unlocks after completion, or with Premium access.