You are building the core of an exchange for one symbol.
Stage 1 (easy). Accept limit orders (order_id, side, price, quantity) and store them in an order book. Implement print_book(): bids from highest price to lowest, asks from lowest to highest, showing total quantity at each price level.
Answer 1.1 — plan:
txt
OrderBook- Store a dictionary mapping price -> list of ordersadd()- Adds an order to that price level's list of ordersprint_book()
Answer 1.1 — code:
Stage 2 (medium). Add matching. An incoming order that crosses the book (buy price ≥ best ask, or sell price ≤ best bid) executes immediately against resting orders, best price first, oldest first within a price. Trades print as (resting_id, incoming_id, price, quantity) and execute at the resting order’s price. Any unfilled remainder rests in the book.
Answer 1.2 — plan:
Answer 1.2 — code:
Stage 3 (hard). Add cancel(order_id) and modify(order_id, new_price, new_quantity). Cancel must work on partially filled orders and be safe on unknown ids. Modify keeps time priority only if the price is unchanged and the quantity decreased; otherwise it is treated as cancel + new order. State the time complexity of every public operation you now have.
Answer 1.3 — plan:
Answer 1.3 — code:
Answer 1.3 — complexities:
1Some Practice Questions, Jane Street Style
2
3
4## Question 1: Matching engine
5You are building the core of an exchange for one symbol.
6
7Stage 1 (easy). Accept limit orders (order_id, side, price, quantity) and store them in an order book. Implement print_book(): bids from highest price to lowest, asks from lowest to highest, showing total quantity at each price level.
8
9#### Answer 1.1 — plan:
10
11```
12OrderBook
13- Store a dictionary mapping price -> list of orders
14
15add()
16- Adds an order to that price level's list of orders
17
18print_book()
19
20
21
22```
23
24#### Answer 1.1 — code:
25
26
27
28Stage 2 (medium). Add matching. An incoming order that crosses the book (buy price ≥ best ask, or sell price ≤ best bid) executes immediately against resting orders, best price first, oldest first within a price. Trades print as (resting_id, incoming_id, price, quantity) and execute at the resting order's price. Any unfilled remainder rests in the book.
29
30Answer 1.2 — plan:
31
32Answer 1.2 — code:
33
34Stage 3 (hard). Add cancel(order_id) and modify(order_id, new_price, new_quantity). Cancel must work on partially filled orders and be safe on unknown ids. Modify keeps time priority only if the price is unchanged and the quantity decreased; otherwise it is treated as cancel + new order. State the time complexity of every public operation you now have.