Stock Broker
hard · limit order book, price-time priority
Brief-reported interview attribution (unverified): Amazon
How to approach an LLD roundRequirements
- Functional: place buy/sell orders, match by price-time priority, trade at the resting order's price, partial fills rest the remainder, view the book (bids price-desc, asks price-asc), cancel a resting order.
- Non-functional: a fully filled order must disappear (it cannot be cancelled); the matching rule must be separate from the book; the book view must be a copy.
- Out of scope: market orders, stop orders, multiple exchanges.
Statement
Implement a simplified stock exchange. Orders are placed for a
symbol with a side ("buy"/"sell"), a price (whole dollars), and a quantity
(shares). The exchange keeps a limit order book per symbol: bids (buy orders) and
asks (sell orders). A new order matches against the opposite book by **price-time
priority** — the best price first, the earliest order first among equal prices:
a buy matches the lowest-priced ask at or below the buy price; a sell matches the
highest-priced bid at or above the sell price. Each trade happens at the **resting
order's price** (the order already in the book). A partially filled order rests in
its own book with the remaining quantity; a fully filled order leaves no trace.
class StockBroker:
def __init__(self):
def place_order(self, symbol, side, price, quantity):
# -> (order_id, trades) where trades = [{"buy_order":, "sell_order":, "price":, "quantity":}, ...]
# in the order they happened; (None, []) for a bad side, price <= 0, or quantity <= 0
def book(self, symbol):
# -> {"bids": [{"order_id":, "price":, "quantity":}], "asks": [...]}
# bids by price desc then order id asc; asks by price asc then order id asc
# ({"bids": [], "asks": []} for an unknown symbol)
def cancel_order(self, order_id):
# -> True if a resting order was cancelled, False otherwise
# (a fully filled order cannot be cancelled)Rules. Order ids start at 1 and increase. A trade's quantity is
min(remaining new quantity, resting quantity). A buy that cannot match at all
rests as a bid; a sell that cannot match at all rests as an ask. book() returns
copies, so callers cannot mutate the book.
Money units: order prices are whole dollars. Quantity is a count of shares.
Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.
Class design (SOLID)
Order (id, side, price, remaining quantity; SRP). OrderBook (bids as a max-heap by (-price, order_id), asks as a min-heap by (price, order_id), with lazy cancellation — cancelled/filled orders stay in the heap until they surface and are skipped; SRP). MatchingEngine (ABC interface) + PriceTimeMatchingEngine (the price-time priority match; OCP — a pro-rata engine swaps in). StockBroker orchestrates and takes the engine as a constructor argument (DIP). Pattern: Strategy (matching).
Public demo
# Public demo: run after implementing the class API above.
s = StockBroker()
print(s.place_order('AAPL', 'sell', 150, 10))Reference solution and hidden tests
Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.
Concurrency
This is the hardest concurrency case in the section: two orders matching at once can double-fill the same resting order. The whole match — pick the best opposite order, trade, update quantities — must be atomic: one lock per symbol's book, held for the entire place_order. In production this is a per-symbol lock or a single-threaded matching engine per symbol. The reference is single-threaded; the lock is described here.
Trade-offs & extensions
Heaps make the best opposite price O(1) to peek (O(log M) per match); cancelled orders linger in the heap until they surface, so view filters them out. Extending: a MarketData feed (Observer) and persistence of the book (write-ahead log).
Starter code
import heapq
from abc import ABC, abstractmethod
class Order:
def __init__(self, order_id, symbol, side, price, quantity):
"""Initialize the state described in the problem."""
pass
def view(self):
"""Implement the return value and rules in the API contract."""
pass
class OrderBook:
def __init__(self, symbol):
"""Initialize the state described in the problem."""
pass
def best_opposite(self, side):
"""Implement the return value and rules in the API contract."""
pass
def add(self, order):
"""Implement the return value and rules in the API contract."""
pass
def remove(self, order):
"""Implement the return value and rules in the API contract."""
pass
def view(self):
"""Implement the return value and rules in the API contract."""
pass
class MatchingEngine(ABC):
@abstractmethod
def match(self, book, order):
"""Implement the return value and rules in the API contract."""
pass
class PriceTimeMatchingEngine(MatchingEngine):
def match(self, book, order):
"""Implement the return value and rules in the API contract."""
pass
class StockBroker:
def __init__(self, engine=None):
"""Initialize the state described in the problem."""
pass
def place_order(self, symbol, side, price, quantity):
"""-> (order_id, trades) where trades = [{"buy_order":, "sell_order":, "price":, "quantity":}, ...] in the order they happened; (None, []) for a bad side, price <= 0, or quantity <= 0"""
pass
def book(self, symbol):
"""-> {"bids": [{"order_id":, "price":, "quantity":}], "asks": [...]} bids by price desc then order id asc; asks by price asc then order id asc ({"bids": [], "asks": []} for an unknown symbol)"""
pass
def cancel_order(self, order_id):
"""-> True if a resting order was cancelled, False otherwise (a fully filled order cannot be cancelled)"""
pass
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter