Project: Limit Order Book

A limit order book holds the resting orders of one instrument, grouped by side and price level, in time order inside each level. This project builds one in three stages. Each stage is a complete program that runs the same scripted order stream, so the outputs can be compared line by line. The terms (bid, ask, depth, ticks) come from Market Data, Orders, and FIX; matching crossing orders is the next project, Project: Matching Engine.

Stage	Price levels	Orders in a level	Order lookup	Allocation per operation
1	`TreeMap<Long, ArrayDeque<Order>>`	`ArrayDeque`	`HashMap<Long, Order>`	Boxing, map entries, deques, orders
2	`Level[]` indexed by `price - minPrice`	Intrusive doubly linked list	`HashMap<Long, Order>`	Orders and map entries
3	`Level[]` as in stage 2	Intrusive list over pooled orders	fastutil `Long2ObjectOpenHashMap`	None in the steady state

Problem statement

Build a book for one instrument that accepts add, cancel, and modify requests, answers best bid and best ask at once, and prints a depth snapshot of the top N levels per side. The book is used by a single thread (an engine or a market data handler), so it has no locks.

Requirements

Prices are long ticks, quantities long, order ids long and unique.
Inside a level, orders keep arrival order (FIFO), because exchanges fill earlier orders first.
add rejects a duplicate id, a non-positive quantity, and an order that would cross the book (a buy at or above the best ask, or a sell at or below the best bid). Crossing orders are traded by a matching engine, not by this book.
cancel removes an order by id; an unknown id is reported, not thrown.
modify with the same price and a smaller quantity keeps the order's place in the queue. A price change or a quantity increase loses priority: the order moves to the back of its (new) level. This is the rule most venues use, because a larger order at the front would take fills from orders that arrived earlier.
Best bid and best ask are O(1) to read. Depth lists levels with total quantity.
Stage 3 allocates nothing per operation after warmup, checked with ThreadMXBean.

The scripted stream used by every stage:

Step	Request	Expected effect
1 to 3	add 1 buy 10025 x100, add 2 buy 10025 x200, add 3 buy 10024 x400	two bid levels
4 to 6	add 4 sell 10027 x500, add 5 sell 10028 x150, add 6 sell 10028 x250	two ask levels
7	modify 1 to 10025 x60	smaller, keeps place ahead of order 2
8	modify 2 to 10026 x200	new price, new best bid
9	cancel 3	level 10024 disappears
10	add 7 sell 10026 x10	rejected: crosses bid 10026
11	cancel 99	unknown id
12	add 4 buy 10020 x1	rejected: duplicate id

Stage 1: TreeMap levels and FIFO queues

A TreeMap keeps keys sorted, so firstKey is the best price: the bid map uses a reverse comparator so its first key is the highest bid. Each level is an ArrayDeque (from Lists and Deques) that appends at the tail and fills from the head. A HashMap from id to order makes cancel find the order without a search through levels.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

final class Order {
    final long id;
    final boolean buy;
    final long price;
    long qty;

    Order(long id, boolean buy, long price, long qty) {
        this.id = id; this.buy = buy; this.price = price; this.qty = qty;
    }
}

final class TreeBook {
    private final TreeMap<Long, ArrayDeque<Order>> bids = new TreeMap<>(Comparator.reverseOrder());
    private final TreeMap<Long, ArrayDeque<Order>> asks = new TreeMap<>();
    private final Map<Long, Order> byId = new HashMap<>();

    String add(long id, boolean buy, long price, long qty) {
        if (byId.containsKey(id)) return "reject duplicate id " + id;
        if (qty <= 0) return "reject qty " + qty;
        if (buy ? !asks.isEmpty() && price >= asks.firstKey() : !bids.isEmpty() && price <= bids.firstKey()) {
            return "reject cross " + price;
        }
        Order o = new Order(id, buy, price, qty);
        (buy ? bids : asks).computeIfAbsent(price, p -> new ArrayDeque<>()).addLast(o);
        byId.put(id, o);
        return "added " + id;
    }

