Order Book: Matching Engine

Order Book: Matching Engine

You've joined the team that owns the matching engine for a small exchange: the component that accepts buy and sell orders for one instrument, pairs them up and keeps the resting book. Traders have reported two bugs in the matching itself, and the roadmap has three pieces of work behind them. Prices are integer ticks and quantities are integer units.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against an empty book and returns one result per operation. Every operation is [name, ...args]. Errors are returned as "error: <code>" strings, never raised.

• An unknown operation name returns "error: unknown operation"; a wrong number of arguments returns "error: invalid arguments". cancel, amend and market currently answer "error: not supported".
• side is "buy" or "sell". order_id and trader are non-blank, case-sensitive strings; price and qty are integers >= 1. Anything else is invalid order. Order ids are unique across every order ever accepted, including filled and cancelled ones.
• Matching. An incoming order trades against the opposite side while it crosses: a buy crosses sells priced at or below its price, a sell crosses buys priced at or above its price. Resting orders are served best price first (lowest ask, highest bid) and, within one price, in the order they arrived (price-time priority). Each trade happens at the resting order's price and is reported as [maker_id, price, qty], in the order the trades happen. Whatever is left of a limit order is added to the book (rested is that quantity; 0 if it fully traded).
• A resting order that is partly filled keeps its place in line with its smaller remaining quantity.
• status.state is "open" (still has quantity working), "filled" (fully traded) or "cancelled". filled is the total quantity traded; remaining is the quantity still working (0 once filled or cancelled).
• depth lists at most levels price levels of one side, each with the total remaining quantity of the open orders at that price. side must be a side and levels an integer >= 1.
• ladder is a convenience for market makers. It places levels * per_level limit orders, each of size qty, exactly as if the limit operations were sent one after another in this order: level 0 first, then level 1, and so on, with per_level orders per level. Order k of level i has id "<prefix>-<i>-<k>" and trader trader. A buy ladder's prices step down from price (price - i * step), a sell ladder's step up (price + i * step). traded is the total quantity its orders traded on arrival. price, step, levels, per_level, qty must all be integers >= 1, prefix and trader non-blank, the lowest price must still be >= 1, and levels * per_level at most 20,000; otherwise invalid order. If any generated id already exists, nothing is placed and the result is duplicate order.

Worked example

[["limit", "s1", "alice", "sell", 101, 5],
 ["limit", "s2", "bob",   "sell", 101, 3],
 ["limit", "s3", "carol", "sell", 102, 4],
 ["limit", "b1", "dave",  "buy",  102, 6],
 ["depth", "sell", 5],
 ["best"],
 ["status", "s2"]]

returns

[{"fills": [], "rested": 5},
 {"fills": [], "rested": 3},
 {"fills": [], "rested": 4},
 {"fills": [["s1", 101, 5], ["s2", 101, 1]], "rested": 0},
 [[101, 2], [102, 4]],
 {"bid": null, "ask": 101},
 {"state": "open", "filled": 1, "remaining": 2}]

b1 is willing to pay up to 102 but trades at the resting price, 101. s1 arrived before s2, so it is filled first.

Part 1 — Matching is wrong

Goal: make matching follow the rules above.

Traders have reported:

1. "When two orders sit at the same price, the one that arrived last gets filled first."
2. "My buy at 102 traded against an ask at 101 and I was charged 102."

Rules

1. Within a price level, earlier arrivals are filled first on both sides of the book.
2. Every trade happens at the resting order's price, for buys and sells alike.

Part 2 — Cancels and amends

Goal: let traders cancel and change orders that are resting in the book.

Rules

