Citadel's High-Performance Order Book Question

Citadel's coding rounds put you straight into the matching engine. You build an order book that keeps price-time priority and matches crossing orders, then the interviewer layers on the order types a real exchange supports. Here is the full question, Java for both parts, and a detailed rubric.

The question

Part 1 · The matching book

Two sorted maps of price levels, bids descending and asks ascending, each level a FIFO queue so older orders fill first. A side index by order id makes cancellation cheap. Matching crosses the best bid and ask while they overlap.

import java.util.*;

class OrderBook {
    enum Side { BUY, SELL }
    static final class Order {
        final long id, price; long qty; final Side side; final long ts;
        Order(long id, Side side, long price, long qty, long ts) {
            this.id = id; this.side = side; this.price = price; this.qty = qty; this.ts = ts;
        }
    }

    private final TreeMap<Long, Deque<Order>> bids = new TreeMap<>(Collections.reverseOrder());
    private final TreeMap<Long, Deque<Order>> asks = new TreeMap<>();
    private final Map<Long, Order> index = new HashMap<>();

    void addOrder(Order o) {
        TreeMap<Long, Deque<Order>> book = (o.side == Side.BUY) ? bids : asks;
        book.computeIfAbsent(o.price, k -> new ArrayDeque<>()).addLast(o);  // time priority
        index.put(o.id, o);
    }

    void cancelOrder(long id) {
        Order o = index.remove(id);
        if (o == null) return;
        TreeMap<Long, Deque<Order>> book = (o.side == Side.BUY) ? bids : asks;
        Deque<Order> level = book.get(o.price);
        if (level != null) { level.remove(o); if (level.isEmpty()) book.remove(o.price); }
    }

    void matchOrders() {                       // fill while the book is crossed
        while (!bids.isEmpty() && !asks.isEmpty() && bids.firstKey() >= asks.firstKey()) {
            Deque<Order> bidLevel = bids.firstEntry().getValue();
            Deque<Order> askLevel = asks.firstEntry().getValue();
            Order bid = bidLevel.peekFirst(), ask = askLevel.peekFirst();
            long fill = Math.min(bid.qty, ask.qty);
            bid.qty -= fill; ask.qty -= fill;
            if (bid.qty == 0) { bidLevel.pollFirst(); index.remove(bid.id); if (bidLevel.isEmpty()) bids.pollFirstEntry(); }
            if (ask.qty == 0) { askLevel.pollFirst(); index.remove(ask.id); if (askLevel.isEmpty()) asks.pollFirstEntry(); }
        }
    }

    Long getBestBid() { return bids.isEmpty() ? null : bids.firstKey(); }
    Long getBestAsk() { return asks.isEmpty() ? null : asks.firstKey(); }

    List<long[]> getMarketDepth(Side side, int levels) {   // {price, totalQty} per level
        TreeMap<Long, Deque<Order>> book = (side == Side.BUY) ? bids : asks;
        List<long[]> depth = new ArrayList<>();
        for (Map.Entry<Long, Deque<Order>> e : book.entrySet()) {
            if (depth.size() == levels) break;
            long total = 0;
            for (Order o : e.getValue()) total += o.qty;
            depth.add(new long[]{ e.getKey(), total });
        }
        return depth;
    }
}

A TreeMap is clear but not sub-microsecond. The optimization to discuss is an array of price levels with intrusive linked lists, pooled order objects to avoid allocation, and tight cache layout. State the clean version first, then describe that path.

Part 2 · Advanced order types

Each extension is a layer on top of the book, not a rewrite. Describe the data each one adds and where it hooks into matching.

// Iceberg replenishment, triggered when the visible slice is exhausted.
void onIcebergFilled(Iceberg ico) {
    if (ico.reserve == 0) return;
    long slice = Math.min(ico.displaySize, ico.reserve);
    ico.reserve -= slice;
    Order visible = new Order(nextId(), ico.side, ico.price, slice, now());
    addOrder(visible);            // re-enters at the BACK of its price level (loses time priority)
}

How Citadel scores it

Citadel interview FAQ