    String cancel(long id) {
        Order o = byId.remove(id);
        if (o == null) return "unknown id " + id;
        TreeMap<Long, ArrayDeque<Order>> side = o.buy ? bids : asks;
        ArrayDeque<Order> level = side.get(o.price);
        level.remove(o);                       // linear in the level size
        if (level.isEmpty()) side.remove(o.price);
        return "cancelled " + id;
    }

    String modify(long id, long newPrice, long newQty) {
        Order o = byId.get(id);
        if (o == null) return "unknown id " + id;
        if (newPrice == o.price && newQty > 0 && newQty <= o.qty) {
            o.qty = newQty;                    // keeps queue position
            return "reduced " + id;
        }
        cancel(id);
        String r = add(id, o.buy, newPrice, newQty);
        return r.startsWith("added") ? "replaced " + id : r;
    }

    long bestBid() { return bids.isEmpty() ? -1 : bids.firstKey(); }
    long bestAsk() { return asks.isEmpty() ? -1 : asks.firstKey(); }

    String depth(int n) {
        return "bids " + levels(bids, n) + " asks " + levels(asks, n);
    }

    private static List<String> levels(TreeMap<Long, ArrayDeque<Order>> side, int n) {
        List<String> out = new ArrayList<>();
        for (var e : side.entrySet()) {
            if (out.size() == n) break;
            long total = 0;
            StringBuilder ids = new StringBuilder();
            for (Order o : e.getValue()) { total += o.qty; ids.append(ids.isEmpty() ? "" : ",").append(o.id); }
            out.add(e.getKey() + "x" + total + "(" + ids + ")");
        }
        return out;
    }
}

public class Main {
    public static void main(String[] args) {
        TreeBook b = new TreeBook();
        System.out.println(b.add(1, true, 10_025, 100));
        System.out.println(b.add(2, true, 10_025, 200));
        System.out.println(b.add(3, true, 10_024, 400));
        System.out.println(b.add(4, false, 10_027, 500));
        System.out.println(b.add(5, false, 10_028, 150));
        System.out.println(b.add(6, false, 10_028, 250));
        System.out.println(b.depth(5));
        System.out.println(b.modify(1, 10_025, 60));
        System.out.println(b.modify(2, 10_026, 200));
        System.out.println(b.cancel(3));
        System.out.println(b.add(7, false, 10_026, 10));
        System.out.println(b.cancel(99));
        System.out.println(b.add(4, true, 10_020, 1));
        System.out.println(b.depth(5));
        System.out.println("best " + b.bestBid() + " / " + b.bestAsk());
    }
}

Output

added 1
added 2
added 3
added 4
added 5
added 6
bids [10025x300(1,2), 10024x400(3)] asks [10027x500(4), 10028x400(5,6)]
reduced 1
replaced 2
cancelled 3
reject cross 10026
unknown id 99
reject duplicate id 4
bids [10026x200(2), 10025x60(1)] asks [10027x500(4), 10028x400(5,6)]
best 10026 / 10027

The ids in parentheses show queue order: after step 7 order 1 is still ahead of order 2 at 10025, and after step 8 order 2 sits alone at its new level. The design is short and correct, and it is the version to write first in an interview. Its costs: every price is a boxed Long, every level is a tree node plus a deque, ArrayDeque.remove(Object) scans the level, and TreeMap operations are O(log L) for L levels.

Stage 2: arrays indexed by price ticks

Most activity happens within a few hundred ticks of the best price. If the book covers a fixed band of prices, the level for price p is levels[p - minPrice]: an array index instead of a tree search. Each order holds prev and next references, so the level is an intrusive doubly linked list (the links live inside the element) and cancel unlinks in O(1) without a scan.

The best bid is an index that moves when the best level empties. The scan to the next non-empty level is bounded by the band size and is usually a few steps, because levels near the best are dense.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

final class Order {
    long id;
    boolean buy;
    long price;
    long qty;
    Order prev, next;
}

final class Level {
    Order head, tail;
    long qty;
    int count;

