Online Stock Exchange

A tiny exchange: traders place buy and sell orders on an instrument, and something has to decide which ones turn into a trade. The class model matters more than the matching algorithm here - get Order and OrderBook right and the matching logic is a dozen lines.

Requirements

Functional

• A trader places a buy or sell order for a quantity of an instrument, either at a fixed price (limit order) or at whatever the best available price is (market order).
• A buy order matches a sell order when their prices cross; a trade is created for the overlapping quantity.
• Partially filled orders stay on the book for their remaining quantity.
• A trader can cancel an order that hasn't fully filled yet.

Non-functional

• Matching must always prefer the best price first (highest bid, lowest ask), then earliest order at that price - price-time priority, not first-come-first-served across all prices.
• Adding a new order type (say, stop-loss) should extend Order, not require rewriting OrderBook's matching loop.

Design

OrderBook holds two sides - bids and asks - each kept sorted by price-time priority, and its match method only ever looks at the best order on each side. Order itself carries whether it's a limit or market order as data (a price, or none), so the book doesn't need a different code path per order type.

1. 1The trader submits an order for one instrument - the exchange routes by instrument symbol.
2. 2The order lands on the correct side (bids or asks) of that instrument’s book, sorted by price-time priority.
3. 3The book peeks at the best bid and best ask; if they cross, a fill happens for the overlapping quantity.
4. 4A trade is recorded once a match is found; both orders’ remaining quantities are reduced.
5. 5A trader can pull an order that hasn’t fully filled; the book removes it from its side.

A Trade is the one output of matching that outlives the match call - it's what both traders and any downstream settlement system actually care about, independent of how the book got there.

Class diagram

usescreates

OrderBook holds two priority-ordered sides of Orders on one Instrument and emits Trades when a bid and an ask cross.

Code

import java.time.Instant;

import java.util.*;

 

enum Side { BUY, SELL }

 

class Instrument {

final String symbol;

 

Instrument(String symbol) {

this.symbol = symbol;

}

}

 

class Order {

final String id;

final Side side;

final Double price;

int quantity;

final Instant placedAt;

 

Order(String id, Side side, Double price, int quantity) {

this.id = id;

this.side = side;

this.price = price;

this.quantity = quantity;

this.placedAt = Instant.now();

}

 

boolean isMarketOrder() {

return price == null;

}

}

 

class Trade {

final String buyOrderId;

final String sellOrderId;

final double price;

final int quantity;

 

Trade(String buyOrderId, String sellOrderId, double price, int quantity) {

this.buyOrderId = buyOrderId;

this.sellOrderId = sellOrderId;

this.price = price;

this.quantity = quantity;

}

}

 

class OrderBook {

final Instrument instrument;

private final List<Order> bids = new ArrayList<>();

private final List<Order> asks = new ArrayList<>();

 

OrderBook(Instrument instrument) {

this.instrument = instrument;

}

 

void addOrder(Order order) {

List<Order> side = order.side == Side.BUY ? bids : asks;

side.add(order);

side.sort((a, b) -> {

double pa = a.isMarketOrder() ? (order.side == Side.BUY ? Double.MAX_VALUE : 0) : a.price;

double pb = b.isMarketOrder() ? (order.side == Side.BUY ? Double.MAX_VALUE : 0) : b.price;

int byPrice = order.side == Side.BUY ? Double.compare(pb, pa) : Double.compare(pa, pb);

return byPrice != 0 ? byPrice : a.placedAt.compareTo(b.placedAt);

});

}

 

void cancelOrder(String orderId) {

bids.removeIf(o -> o.id.equals(orderId));

asks.removeIf(o -> o.id.equals(orderId));

}

 

List<Trade> match() {

List<Trade> trades = new ArrayList<>();

while (!bids.isEmpty() && !asks.isEmpty()) {

Order bestBid = bids.get(0);

Order bestAsk = asks.get(0);

boolean crosses = bestBid.isMarketOrder() || bestAsk.isMarketOrder()

|| bestBid.price >= bestAsk.price;

if (!crosses) break;

 

int qty = Math.min(bestBid.quantity, bestAsk.quantity);

double price = bestAsk.isMarketOrder() ? bestBid.price : bestAsk.price;

trades.add(new Trade(bestBid.id, bestAsk.id, price, qty));

 

bestBid.quantity -= qty;

bestAsk.quantity -= qty;

if (bestBid.quantity == 0) bids.remove(0);

if (bestAsk.quantity == 0) asks.remove(0);

}

return trades;

}

}

 

class Exchange {

private final Map<String, OrderBook> books = new HashMap<>();

 

void registerInstrument(Instrument instrument) {

books.put(instrument.symbol, new OrderBook(instrument));

}

 

List<Trade> placeOrder(String symbol, Order order) {

OrderBook book = books.get(symbol);

book.addOrder(order);

return book.match();

}

 

void cancelOrder(String symbol, String orderId) {

books.get(symbol).cancelOrder(orderId);

}

}

Design decisions

• OrderBook is per-instrument, never a single book for the whole exchange. Orders for AAPL and orders for GOOG never interact, so keeping one book per instrument means matching is naturally scoped and one busy instrument's order volume never slows down matching for a quiet one.
• A market order is a limit order with no price, not a separate class. Both are the same object with the same fields; a market order simply matches against the best available price on the other side instead of requiring its own price to cross. Splitting it into its own class would duplicate every field except one.
• Price-time priority is an ordering rule on the book's data structure, not a loop condition scattered through match. Bids are kept sorted highest-price-first (ties broken by earlier timestamp), asks lowest-price-first, so match only ever has to peek at the head of each side rather than scan for "the best one."
• What's missing for a real system: this book is single-threaded and in-memory; a real exchange needs the match step to be atomic under concurrent order submission (a lock per instrument, or a single-writer queue per book), and needs every fill to be durably logged before being acknowledged, since a trade can't be un-happened once reported to a trader.

Common follow-ups

• What happens to a market order that arrives when the opposite side of the book is empty? match()'s while loop simply never runs an iteration, so the market order sits on the book indefinitely as if it were a very aggressive limit order. A real exchange would reject or expire an unfilled market order immediately instead of resting it, since "take the best available price" is meaningless with no counter-liquidity.
• How would you add a stop-loss order? A StopLossOrder carrying a trigger price; OrderBook.match wouldn't touch it directly - a separate watcher monitors trade prices and, once triggered, hands the order to the book as an ordinary market or limit order, leaving match()'s core loop untouched.
• Two orders at the same price, submitted a millisecond apart - which fills first, and where is that guaranteed? The earlier one, guaranteed by addOrder's sort comparator breaking price ties on placedAt - price-time priority isn't a runtime check inside match(), it's baked into how the book stays sorted the moment an order is inserted.
• Why would one OrderBook for the whole exchange be a problem at scale? Every match() call would need to filter for the right instrument, and a burst of volume in one hot stock would contend for the same book and slow matching for every other, unrelated instrument - one book per instrument means AAPL's volume never touches GOOG's book.

Check yourself

Question 1 of 4

Why is a market order modeled as an Order with price set to none, instead of a separate MarketOrder class?