Financial & PaymentsProblem 7 of 7
Financial & PaymentsAdvanced
Stock Brokerage
Observer PatternStrategy PatternCommand Pattern
Price-time priority order matching with per-stock order books, sorted buy/sell queues for O(log n) insertion, partial fill tracking, and Observer notifications on every executed trade.
Key Abstractions
Exchange
Top-level matching engine that routes orders to the correct order book and updates portfolios
Order
Buy or sell request with price, quantity, and fill tracking. MarketOrder and LimitOrder are subtypes.
OrderBook
Per-stock bid/ask queues sorted by price-time priority, with its own lock for parallel matching
Portfolio
User's cash balance and stock holdings, updated atomically on each trade
Trade
Immutable record of an executed match: buyer, seller, price, quantity, timestamp
Class Diagram
The Key Insight
A stock brokerage is fundamentally a matching engine. Buy orders arrive on one side, sell orders on the other, and the engine pairs them using price-time priority. Whoever offers the best price gets matched first. If two orders have the same price, the one that arrived earlier wins.
Every stock gets its own order book. AAPL's buy and sell queues are completely independent from GOOGL's. This matters because it means matching for different stocks can happen in parallel. There is no reason an AAPL trade should block a GOOGL trade.
The part that trips people up is partial fills. Alice wants to buy 100 shares, but the sell side only has orders for 20, 30, and 50 shares at acceptable prices. Her order matches against all three, filling progressively. After matching against the first two (50 shares total), her order sits in the book as PARTIALLY_FILLED until more sell orders come in or she cancels.
Requirements
Functional
- Place market orders (execute immediately at best available price) and limit orders (execute only at a specified price or better)
- Match buy and sell orders using price-time priority within per-stock order books
- Support partial fills when an order is larger than the available counter-orders
- Cancel open or partially filled orders
- Track user portfolios with cash balance and stock holdings
- Notify observers when trades execute
Non-Functional
- Per-stock order book locking so different symbols can match in parallel
- O(log n) order insertion and O(1) best-price access via priority queues
- Portfolio updates must be atomic per trade to prevent inconsistent state
Design Decisions
Why one OrderBook per stock?
Consider a single shared order book for all stocks. Every incoming AAPL order would need to filter through GOOGL and MSFT orders. Matching gets slower, and you need a global lock that serializes everything. Separate books give natural partitioning. Each one manages its own sorted queues and its own lock. Different stocks, zero contention.
Why price-time priority?
This is the standard algorithm used by NASDAQ, NYSE, and most major exchanges. Fairness demands it. If you are willing to pay more, you should get matched first. Among equal prices, the order that arrived first should execute first. Any other approach creates perverse incentives or exploitable ordering.
Why priority queues for the order book?
Matching always starts with the best available price. On the buy side, that is the highest bid. On the sell side, that is the lowest ask. A heap gives you O(1) access to the best price and O(log n) insertion. A flat list would require O(n) scanning or O(n log n) re-sorting on every new order.
Why do market orders return null for price?
Market orders carry no price constraint. They match at whatever the resting order's price happens to be. A market buy matches against the lowest sell. By returning null from getPrice(), the matching logic knows to use the counter-order's price as the execution price. Clean separation of order types without special-case branching in the matcher.
Why update portfolios inside the exchange?
Trades and portfolio updates must stay consistent. If a trade executes but the portfolio update fails or runs later, you have a window where the order book says one thing and the portfolio says another. Processing updates as part of the matching flow keeps everything atomic.
Interview Follow-ups
- "How would you handle stop-loss orders?" A stop-loss is a conditional order that converts to a market order when the stock hits a trigger price. Maintain a separate list of stop orders. After each trade, check if any stop prices were breached. Convert triggered stops into regular market orders and submit them.
- "What about after-hours trading?" Separate order book sessions. During market hours, matching runs normally. After hours, orders queue up and activate when the session opens, or you run a limited after-hours session with wider spreads and lower liquidity.
- "How would you scale to millions of orders?" Shard by stock symbol across multiple matching engine instances. A gateway routes orders to the correct shard. Each instance handles a partition of symbols independently. Horizontal scaling without coordination overhead.
- "How do you prevent self-trading?" Before matching, check if the incoming order and the resting counter-order belong to the same user. If they do, skip that match and move to the next counter-order in the queue.
Code Implementation
1 from __future__ import annotations
2 from abc import ABC, abstractmethod
3 from dataclasses import dataclass, field
4 from decimal import Decimal
5 from datetime import datetime
6 from enum import Enum, auto
7 from collections import defaultdict
8 import threading
9 import uuid
10 import heapq
11
12
13 class OrderSide(Enum):
14 BUY = auto()
15 SELL = auto()
16
17
18 class OrderStatus(Enum):
19 PENDING = auto()
20 PARTIALLY_FILLED = auto()
21 FILLED = auto()
22 CANCELLED = auto()
23
24
25 @dataclass
26 class Order(ABC):
27 order_id: str
28 user_id: str
29 symbol: str
30 side: OrderSide
31 quantity: int
32 filled_qty: int = 0
33 status: OrderStatus = OrderStatus.PENDING
34 timestamp: datetime = field(default_factory=datetime.now)
35
36 @property
37 def remaining(self) -> int:
38 return self.quantity - self.filled_qty
39
40 def fill(self, qty: int) -> None:
41 self.filled_qty += qty
42 self.status = (
43 OrderStatus.FILLED if self.filled_qty >= self.quantity
44 else OrderStatus.PARTIALLY_FILLED
45 )
46
47 @abstractmethod
48 def get_price(self) -> Decimal | None: ...
49
50
51 @dataclass
52 class LimitOrder(Order):
53 limit_price: Decimal = Decimal("0")
54
55 def get_price(self) -> Decimal | None:
56 return self.limit_price
57
58
59 @dataclass
60 class MarketOrder(Order):
61 def get_price(self) -> Decimal | None:
62 return None # matches at whatever price is available
63
64
65 @dataclass(frozen=True)
66 class Trade:
67 trade_id: str
68 buy_order_id: str
69 sell_order_id: str
70 symbol: str
71 price: Decimal
72 quantity: int
73 timestamp: datetime
74
75
76 class TradeObserver(ABC):
77 @abstractmethod
78 def on_trade(self, trade: Trade) -> None: ...
79
80
81 class TradeLogger(TradeObserver):
82 def on_trade(self, trade: Trade) -> None:
83 print(
84 f" [TRADE] {trade.symbol}: {trade.quantity} shares "
85 f"@ ${trade.price} (buy={trade.buy_order_id}, sell={trade.sell_order_id})"
86 )
87
88
89 class _HeapEntry:
90 """Wrapper for heap-based priority ordering."""
91 def __init__(self, order: Order, is_buy: bool):
92 self.order = order
93 self.is_buy = is_buy
94
95 def __lt__(self, other: "_HeapEntry") -> bool:
96 my_price = self.order.get_price() or Decimal("0")
97 other_price = other.order.get_price() or Decimal("0")
98 if self.is_buy:
99 # Buy side: highest price first, then earliest timestamp
100 if my_price != other_price:
101 return my_price > other_price
102 return self.order.timestamp < other.order.timestamp
103 else:
104 # Sell side: lowest price first, then earliest timestamp
105 if my_price != other_price:
106 return my_price < other_price
107 return self.order.timestamp < other.order.timestamp
108
109
110 class OrderBook:
111 def __init__(self, symbol: str):
112 self.symbol = symbol
113 self._buys: list[_HeapEntry] = []
114 self._sells: list[_HeapEntry] = []
115 self._orders: dict[str, Order] = {}
116 self._lock = threading.Lock()
117
118 def add_order(self, order: Order) -> list[Trade]:
119 with self._lock:
120 self._orders[order.order_id] = order
121 trades = self._match(order)
122 # If the order still has unfilled quantity, park it in the book
123 if order.remaining > 0 and order.status != OrderStatus.CANCELLED:
124 if order.side == OrderSide.BUY:
125 heapq.heappush(self._buys, _HeapEntry(order, True))
126 else:
127 heapq.heappush(self._sells, _HeapEntry(order, False))
128 return trades
129
130 def _match(self, incoming: Order) -> list[Trade]:
131 trades = []
132 counter = self._sells if incoming.side == OrderSide.BUY else self._buys
133
134 while incoming.remaining > 0 and counter:
135 best = counter[0].order
136
137 # Skip dead orders still sitting in the heap
138 if best.status in (OrderStatus.FILLED, OrderStatus.CANCELLED):
139 heapq.heappop(counter)
140 continue
141
142 # Price compatibility
143 if incoming.get_price() is not None and best.get_price() is not None:
144 if incoming.side == OrderSide.BUY and incoming.get_price() < best.get_price():
145 break
146 if incoming.side == OrderSide.SELL and incoming.get_price() > best.get_price():
147 break
148
149 # Execution price is the resting order's price
150 exec_price = best.get_price() or incoming.get_price() or Decimal("0")
151 fill_qty = min(incoming.remaining, best.remaining)
152
153 incoming.fill(fill_qty)
154 best.fill(fill_qty)
155
156 buy_id = incoming.order_id if incoming.side == OrderSide.BUY else best.order_id
157 sell_id = best.order_id if incoming.side == OrderSide.BUY else incoming.order_id
158
159 trades.append(Trade(
160 trade_id=str(uuid.uuid4())[:8],
161 buy_order_id=buy_id,
162 sell_order_id=sell_id,
163 symbol=self.symbol,
164 price=exec_price,
165 quantity=fill_qty,
166 timestamp=datetime.now(),
167 ))
168
169 if best.remaining == 0:
170 heapq.heappop(counter)
171
172 return trades
173
174 def cancel_order(self, order_id: str) -> bool:
175 with self._lock:
176 order = self._orders.get(order_id)
177 if order and order.status in (OrderStatus.PENDING, OrderStatus.PARTIALLY_FILLED):
178 order.status = OrderStatus.CANCELLED
179 return True
180 return False
181
182 @property
183 def best_bid(self) -> Decimal | None:
184 for entry in self._buys:
185 if entry.order.status not in (OrderStatus.FILLED, OrderStatus.CANCELLED):
186 return entry.order.get_price()
187 return None
188
189 @property
190 def best_ask(self) -> Decimal | None:
191 for entry in self._sells:
192 if entry.order.status not in (OrderStatus.FILLED, OrderStatus.CANCELLED):
193 return entry.order.get_price()
194 return None
195
196
197 class Portfolio:
198 def __init__(self, user_id: str, cash: Decimal):
199 self.user_id = user_id
200 self._cash = cash
201 self._holdings: dict[str, int] = defaultdict(int)
202
203 def buy(self, symbol: str, qty: int, price: Decimal) -> None:
204 cost = price * qty
205 if cost > self._cash:
206 raise ValueError(f"Need ${cost}, have ${self._cash}")
207 self._cash -= cost
208 self._holdings[symbol] += qty
209
210 def sell(self, symbol: str, qty: int, price: Decimal) -> None:
211 held = self._holdings.get(symbol, 0)
212 if held < qty:
213 raise ValueError(f"Need {qty} shares of {symbol}, have {held}")
214 self._holdings[symbol] -= qty
215 self._cash += price * qty
216
217 @property
218 def cash(self) -> Decimal:
219 return self._cash
220
221 @property
222 def holdings(self) -> dict[str, int]:
223 return dict(self._holdings)
224
225
226 class Exchange:
227 def __init__(self):
228 self._books: dict[str, OrderBook] = {}
229 self._portfolios: dict[str, Portfolio] = {}
230 self._observers: list[TradeObserver] = []
231
232 def register_portfolio(self, portfolio: Portfolio) -> None:
233 self._portfolios[portfolio.user_id] = portfolio
234
235 def add_observer(self, observer: TradeObserver) -> None:
236 self._observers.append(observer)
237
238 def _get_book(self, symbol: str) -> OrderBook:
239 if symbol not in self._books:
240 self._books[symbol] = OrderBook(symbol)
241 return self._books[symbol]
242
243 def place_order(self, order: Order) -> list[Trade]:
244 book = self._get_book(order.symbol)
245 trades = book.add_order(order)
246
247 for trade in trades:
248 buy_order = book._orders.get(trade.buy_order_id)
249 sell_order = book._orders.get(trade.sell_order_id)
250
251 if buy_order:
252 bp = self._portfolios.get(buy_order.user_id)
253 if bp:
254 bp.buy(trade.symbol, trade.quantity, trade.price)
255 if sell_order:
256 sp = self._portfolios.get(sell_order.user_id)
257 if sp:
258 sp.sell(trade.symbol, trade.quantity, trade.price)
259
260 for obs in self._observers:
261 obs.on_trade(trade)
262
263 return trades
264
265 def cancel_order(self, symbol: str, order_id: str) -> bool:
266 book = self._books.get(symbol)
267 return book.cancel_order(order_id) if book else False
268
269 def get_book(self, symbol: str) -> OrderBook | None:
270 return self._books.get(symbol)
271
272
273 if __name__ == "__main__":
274 exchange = Exchange()
275 exchange.add_observer(TradeLogger())
276
277 # Set up portfolios
278 alice_port = Portfolio("alice", Decimal("10000.00"))
279 bob_port = Portfolio("bob", Decimal("5000.00"))
280 bob_port._holdings["AAPL"] = 50 # Bob starts with shares to sell
281
282 exchange.register_portfolio(alice_port)
283 exchange.register_portfolio(bob_port)
284
285 print("=== Stock Brokerage ===\n")
286 print(f"Alice: ${alice_port.cash} cash")
287 print(f"Bob: ${bob_port.cash} cash, {bob_port.holdings} shares\n")
288
289 # Bob places two sell limit orders at different prices
290 print("Bob posts sell orders for AAPL:")
291 s1 = LimitOrder(order_id="S1", user_id="bob", symbol="AAPL",
292 side=OrderSide.SELL, quantity=20, limit_price=Decimal("150.00"))
293 s2 = LimitOrder(order_id="S2", user_id="bob", symbol="AAPL",
294 side=OrderSide.SELL, quantity=15, limit_price=Decimal("155.00"))
295 exchange.place_order(s1)
296 exchange.place_order(s2)
297 print(f" Sell 20 @ $150, Sell 15 @ $155\n")
298
299 # Alice places a buy limit order that crosses the best ask
300 print("Alice buys 25 AAPL @ limit $152...")
301 b1 = LimitOrder(order_id="B1", user_id="alice", symbol="AAPL",
302 side=OrderSide.BUY, quantity=25, limit_price=Decimal("152.00"))
303 trades = exchange.place_order(b1)
304 print(f" Matched {len(trades)} trade(s)")
305 print(f" Order status: {b1.status.name} ({b1.filled_qty}/{b1.quantity})\n")
306
307 # Alice places a market order for 10 more shares
308 print("Alice market-buys 10 AAPL...")
309 b2 = MarketOrder(order_id="B2", user_id="alice", symbol="AAPL",
310 side=OrderSide.BUY, quantity=10)
311 trades = exchange.place_order(b2)
312 print(f" Matched {len(trades)} trade(s)\n")
313
314 # Final state
315 print("Final portfolios:")
316 print(f" Alice: ${alice_port.cash} cash, {alice_port.holdings}")
317 print(f" Bob: ${bob_port.cash} cash, {bob_port.holdings}")
318
319 book = exchange.get_book("AAPL")
320 print(f"\nAAPL order book:")
321 print(f" Best bid: {book.best_bid}")
322 print(f" Best ask: {book.best_ask}")
323
324 # Cancel remaining order
325 print(f"\nBob cancels S2...")
326 print(f" Cancelled: {exchange.cancel_order('AAPL', 'S2')}")
327 print(f" S2 status: {s2.status.name}")Common Mistakes
- ✗Using a single order book for all stocks. Matching AAPL orders would block GOOGL for no reason.
- ✗Not handling partial fills. A large order routinely matches against several smaller counter-orders at different price levels.
- ✗Sorting the sell side in descending order instead of ascending. The lowest ask should match first, not the highest.
- ✗Forgetting to update portfolio holdings after a trade executes. The order is filled but the user's position stays stale.
Key Points
- ✓One OrderBook per stock. AAPL and GOOGL match independently, so they can run in parallel without contention.
- ✓Price-time priority: best price wins. Ties broken by earliest submission. This is how NYSE and NASDAQ work.
- ✓Market orders match immediately at the best available price. Limit orders wait in the book until a compatible counter-order arrives.
- ✓Partial fills are first-class. A buy for 100 shares might match against three separate sells of 30, 30, and 40.