    void append(Order o) {
        o.prev = tail; o.next = null;
        if (tail == null) head = o; else tail.next = o;
        tail = o;
        qty += o.qty; count++;
    }

    void unlink(Order o) {
        if (o.prev == null) head = o.next; else o.prev.next = o.next;
        if (o.next == null) tail = o.prev; else o.next.prev = o.prev;
        o.prev = o.next = null;
        qty -= o.qty; count--;
    }
}

final class ArrayBook {
    private final long minPrice;
    private final Level[] bids, asks;
    private int bestBid = -1;            // index, -1 = empty
    private int bestAsk;                 // index, levels.length = empty
    private final Map<Long, Order> byId = new HashMap<>();

    ArrayBook(long minPrice, int band) {
        this.minPrice = minPrice;
        bids = new Level[band]; asks = new Level[band];
        for (int i = 0; i < band; i++) { bids[i] = new Level(); asks[i] = new Level(); }
        bestAsk = band;
    }

    private int index(long price) {
        long i = price - minPrice;
        if (i < 0 || i >= bids.length) throw new IllegalArgumentException("price outside band: " + price);
        return (int) i;
    }

    String add(long id, boolean buy, long price, long qty) {
        if (byId.containsKey(id)) return "reject duplicate id " + id;
        if (qty <= 0) return "reject qty " + qty;
        int i = index(price);
        if (buy ? i >= bestAsk : i <= bestBid) return "reject cross " + price;
        Order o = new Order();
        o.id = id; o.buy = buy; o.price = price; o.qty = qty;
        insert(o, i);
        byId.put(id, o);
        return "added " + id;
    }

    private void insert(Order o, int i) {
        if (o.buy) { bids[i].append(o); if (i > bestBid) bestBid = i; }
        else { asks[i].append(o); if (i < bestAsk) bestAsk = i; }
    }

    private void remove(Order o) {
        int i = index(o.price);
        if (o.buy) {
            bids[i].unlink(o);
            while (bestBid >= 0 && bids[bestBid].count == 0) bestBid--;
        } else {
            asks[i].unlink(o);
            while (bestAsk < asks.length && asks[bestAsk].count == 0) bestAsk++;
        }
    }

    String cancel(long id) {
        Order o = byId.remove(id);
        if (o == null) return "unknown id " + id;
        remove(o);
        return "cancelled " + id;
    }

    String modify(long id, long newPrice, long newQty) {
        Order o = byId.get(id);
        if (o == null) return "unknown id " + id;
        if (newPrice == o.price && newQty > 0 && newQty <= o.qty) {
            (o.buy ? bids : asks)[index(o.price)].qty -= o.qty - newQty;
            o.qty = newQty;
            return "reduced " + id;
        }
        cancel(id);
        String r = add(id, o.buy, newPrice, newQty);
        return r.startsWith("added") ? "replaced " + id : r;
    }

    long bestBid() { return bestBid < 0 ? -1 : minPrice + bestBid; }
    long bestAsk() { return bestAsk == asks.length ? -1 : minPrice + bestAsk; }

    String depth(int n) {
        List<String> b = new ArrayList<>(), a = new ArrayList<>();
        for (int i = bestBid; i >= 0 && b.size() < n; i--) if (bids[i].count > 0) b.add(describe(i, bids[i]));
        for (int i = bestAsk; i < asks.length && a.size() < n; i++) if (asks[i].count > 0) a.add(describe(i, asks[i]));
        return "bids " + b + " asks " + a;
    }