1. cancel(order_id) removes an open order from the book (which may already be partly filled) and returns the quantity that was still working. Afterwards its status is "cancelled" with its filled quantity unchanged and remaining 0. depth and best no longer include it, and the orders behind it move up. Errors: unknown order; order not open for orders that are already filled or cancelled.
2. amend(order_id, new_price, new_qty) changes an open order. new_qty is the new *remaining* quantity (what is still working), not the original size; the order's filled quantity is kept. Checks are in this order: invalid order (new_price and new_qty must be integers >= 1), unknown order, order not open.
3. If new_price equals the current price and new_qty is at most the current remaining quantity, the order keeps its place in line, now with new_qty remaining. The result is {"fills": [], "rested": new_qty}.
4. Any other amend (a different price, or more quantity than is currently remaining) takes the order off the book and re-enters it as a new arrival at the back of the line with the new price and new_qty. If it now crosses the other side it trades immediately, exactly like a new limit order. The result has the same shape as limit: the fills and the quantity that rested.
5. An order can never trade against itself, and amends never change the order's id or trader.

Example

[["limit", "s1", "alice", "sell", 101, 5],
 ["limit", "s2", "bob",   "sell", 101, 3],
 ["amend", "s1", 101, 2],
 ["amend", "s1", 101, 4],
 ["limit", "b1", "carol", "buy", 101, 4],
 ["cancel", "s1"],
 ["status", "s1"]]

returns

[{"fills": [], "rested": 5},
 {"fills": [], "rested": 3},
 {"fills": [], "rested": 2},
 {"fills": [], "rested": 4},
 {"fills": [["s2", 101, 3], ["s1", 101, 1]], "rested": 0},
 3,
 {"state": "cancelled", "filled": 1, "remaining": 0}]

(The first amend only shrinks s1, so it stays first in line. The second raises it back to 4, which sends it behind s2.)

Part 3 — Market orders and self-trade prevention

Goal: support orders that take whatever liquidity is available, and stop traders trading with themselves.

Rules

1. market(order_id, trader, side, qty) trades against the opposite side from the best price outward with no price limit, using the same priority and trade-price rules as limit orders. Whatever cannot be filled is not added to the book: the result is {"fills": [...], "rested": 0, "unfilled": n} with n the quantity that found no counterparty. Validation and errors are those of limit without the price. The order's status is "filled" if it fully traded and "cancelled" otherwise (its filled quantity is what did trade; remaining is 0).
2. Self-trade prevention. When an incoming order (limit, market, ladder order or re-entered amend) reaches a resting order with the same trader that it would otherwise trade with, no trade happens. The resting order is cancelled instead (status "cancelled", nothing reported in fills) and matching continues with the next resting order. Resting orders of the same trader that the incoming order does not cross are left alone.
3. Rules 1 and 2 apply on both sides, and ladder orders are subject to them one by one, in order.
4. Parts 1 and 2 behaviour is unchanged.

Example

[["limit", "s1", "alice", "sell", 100, 5],
 ["limit", "s2", "bob",   "sell", 100, 5],
 ["limit", "b1", "alice", "buy",  100, 7],
 ["status", "s1"],
 ["market", "m1", "carol", "sell", 10],
 ["status", "m1"]]

returns

[{"fills": [], "rested": 5},
 {"fills": [], "rested": 5},
 {"fills": [["s2", 100, 5]], "rested": 2},
 {"state": "cancelled", "filled": 0, "remaining": 0},
 {"fills": [["b1", 100, 2]], "rested": 0, "unfilled": 8},
 {"state": "cancelled", "filled": 2, "remaining": 0}]

(Alice's own sell s1 is cancelled instead of trading with her buy; the buy then trades with Bob and the remaining 2 rests. Carol's market sell finds only those 2 units.)

Part 4 — Order flow at scale (stretch)

Goal: keep every result above identical, but make the engine handle real market-maker traffic.

Production books hold tens of thousands of resting orders, and market makers send ladders with thousands of orders at a time. Hidden tests send ladders of several thousand orders that rest, cross each other and get swept, interleaved with depth, best, cancel and amend operations on a deep book. Each of these tests needs to finish in about a second.

Notes

• validation.py, ladder.py, queries.py and models.py are known-good for Parts 1 to 3; the Part 1 bugs are in the matching and the book.
• You may use the AI assistant freely. Later parts must not break earlier ones: hidden tests re-check earlier behaviour.
• Parts 1 to 3 are a strong result; Part 4 is a stretch.