Why this matters: the match loop is short, and every line of it is a rule from lesson 01 made executable. What interviewers verify here is exact correspondence — the code must enforce price-time priority by construction, not by comparator luck — and the two classic bugs (re-inserted partial fills, searching cancels) announce themselves instantly in code that has them.
The records
class Order {
long id;
Side side; // BUY or SELL
long price; // integer ticks — never floats for money
long remaining; // shrinks as fills happen
Order prev, next; // intrusive links within the level queue
Level level; // back-pointer for O(1) cancel
}
class Level {
long price;
long totalQty; // cached; kept equal to sum of remainders
Order head, tail; // FIFO: head is oldest = first to fill
}class Book {
TreeMap<Long, Level> bids; // descending: best bid first
TreeMap<Long, Level> asks; // ascending: best ask first
HashMap<Long, Order> byId; // resting orders only
List<Trade> trades; // append-only
}submit(): the match loop
void submit(Order incoming) {
TreeMap<Long, Level> opposite = (incoming.side == BUY) ? asks : bids;
while (incoming.remaining > 0 && !opposite.isEmpty()
&& crosses(incoming, opposite.firstKey())) {
Level best = opposite.firstEntry().getValue();
Order resting = best.head; // time priority: oldest first
long fillQty = Math.min(incoming.remaining, resting.remaining);
trades.add(new Trade(incoming.id, resting.id,
resting.price, // maker sets the price
fillQty, nextSeq++));
incoming.remaining -= fillQty;
resting.remaining -= fillQty;
best.totalQty -= fillQty;
if (resting.remaining == 0) {
unlinkHead(best); // exhausted: leaves the book
byId.remove(resting.id);
if (best.head == null) opposite.pollFirstEntry(); // empty level dies
}
// else: resting shrank IN PLACE — it keeps its queue position.
// Removing and re-adding it here is the classic time-priority bug.
}
if (incoming.remaining > 0) rest(incoming); // limit remainder rests
}crosses is the one-line rule: a buy crosses while incoming.price >= bestAskPrice; a sell while incoming.price <= bestBidPrice. Narrate the trade line as you write it — price comes from the resting order: the maker was there first and set the terms; the taker accepts them. Getting this backwards produces trades at wrong prices, which in this domain is not a bug but an incident.
rest(): the remainder joins the book
void rest(Order o) {
TreeMap<Long, Level> side = (o.side == BUY) ? bids : asks;
Level lvl = side.computeIfAbsent(o.price, p -> new Level(p));
appendToTail(lvl, o); // newest = last = lowest time priority
lvl.totalQty += o.remaining;
o.level = lvl;
byId.put(o.id, o); // indexed the moment it rests
}Appending to the tail is time priority again, from the other direction: the fill path reads heads, the rest path writes tails, and the queue between them is the rule.
cancel(): the index pays off
boolean cancel(long orderId) {
Order o = byId.remove(orderId);
if (o == null) return false; // already filled or never rested
o.level.totalQty -= o.remaining;
unlink(o); // intrusive links: O(1), no search
if (o.level.head == null) removeLevel(o.level);
return true;
}Six lines, constant time, and the entire justification for the intrusive-list-plus-index design. A cancel that searches is the second classic bug of this problem — and in a venue where cancel traffic typically dwarfs trade traffic, an O(n) cancel is a performance lie told by the average case.
Market orders: the variant, contained
void submitMarket(Order incoming) {
// same loop with crosses() == true while the opposite side is non-empty
matchAgainstOpposite(incoming, /*crosses*/ (i, px) -> true);
if (incoming.remaining > 0) reject(incoming); // v1 contract: no resting
}The match loop is untouched — a market order is a limit order with an always-true cross test, which is precisely why the loop was written against a predicate. The remainder rule (reject) is the defended choice from lesson 01, and here it's one visible line, easy to swap if the interviewer's venue wants convert-to-limit.
What you'd say about complexity
Each fill is O(1); a submit that eats k resting orders across m levels is O(k + m log L) with L price levels — the log only from level insert/delete on the sorted map. Cancel is O(1). And the worst-case framing from lesson 01 belongs here: the expensive submit is a large order sweeping many levels, its cost is proportional to the trades it produces, and no operation ever scans orders it doesn't touch. That last sentence is the honest summary of the whole structure.
Key takeaway
The loop enforces the rules by construction: fills read level heads (time priority), levels are consumed best-first (price priority), partial fills shrink in place and keep their spot, remainders rest at the tail and get indexed, and cancel is an O(1) unlink because the index and intrusive links were designed as one decision. Market orders reuse the loop through a predicate — the sign the core was shaped right.