    private String describe(int i, Level l) {
        StringBuilder ids = new StringBuilder();
        for (Order o = l.head; o != null; o = o.next) ids.append(ids.isEmpty() ? "" : ",").append(o.id);
        return (minPrice + i) + "x" + l.qty + "(" + ids + ")";
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBook b = new ArrayBook(10_000, 64);    // prices 10000..10063
        System.out.println(b.add(1, true, 10_025, 100));
        System.out.println(b.add(2, true, 10_025, 200));
        System.out.println(b.add(3, true, 10_024, 400));
        System.out.println(b.add(4, false, 10_027, 500));
        System.out.println(b.add(5, false, 10_028, 150));
        System.out.println(b.add(6, false, 10_028, 250));
        System.out.println(b.depth(5));
        System.out.println(b.modify(1, 10_025, 60));
        System.out.println(b.modify(2, 10_026, 200));
        System.out.println(b.cancel(3));
        System.out.println(b.add(7, false, 10_026, 10));
        System.out.println(b.cancel(99));
        System.out.println(b.add(4, true, 10_020, 1));
        System.out.println(b.depth(5));
        System.out.println("best " + b.bestBid() + " / " + b.bestAsk());
        try {
            b.add(8, true, 9_000, 1);
        } catch (IllegalArgumentException e) {
            System.out.println(e.getMessage());
        }
    }
}

Output

added 1
added 2
added 3
added 4
added 5
added 6
bids [10025x300(1,2), 10024x400(3)] asks [10027x500(4), 10028x400(5,6)]
reduced 1
replaced 2
cancelled 3
reject cross 10026
unknown id 99
reject duplicate id 4
bids [10026x200(2), 10025x60(1)] asks [10027x500(4), 10028x400(5,6)]
best 10026 / 10027
price outside band: 9000

The output matches stage 1 line for line. Each Level keeps a running qty, so a depth snapshot reads one field per level instead of walking the orders. The band is the price range the array covers; prices outside it throw here. Production books handle that with a band that recenters when the price drifts, or with a sparse structure for far-away levels.

Operation	Stage 1	Stage 2
Add	O(log L)	O(1)
Cancel	O(log L) + O(level size)	O(1), plus best-price scan when the best level empties
Best bid/ask	O(log L) via `firstKey`	O(1), a field read
Depth N	O(N + orders)	O(N) over non-empty levels near the best

Stage 3: allocation-free with a pre-allocated order pool

Stage 2 still allocates an Order per add and a map entry per id, and HashMap<Long, Order> boxes every key. Stage 3 removes all three, using the techniques from Allocation-Free Code:

A pool creates every Order at startup and links the free ones through their next field, so acquire and release are two field writes.
fastutil's Long2ObjectOpenHashMap (from Primitive Collections) maps primitive long ids to orders with no boxing and no entry objects. Sized up front, its put and remove do not resize.
Results are int codes instead of strings, and the depth snapshot writes into caller-supplied long[] arrays.

The program runs the scripted stream (printing is allowed there), then a generated stream of one million operations after a warmup, and reads getThreadAllocatedBytes before and after.

Java

import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
import java.lang.management.ManagementFactory;

final class Order {
    long id;
    boolean buy;
    long price;
    long qty;
    Order prev, next;
}

final class OrderPool {
    private Order free;
    private int available;

    OrderPool(int capacity) {
        for (int i = 0; i < capacity; i++) { Order o = new Order(); o.next = free; free = o; }
        available = capacity;
    }

    Order acquire() {
        Order o = free;
        if (o == null) return null;           // caller rejects: pool exhausted
        free = o.next; o.next = null; available--;
        return o;
    }

    void release(Order o) {
        o.id = 0; o.qty = 0; o.prev = null;
        o.next = free; free = o; available++;
    }

    int available() { return available; }
}

final class Level {
    Order head, tail;
    long qty;
    int count;

    void append(Order o) {
        o.prev = tail; o.next = null;
        if (tail == null) head = o; else tail.next = o;
        tail = o;
        qty += o.qty; count++;
    }

    void unlink(Order o) {
        if (o.prev == null) head = o.next; else o.prev.next = o.next;
        if (o.next == null) tail = o.prev; else o.next.prev = o.prev;
        o.prev = o.next = null;
        qty -= o.qty; count--;
    }
}

final class PooledBook {
    static final int OK = 0, DUPLICATE = 1, BAD_QTY = 2, CROSS = 3, UNKNOWN = 4, OUT_OF_BAND = 5, FULL = 6;

