Stock Broker

hard · limit order book, price-time priority

Brief-reported interview attribution (unverified): Amazon

How to approach an LLD round

Requirements

  • 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
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. TryGetValueCharacter joke · No posting date

    I found the bug. It was me. I was the bug.

  2. Me at 2amCharacter joke · No posting date

    I renamed the function and everything broke. The function was load-bearing.

  3. AntyCharacter joke · No posting date

    I asked the hash for one shard. It gave me a lecture on consistency.