Online Stock Brokerage

Trading Platform & Order Matching

Design a brokerage with an order book per stock: market, limit and stop orders matched by price-time priority, partial fills, cancels, and accounts whose cash and shares are reserved so nothing is spent twice.

Overview

A brokerage lets people buy and sell shares. At its center is an order book for each stock: the buy orders waiting at each price (bids) and the sell orders waiting at each price (asks). A new order is matched against the other side of the book; whatever does not fill either waits in the book (a limit order) or is dropped (a market order). Around the book sit accounts, which must hold enough cash or shares before an order is accepted.

The problem tests three things. First, the matching rule: best price first, and among orders at the same price, the oldest first (price-time priority, also called FIFO). Nasdaq's own book rule works this way, and also ranks displayed orders ahead of hidden ones at the same price. Second, the data structure that makes that rule cheap: a queue per price level and a sorted list of prices. Third, money safety: an account with 100 dollars must not place two 100-dollar orders, so cash and shares are reserved when an order is placed and released when it fills or is canceled.

A strong answer walks through one trade by hand, draws the book, keeps money in integer cents, and ends with a demo that checks partial fills, time priority, a cancel and a stop order.

Scoping the problem

Are we the exchange, or a broker sending orders to one? — A broker routes orders; an exchange matches them — Build the matching core; routing is a follow-up
Which order types? — Each adds a rule — Market, limit, sell stop
Partial fills? — Orders keep a filled count — Yes
Does a market order's remainder wait in the book? — Changes what happens when liquidity runs out — No, it is canceled
Short selling or margin? — Changes the account checks — No: sell only shares you hold, buy only with cash you have
How are prices stored? — Floats round badly — Integer cents
Many clients at once? — Decides the locking — Yes; one symbol's orders are processed one at a time

Order types

Market — Buy or sell now at the best prices available; the price is not guaranteed — Walks the book; the remainder is canceled
Limit — Buy at the limit price or lower, sell at the limit price or higher; may not fill — Matches while prices cross, then rests in the book
Stop (stop-loss) — Waits until the price reaches the stop price, then becomes a market order — Sell stops fire when the last trade price falls to the stop
Stop-limit — Like a stop, but becomes a limit order when triggered — A follow-up

The order book

Each side is a dictionary from price to a queue of orders, plus a sorted list of the prices that have orders. The best bid is the last (highest) price on the buy side; the best ask is the first (lowest) on the sell side. New orders join the back of their price's queue, so the front is always the oldest.

Best price — O(1) — Ends of the sorted price list
Match against the front order — O(1), or O(L) when it empties a level — popleft on a deque; an empty level leaves the price list
Rest an order at an existing price — O(1) — append
Rest at a new price — O(L) — Insert into the sorted list of L price levels
Cancel — O(L + k) — Remove from its queue of k orders; drop the price if empty

A balanced tree would make adding or removing a price level O(log L). The sorted list is simpler and fine while L is small; say you would measure before switching.

One trade, step by step

The demo's first trade: bob has two asks resting, and alice sends a limit buy for 15 at 10.10.

Before — 10.00: bob 10; 10.10: bob 10 — none — 151.50
1 — 10.10: bob 10 — 10 at 10.00 — 50.50
2 — 10.10: bob 5 — 5 at 10.10 — 0

alice pays 100.00 + 50.50 = 150.50, and the 1.00 she saved on the first 10 shares goes back to her free cash. The demo asserts she ends with 849.50 of her 1,000.00.

Reserving money

Without the hold, an account could place two orders that each look affordable on their own. With it, the check and the hold happen together under the account lock.

What you will be able to do

Explain price-time priority and walk a limit order through the book by hand.
Build a book from a queue per price level and a sorted list of prices, and state each operation's cost.
Keep money exact in integer cents and reserve cash and shares so nothing is spent twice.
Handle market, limit and stop orders, partial fills and cancels.
Say where the locks are and why one symbol is processed one order at a time.

Functional requirements

place(account, symbol, side, kind, qty, price, stop) accepts market, limit and sell stop orders
Orders match by price-time priority; a trade happens at the resting order's price; partial fills are allowed
A limit remainder rests in the book; a market remainder is canceled
A sell stop becomes a market order when the last trade price falls to its stop price
cancel(order_id) removes an open or partly filled order and releases its reservation
Buys need free cash and sells need free shares at placement, or the order is rejected
Every trade is sent to listeners (market data, audit log)

Non-functional requirements

Money in integer cents; no floating point in balances
Best price and matching the front order are O(1)
One symbol is processed one order at a time, so results are deterministic; different symbols run in parallel
No cash or share is created or lost: a threaded test checks the totals
Listeners are called outside the book lock, so a slow subscriber does not stall matching

Interview questions

Why is a trade priced at the resting order's price, and what does the incoming order gain?
Price-time priority is not the only rule. What else do exchanges use?
How do stop orders work, and what can go wrong?
How does this scale to many symbols and a crash-safe engine?
Why integer cents instead of floats?