    private final long minPrice;
    private final Level[] bids, asks;
    private int bestBid = -1, bestAsk;
    private final Long2ObjectOpenHashMap<Order> byId;
    private final OrderPool pool;

    PooledBook(long minPrice, int band, int capacity) {
        this.minPrice = minPrice;
        bids = new Level[band]; asks = new Level[band];
        for (int i = 0; i < band; i++) { bids[i] = new Level(); asks[i] = new Level(); }
        bestAsk = band;
        byId = new Long2ObjectOpenHashMap<>(capacity);
        pool = new OrderPool(capacity);
    }

    int add(long id, boolean buy, long price, long qty) {
        if (byId.containsKey(id)) return DUPLICATE;
        if (qty <= 0) return BAD_QTY;
        long li = price - minPrice;
        if (li < 0 || li >= bids.length) return OUT_OF_BAND;
        int i = (int) li;
        if (buy ? i >= bestAsk : i <= bestBid) return CROSS;
        Order o = pool.acquire();
        if (o == null) return FULL;
        o.id = id; o.buy = buy; o.price = price; o.qty = qty;
        if (buy) { bids[i].append(o); if (i > bestBid) bestBid = i; }
        else { asks[i].append(o); if (i < bestAsk) bestAsk = i; }
        byId.put(id, o);
        return OK;
    }

    int cancel(long id) {
        Order o = byId.remove(id);
        if (o == null) return UNKNOWN;
        int i = (int) (o.price - minPrice);
        if (o.buy) {
            bids[i].unlink(o);
            while (bestBid >= 0 && bids[bestBid].count == 0) bestBid--;
        } else {
            asks[i].unlink(o);
            while (bestAsk < asks.length && asks[bestAsk].count == 0) bestAsk++;
        }
        pool.release(o);
        return OK;
    }

    int modify(long id, long newPrice, long newQty) {
        Order o = byId.get(id);
        if (o == null) return UNKNOWN;
        if (newPrice == o.price && newQty > 0 && newQty <= o.qty) {
            (o.buy ? bids : asks)[(int) (o.price - minPrice)].qty -= o.qty - newQty;
            o.qty = newQty;
            return OK;
        }
        boolean buy = o.buy;
        cancel(id);
        return add(id, buy, newPrice, newQty);
    }

    /** Writes up to n levels as price, qty pairs; returns the number of levels written. */
    int depth(boolean bidSide, long[] out, int n) {
        int k = 0;
        if (bidSide) {
            for (int i = bestBid; i >= 0 && k < n; i--)
                if (bids[i].count > 0) { out[2 * k] = minPrice + i; out[2 * k + 1] = bids[i].qty; k++; }
        } else {
            for (int i = bestAsk; i < asks.length && k < n; i++)
                if (asks[i].count > 0) { out[2 * k] = minPrice + i; out[2 * k + 1] = asks[i].qty; k++; }
        }
        return k;
    }

    long bestBid() { return bestBid < 0 ? -1 : minPrice + bestBid; }
    long bestAsk() { return bestAsk == asks.length ? -1 : minPrice + bestAsk; }
    int live() { return byId.size(); }
    int poolAvailable() { return pool.available(); }
}

public class Main {
    static final com.sun.management.ThreadMXBean MX =
            (com.sun.management.ThreadMXBean) ManagementFactory.getThreadMXBean();
    static long allocated() { return MX.getThreadAllocatedBytes(Thread.currentThread().threadId()); }

    static final String[] CODES = {"OK", "DUPLICATE", "BAD_QTY", "CROSS", "UNKNOWN", "OUT_OF_BAND", "FULL"};
    static final long[] levels = new long[10];

    static String depth(PooledBook b) {
        StringBuilder s = new StringBuilder("bids");
        int n = b.depth(true, levels, 5);
        for (int k = 0; k < n; k++) s.append(' ').append(levels[2 * k]).append('x').append(levels[2 * k + 1]);
        s.append(" | asks");
        n = b.depth(false, levels, 5);
        for (int k = 0; k < n; k++) s.append(' ').append(levels[2 * k]).append('x').append(levels[2 * k + 1]);
        return s.toString();
    }

