Order Book That Matches Trades
Implement a class OrderBook for trading one stock. Orders arrive with a side ("buy" or "sell"), a price and a quantity, and get the ids 1, 2, 3, ... in order of arrival. An arriving order trades with resting orders on the other side, and whatever is left of it rests in the book. Write these methods:
- OrderBook() starts with an empty book.
- place(side, price, qty) adds an order and returns the total quantity it traded on arrival.
- A buy order can trade with resting sell orders priced at or below its price; a sell order can trade with resting buy orders priced at or above its price.
- It always trades with the best such order: the lowest-priced sell for a buy, the highest-priced buy for a sell, and the earliest one among equal prices. Each trade is for the smaller of the two remaining quantities, at the price of the resting order.
- It keeps trading until it is filled or nothing more can trade. Any quantity left rests in the book. A resting order that is partly filled keeps its place.
- cancel(order_id) removes a resting order and returns the quantity it still had, or 0 if that order is not resting.
- best_price(side) returns the highest resting buy price (for "buy") or the lowest resting sell price (for "sell"), or -1 if that side has no resting orders.
- quantity_at(side, price) returns the total resting quantity on side at price.
- get_last_trades() returns the trades made by the most recent place as [resting_id, price, qty] triples, in the order they happened ([] if that order traded nothing or no order has been placed).
The tests call the methods in sequence and compare every return value. The expected list holds null for the constructor.
Example 1
The buy for 10 shares first takes the cheapest sell, order 2 at 9. At price 10, order 1 arrived before order 3, so it trades first, and order 3 is left with 2 shares. Order 4 was filled completely, so cancelling it returns 0.
Constraints
sideis"buy"or"sell"1 <= price <= 20and1 <= qty <= 101 <= order_id <= 50- Each test makes
1to40method calls after the constructor.
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.