You’re building a simplified matching engine for a fintech brokerage app that processes hundreds of thousands of order events per minute during volatile markets. A bug in matching logic can directly impact execution quality and regulatory reporting, so correctness matters.
Implement an order book for a single asset. You will receive a sequence of operations ops, each being either:
("POST", order_id, side, price, qty)("CANCEL", order_id)Where:
side is either "BUY" or "SELL"price and qty are positive integersorder_id is unique across all POSTsAfter each POST, repeatedly match as long as the book is crossed:
best_buy.price >= best_sell.pricemin(buy_remaining_qty, sell_remaining_qty)CANCEL makes the order immediately inactive if it is still resting with remaining quantity. Canceling an unknown or already-filled order is a no-op.
Return a list of executed trades in the order they occur. Each trade is:
(buy_order_id, sell_order_id, trade_price, trade_qty)
Example 1
ops = [("POST","b1","BUY",100,5), ("POST","s1","SELL",90,2), ("POST","s2","SELL",95,10)][("b1","s1",100,2), ("b1","s2",100,3)]Example 2
ops = [("POST","b1","BUY",100,5), ("POST","b2","BUY",105,4), ("POST","s1","SELL",103,10)][("b2","s1",105,4), ("b1","s1",100,5)]