    // Generated stream: bids at 10480..10499, asks at 10501..10520, so nothing crosses.
    static long seed = 42, nextId = 1_000;
    static final long[] liveIds = new long[4_096], livePx = new long[4_096], liveQty = new long[4_096];
    static int liveCount;

    static long rnd() { seed = seed * 6364136223846793005L + 1442695040888963407L; return seed >>> 33; }

    static void run(PooledBook b, int ops) {
        for (int n = 0; n < ops; n++) {
            long r = rnd();
            int action = (int) (r & 3);
            if (action == 0 || liveCount < 1_000) {                    // add
                boolean buy = (r & 4) != 0;
                long px = buy ? 10_499 - (r >> 3) % 20 : 10_501 + (r >> 3) % 20;
                long qty = 2 + (r >> 10) % 100;
                if (b.add(nextId, buy, px, qty) == PooledBook.OK) {
                    liveIds[liveCount] = nextId; livePx[liveCount] = px; liveQty[liveCount] = qty; liveCount++;
                }
                nextId++;
                continue;
            }
            int k = (int) ((r >> 3) % liveCount);
            if (action == 1) {                                          // cancel
                b.cancel(liveIds[k]);
                liveCount--;
                liveIds[k] = liveIds[liveCount]; livePx[k] = livePx[liveCount]; liveQty[k] = liveQty[liveCount];
            } else if (action == 2 && liveQty[k] > 1) {                 // reduce: keeps priority
                liveQty[k] /= 2;
                b.modify(liveIds[k], livePx[k], liveQty[k]);
            } else if (action == 3) {                                   // reprice by one tick away from mid
                livePx[k] += livePx[k] < 10_500 ? (livePx[k] > 10_480 ? -1 : 0) : (livePx[k] < 10_520 ? 1 : 0);
                b.modify(liveIds[k], livePx[k], liveQty[k]);
            }
        }
    }

    public static void main(String[] args) {
        PooledBook s = new PooledBook(10_000, 64, 16);
        System.out.println(CODES[s.add(1, true, 10_025, 100)] + " " + CODES[s.add(2, true, 10_025, 200)]
                + " " + CODES[s.add(3, true, 10_024, 400)] + " " + CODES[s.add(4, false, 10_027, 500)]
                + " " + CODES[s.add(5, false, 10_028, 150)] + " " + CODES[s.add(6, false, 10_028, 250)]);
        System.out.println(depth(s));
        System.out.println("modify 1: " + CODES[s.modify(1, 10_025, 60)] + ", modify 2: " + CODES[s.modify(2, 10_026, 200)]
                + ", cancel 3: " + CODES[s.cancel(3)]);
        System.out.println("add 7: " + CODES[s.add(7, false, 10_026, 10)] + ", cancel 99: " + CODES[s.cancel(99)]
                + ", add 4 again: " + CODES[s.add(4, true, 10_020, 1)] + ", add 8 at 9000: " + CODES[s.add(8, true, 9_000, 1)]);
        System.out.println(depth(s));
        System.out.println("best " + s.bestBid() + " / " + s.bestAsk() + ", live " + s.live() + ", pool free " + s.poolAvailable());

        PooledBook b = new PooledBook(10_000, 1_024, 4_096);
        for (int w = 0; w < 20; w++) run(b, 200_000);           // warmup: lets the JIT compile run()
        long before = allocated();
        run(b, 1_000_000);
        long bytes = allocated() - before;
        System.out.println("live orders: " + b.live() + ", live + free = capacity: " + (b.live() + b.poolAvailable() == 4_096));
        System.out.println("bytes/op < 1: " + (bytes < 1_000_000));
        System.out.println("best " + b.bestBid() + " / " + b.bestAsk());
    }
}

Output

OK OK OK OK OK OK
bids 10025x300 10024x400 | asks 10027x500 10028x400
modify 1: OK, modify 2: OK, cancel 3: OK
add 7: CROSS, cancel 99: UNKNOWN, add 4 again: DUPLICATE, add 8 at 9000: OUT_OF_BAND
bids 10026x200 10025x60 | asks 10027x500 10028x400
best 10026 / 10027, live 5, pool free 11
live orders: 1601, live + free = capacity: true
bytes/op < 1: true
best 10499 / 10501

