Most orders never trade. They get cancelled - and that is the hot path.
Build the book. Then survive the cancel storm.
An exchange matching engine sees far more cancels than fills - most resting orders never trade. Getting the matching logic right is table stakes; the interview is really about what your cancel costs.
PRICE-TIMEbest price, then oldest
PARTIAL FILLSrest the remainder
O(1) CANCELno scanning
TOMBSTONESdelete lazily
Interview lens: nearly everyone writes a working book. The follow-up - “now cancel is on the hot path, what does it cost you?” - is what separates candidates.