A market order says "fill me now at whatever prices are available". A market buy takes shares from the resting sell orders, cheapest price first, and keeps climbing to worse prices until it has its quantity or the sell side runs out. A market sell does the mirror image against the resting buy orders, highest price first. Traders call this walking or sweeping the book, and they care about three numbers: how much got filled, what it cost, and the worst price touched.
Implement sweep(resting, side, qty) -> tuple[int, int, int | None]:
restingis the book: a list of(side, price, qty)orders,sidebeing"buy"or"sell", in no particular price order. Several orders can share a price.sideis the market order's side ("buy"or"sell"),qtyits size (a positive integer).- Return
(filled, notional, worst_price):filled: shares actually filled (less thanqtyif the opposite side is too thin);notional:Σ price · sharesover every fill;worst_price: the last (worst) price it traded at, orNoneif nothing filled.
- Don't modify
resting.
book = [("sell", 102, 5), ("buy", 99, 4), ("sell", 101, 3), ("sell", 105, 10), ("buy", 100, 2)]
sweep(book, "buy", 6) # (6, 101*3 + 102*3, 102) = (6, 609, 102)
sweep(book, "sell", 5) # (5, 100*2 + 99*3, 99) = (5, 497, 99)
sweep(book, "sell", 50) # (6, 596, 99) only 6 shares were bid
sweep([("buy", 10, 1)], "buy", 3) # (0, 0, None) no sellers at all
Constraints: up to 10^5 resting orders, prices and quantities up to 10^9, qty up to 10^15. All integers; don't use floats.
Show hint
Keep only the opposite side's orders and sort them best-first (ascending prices for a buy, descending for a sell). Walk them, taking min(remaining, order_qty) from each and stopping when remaining hits 0.