The scripted part prints the same book as stages 1 and 2, with result codes in place of messages. After warmup, a million adds, cancels, reductions, and reprices allocate less than one byte per operation on average; the program prints a threshold check instead of an exact byte count, so the output does not depend on JIT timing. The pool check (live + free = capacity) catches a leak: a cancel path that forgot release would make it false.

Points that make the stage allocation-free, and the costs they bring:

release clears the order's fields. A reference kept after release would read the next order's data; the pool cannot detect that, so ownership rules ("only the book holds Order references") are part of the design.
modify with a price change reuses the pool through cancel and add, so it never needs a second order.
The pool has a fixed capacity. add returns FULL instead of allocating, and capacity is set from the venue's limit on open orders.
Long2ObjectOpenHashMap is sized for the capacity at construction. A map that grows would allocate a new table during trading.

Parts of the project

Part	Stage	Purpose
`TreeMap` levels with reverse comparator for bids	1	Sorted levels, best price is `firstKey`
`ArrayDeque` per level	1	FIFO time priority
`HashMap<Long, Order>`	1, 2	Cancel and modify by id without a scan
Modify rule (reduce keeps priority, otherwise re-queue)	1 to 3	Matches venue priority rules
Cross check in `add`	1 to 3	Keeps the book uncrossed until a matching engine exists
`Level[]` indexed by `price - minPrice`	2, 3	O(1) level lookup
Intrusive `prev`/`next` links, running level `qty`	2, 3	O(1) cancel, O(1) level quantity
`bestBid`/`bestAsk` indexes with bounded scan	2, 3	O(1) top of book
`OrderPool` free list	3	No allocation per order
`Long2ObjectOpenHashMap` presized	3	No boxing, no entries, no resize
`int` result codes, `long[]` depth output	3	No strings on the hot path
`ThreadMXBean.getThreadAllocatedBytes` check	3	Proves the steady state allocates nothing

Extension tasks

Add queuePosition(id): the quantity ahead of an order in its level. Stage 2 can compute it by walking from head.
Support several instruments: one book per instrument id in an array, with each book's band set from its reference price.
Recenter the band when the best price comes within K ticks of an edge, by copying levels into a shifted array once.
Replace the boolean buy branches with two Side objects that hold their own Level[], best index, and comparison direction.
Publish book changes (level added, level quantity changed, level removed) as events, the input format of a market-by-price feed.
Measure stage 1 and stage 3 with JMH on the same generated stream and compare operations per second and allocation rate.

Interview points

A book is two sides of price levels; each level is a FIFO queue of orders, which gives price-time priority.
A TreeMap with a reverse comparator for bids is the simplest correct design; firstKey is the best price.
An id-to-order map makes cancel O(1) lookup; an intrusive doubly linked list makes the unlink O(1) too.
Arrays indexed by price - minPrice give O(1) level access for a bounded price band; the best index moves by a short scan when a level empties.
Keep a running quantity per level so depth snapshots do not walk orders.
Reducing quantity keeps queue priority; increasing it or changing price loses priority.
An allocation-free book pre-allocates orders in a pool, uses primitive-keyed maps sized up front, and returns codes instead of strings.
Pools need strict ownership: a reference used after release reads another order's data.
getThreadAllocatedBytes before and after a warmed-up loop verifies zero allocation.

Summary

Stage 1: TreeMap levels, ArrayDeque queues, HashMap by id; O(log L) operations and allocation everywhere.
Stage 2: Level[] by tick index, intrusive lists, best-price indexes; O(1) add, cancel, and top of book.
Stage 3: the same structure with an order pool and a fastutil map; no allocation per operation after warmup.
All stages accept add, cancel, and modify, reject crossing and duplicate orders, and print the same depth.
The book does not match orders; Project: Matching Engine adds that.