Implement an order matching engine supporting buy, sell, modify, cancel and print

Design and implement an order matching system: a program that keeps a book of buy and sell orders and supports five operations, buy, sell, modify, cancel and print. A new buy or sell order is matched against resting orders on the opposite side when the prices cross, and whatever is not filled rests in the book. Modify changes a resting order, cancel removes one, and print shows the current state of the book. This was a take-home online assessment with a 24-hour limit. The matching logic itself is not complicated; the challenge is designing a complete, clean framework in a short time. The report gives no input format or detailed rules, so settle them through the questions below and state your choices. A reasonable default is limit orders on a single instrument, integer prices and quantities, and text commands such as `BUY <order_id> <price> <quantity>`. ### Clarifying Questions - One instrument or several? Are all orders limit orders, or are there market or immediate-or-cancel orders as well? - Are prices and quantities integers, for example prices in ticks? - When an incoming order crosses several resting orders, which trades first, and at whose price does each trade execute? - What can modify change (price, quantity, side), and does a modified order keep its place in the queue? - What exactly should print show, every order or the total quantity at each price level, and in which order? - What should happen on invalid input: a duplicate order id, a zero quantity, or modify and cancel on an unknown or already-filled order? ### Part 1 — Model the book and the matching rule Define the order and the book, and implement buy and sell: match an incoming order against the opposite side, produce trades, handle partial fills, and rest the remainder. ```hint Which order sets the price When an incoming buy crosses a resting sell, decide whose price the trade uses and which resting order trades first when several share the best price. ``` #### What This Part Should Cover - A structure per side that finds the best price quickly and keeps arrival order within a price - A matching loop that handles partial fills and walks across several price levels - The trade record that is reported, and its exact contents ### Part 2 — Modify and cancel Implement modify and cancel for resting orders. ```hint Find it fast, keep it fair Think about how to reach a resting order by its id without scanning the book, and whether an order that changes its price or raises its quantity should keep its place ahead of orders that arrived later. ``` #### What This Part Should Cover - Constant-time lookup from an order id to the resting order - Priority rules on modify, including a modify that makes the order cross the book - Unknown, filled or already-cancelled ids, and invalid new values ### Part 3 — Print, structure and tests Implement print, and organize the program so that parsing, matching and output are separate. Describe the tests you would ship with it. ```hint Separate parsing from matching Ask which parts of your program would have to change if the input format changed but the matching rules did not. ``` #### What This Part Should Cover - A deterministic print order and format - Modules with clear responsibilities, and an engine that performs no input or output - Tests for matching, partial fills, priority, modify, cancel and invalid input, plus the complexity of each operation ### What a Strong Answer Covers - Rules stated explicitly before coding, so that every behavior is unambiguous - Efficient structures: the best price found in logarithmic time or better, and cancel without scanning - Correct matching with price-time priority and partial fills - Precise modify and cancel semantics, with edge cases handled - A clean separation of concerns and a test suite that pins every rule ### Follow-up Questions - Add immediate-or-cancel orders that never rest in the book. What changes? - Support many instruments in one process. How do you structure it, and can the books be processed in parallel? - How would you change the data structures for a very high message rate with tight latency? - The process crashes. How do you rebuild the exact book on restart?