Implement an in-memory limit-order matcher that processes orders in arrival order and returns both the executed trades and the final resting order books. Each input order has this shape: ```text Order { id: string side: "BUY" | "SELL" price: integer quantity: integer } ``` Use these matching rules: 1. A buy order can trade with a sell order when the buy price is greater than or equal to the sell price. 2. The best resting buy has the highest price; the best resting sell has the lowest price. 3. At the same price, the order that arrived first has priority. The position in the input array is its arrival time. 4. Match an incoming order repeatedly against the best eligible resting order until the incoming order is filled or the books no longer cross. 5. A trade executes at the resting order's price. A partially filled resting order keeps its original time priority. An unfilled remainder of the incoming order becomes a resting order with its original arrival time. 6. Order IDs are unique. Return: ```text MatchResult { trades: Trade[] buyBook: RestingOrder[] sellBook: RestingOrder[] } Trade { buyId: string sellId: string price: integer quantity: integer } RestingOrder { id: string price: integer remainingQuantity: integer } ``` Trade records must appear in execution order. Return the buy book in descending price and then arrival order, and the sell book in ascending price and then arrival order. ## Constraints - `1 <= orders.length <= 200,000` - `1 <= price, quantity <= 1,000,000,000` - The sum of quantities can exceed a signed 32-bit integer; use 64-bit arithmetic for quantities and aggregates. - The expected running time is `O(n log n)` and the order books may use `O(n)` space. ## Example ```text orders = [ {id: "B1", side: "BUY", price: 100, quantity: 5}, {id: "S1", side: "SELL", price: 99, quantity: 2}, {id: "S2", side: "SELL", price: 100, quantity: 5} ] ``` The result is: ```text trades = [ {buyId: "B1", sellId: "S1", price: 100, quantity: 2}, {buyId: "B1", sellId: "S2", price: 100, quantity: 3} ] buyBook = [] sellBook = [ {id: "S2", price: 100, remainingQuantity: 2} ] ``` `B1` is already resting when each sell arrives, so both trades use its price. The second trade partially fills `S2`, whose remainder enters the sell book. ## Interview Discussion After implementing the matcher, be prepared to: - Design tests for partial fills, non-crossing books, multiple matches, and price-time priority at equal prices. - Diagnose a mismatch between a computed result and a sample by tracing book state after every arrival. - Explain why order ID or quantity should not replace arrival time as the equal-price tie-breaker. - Compare heaps with balanced trees, linked lists, or per-price FIFO queues, including the operations each design makes cheap or expensive. - Identify what you would improve with more time, including the way trade records and the final output string or object are assembled.