Implement an order book and price-time matching engine in Python

In this article

1. Before you start
2. Why interviewers ask this
3. Order book and price-time matching from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the machine coding rounds guide, where the habit of choosing data structures from the required operations applies to every problem.

If you have built a least recently used (LRU) cache in Python, you have already joined a hash map to an ordered structure. An order book does the same thing with prices.

Why interviewers ask this

A matching engine problem shows, within one coding round, whether you choose data structures from the operations a system needs or from habit. The operations are few and sharp: add an order, cancel one, read the best price, and trade against the best price.

Candidates report prompts of this family at trading firms: build a book that holds bids and asks, save and load it in a serialized format, filter trades by timestamp and total the profit, or find the bug in an engine that mishandles partial fills. No public source says which firm asks which, so none is named here.

A weak answer re-sorts a list after every order. A strong answer names the operations, gives each price a queue, keeps a map from order id to order, and says what an amend does to priority. A Staff-level answer adds a sequence number for deterministic replay, tests for partial fills and says where the design would change under load.

Order book and price-time matching from first principles

Order book

An order book is the record of every resting limit order for one instrument, kept as two sides, bids to buy and asks to sell, each grouped into price levels that hold a queue of orders in arrival order, so the engine can see who will trade at which price and who is first.

Price-time priority

Price-time priority is a matching rule that ranks resting orders first by price, so the highest bid and the lowest ask trade first, and then by arrival within one price, so the earliest order at that price trades first.

Limit order

A limit order is an order to buy or sell a stated quantity at a stated price or better: a buy trades at its price or lower, a sell at its price or higher, and any quantity that cannot trade at once waits in the book.

In plain words

Picture a market with two lines of people. Sellers each name the lowest price they accept. Buyers each name the highest price they pay. At every price, people stand in the order they arrived.

A new person walks to the best line on the other side. They trade with whoever stands first. If they still want more, they move to the next line. If no line suits them, they join the end of their own line.

The analogy breaks in one place. On a real book people can leave the line at any time, and someone who changes their request goes to the back.

A matching engine is the code that takes each incoming order, trades it against the opposite side of the order book under price-time priority, and rests whatever is left.

Step 1: Each side maps a price to a queue, and the best price sits at the front

An order book stores each side as a map from price to a queue of orders, and the two sides are read from opposite ends: the highest bid and the lowest ask are the best prices. Input: orders with a side, price and quantity. Output: a structure where the best price and its oldest order are found quickly.

The queue holds orders in arrival order, and within one price level that order decides who trades first. The Chicago Mercantile Exchange (CME) documentation, as read in October 2026, describes time priority within a price level: orders at the same price are filled in the order they arrived, so the first order at a level is matched first. A Python double-ended queue adds at one end and removes from the other in constant time.

A resting book is never crossed in continuous trading: the best bid is always below the best ask, because an order that met the other side would already have traded. You now know the shape of the data; the next step uses it.

Step 2: An incoming order matches the best opposite price first

An incoming order trades against the best price on the opposite side first, then against the next best, until it is filled or its limit stops it. Input: one order. Output: a list of trades and the quantity still unfilled.

The loop reads the best opposite price. A buy stops when that price is above its limit, and a sell stops when it is below. Otherwise it takes the oldest resting order at that price and trades the smaller of the two quantities.

The trade price is the resting order's price. The usual convention is that the order already in the book stated its price first, so the newcomer accepts it; check the rules of any venue named in a prompt. A trade that uses up the resting order removes it from the front of its queue, and an empty level is dropped. After the loop, the incoming order is either done or has quantity left.

Step 3: Cancel and amend decide who keeps their place in the queue

A cancel removes an order through a hash map from order id to order, and an amend that changes price or raises quantity is a cancel plus a new order, which sends it to the back of its queue. Input: an order id. Output: the book without that order, or the order at a new place in line.

Removing an order from the middle of a queue is slow. An intrusive doubly linked list per level, with the id map pointing at the node, removes from the middle in constant time; the simpler lazy design marks the order dead and skips it at the front, which this page's code uses.

The CME page, as read in October 2026, says an order loses its priority when its quantity is increased, its price is changed or its account is changed. This engine keeps priority on a decrease, a design choice that varies by venue.

The common error is an amend that edits the order in place, which lets a trader jump ahead of everyone at the same price.

Step 4: A limit order rests its remainder and a market order does not

A limit order whose quantity is only partly filled rests the rest at the tail of its price queue, while a market order never rests. A market order is an order with no price limit that trades against whatever the opposite side offers, level after level, until it is filled or the side is empty. Input: the unfilled quantity after matching. Output: a resting order, or nothing.

A partial fill is not an error. The resting order keeps its place with a smaller quantity, and the incoming order keeps walking. When a limit order rests, its price level may not exist yet. The engine then creates the level and adds the price to the heap of prices for that side.

Each level is created once and each price enters its heap once, so heap entries stay in step with levels. The tail position is what gives later arrivals at the same price a lower priority than this order.

Step 5: The price levels need a structure that finds the best price fast

The structure for price levels decides the speed of every order. Python's standard library has no sorted map, so a heap of prices with a map from price to queue is the usual choice; Java or C++ would use a sorted map, which also iterates levels in order for depth and serialization.

A sorted array reads the best price at the end and drops it in constant time, but a new level in the middle shifts later elements, which takes linear time. In the Python heap documentation, heap[0] is always the smallest item, so the best price is read in constant time. Push and pop restore the heap along one root-to-leaf path, which takes logarithmic time. A balanced tree adds or drops a level in logarithmic time.

Bids need the highest price first, so store negated prices in the min-heap.

Each incoming order matches the best opposite price first, trades execute at the resting order's price, an id map finds any order for a cancel or an amend, and unfilled quantity of a limit order rests at the tail of its price queue.

1 · Two sides2 · Match3 · Cancel4 · Rest5 · PricesReplay

Step-by-step description

1. Bids and asks each hold queues by price.
2. The incoming order trades at the resting price.
3. An id map finds any order directly.
4. The remainder joins the queue tail.
5. A heap or map finds the best price.

• Each incoming order matches the best opposite price first.
• Trades execute at the resting order's price.
• An id map finds any order for a cancel or an amend.
• Unfilled quantity of a limit order rests at the tail of its price queue.

Text description of the diagram

• A sorted array inserts a new price level in linear time.
• A heap reads the best price in constant time and adds a level in logarithmic time.

Worked example

The engine below is the whole design in one class. A heap per side holds prices, a dictionary per side maps each price to a deque, and a dictionary maps each order id to its order. A cancelled order is marked dead and skipped lazily.

import heapq
from collections import deque

class Order:
    def __init__(self, oid, side, price, qty):
        self.oid, self.side, self.price, self.qty = oid, side, price, qty
        self.live = True

class Book:
    def __init__(self):
        self.levels = {"buy": {}, "sell": {}}   # price -> deque of Order
        self.heaps = {"buy": [], "sell": []}    # buys store -price
        self.by_id = {}
        self.trades = []                        # (maker, taker, price, qty)

    def best(self, side):
        heap, lv = self.heaps[side], self.levels[side]
        while heap:
            price = abs(heap[0])
            q = lv.get(price)
            while q and not q[0].live:          # skip cancelled orders
                q.popleft()
            if q:
                return price
            lv.pop(price, None)                 # level is empty: drop it
            heapq.heappop(heap)
        return None

    def submit(self, oid, side, price, qty):    # price None = market order
        other = "sell" if side == "buy" else "buy"
        order = Order(oid, side, price, qty)
        while order.qty > 0:
            best = self.best(other)
            if best is None:
                break
            if price is not None and (best > price if side == "buy" else best < price):
                break
            resting = self.levels[other][best][0]
            fill = min(order.qty, resting.qty)
            self.trades.append((resting.oid, oid, best, fill))
            order.qty -= fill
            resting.qty -= fill
            if resting.qty == 0:
                resting.live = False
                self.levels[other][best].popleft()
                del self.by_id[resting.oid]
        if order.qty > 0 and price is not None:
            lv = self.levels[side]
            if price not in lv:
                lv[price] = deque()
                heapq.heappush(self.heaps[side], -price if side == "buy" else price)
            lv[price].append(order)
            self.by_id[oid] = order
        return order.qty

    def cancel(self, oid):
        o = self.by_id.pop(oid, None)
        if o is None:
            return False
        o.live = False
        return True

    def amend(self, oid, price, qty):
        o = self.by_id.get(oid)
        if o is None:
            return False
        if price == o.price and 0 < qty <= o.qty:
            o.qty = qty                         # decrease keeps priority
            return True
        side = o.side
        self.cancel(oid)                        # anything else loses priority
        if qty > 0:
            self.submit(oid, side, price, qty)
        return True

The starting book is illustrative: three bids and two asks, shown as quantity at price. Order 1 buys 10 at 100, order 2 buys 10 at 100 after it, order 3 buys 5 at 99, order 4 sells 7 at 101 and order 5 sells 4 at 102.¹ Order 6 then sells 30 with a limit of 99. It fills 10 against order 1 and 10 against order 2, both at 100, and 5 against order 3 at 99. That trades 25 units worth 2,495 at an average price of 99.8, and the remaining 5 rest as the best ask at 99.¹

Next, order 7 is a market buy for 15. It walks three ask levels: 5 at 99, 7 at 101 and 3 at 102, worth 1,508 at an average of 100.5333, and leaves 1 unit at 102.¹

Text description of the diagram

• The sell order for 30 units fills 10, 10 and 5 units and leaves 5 resting.
• The sell order walks the bids from the best price down and, inside one price, from the oldest order.

The sell order for 30 units fills 10, 10 and 5 units and leaves 5 resting.¹ Cancelling and amending use the same structures: the id map finds the order and the flag removes it from play.

Trade-offs and edge cases

The price-time rule is only one way to allocate trades. The CME page is titled "Supported Matching Algorithms", which signals that a venue can offer more than one rule, but this page implements price-time alone, so read the prompt for the rule it names.

• Lazy deletion. Dead orders sit in queues until they reach the front, so memory is released late. A book with heavy cancellation can keep stale levels, which the loop cleans when it reads the best price. The linked-list alternative unlinks at once and leaves no stale entries, at the cost of more code.
• Arrival order. Use a sequence counter that the engine increments, not a wall-clock timestamp, because two orders can share a timestamp and ties would be broken arbitrarily.
• Self-trade. A trader's buy can meet their own resting sell. Many venues provide self-trade prevention modes, and candidates report it among the edge cases in bug-fix prompts. This engine does not implement it; you would compare the owners of both orders before filling and then skip, reduce or cancel as the stated mode requires.
• Price type. Use integer ticks, never floats, so that equal prices compare equal.
• Serializing the book. Dump each side as a list of price levels, each with its orders in queue order. On load, re-add the orders in that order. If you sort by id or time on load you may change priority. With a heap of prices, sort the level prices before writing them, because heap order is not best-first order.
• Input validation. submit here does not reject a duplicate live order id, which would overwrite the id map entry and leave a stray order that cannot be cancelled. Reject it before matching if the prompt allows.
• Complexity. An order that sweeps several levels costs about one heap removal per emptied level, plus constant work per fill, and the lazy cleanup of cancelled orders is amortised over the orders that were cancelled. Reads of the best price stay cheap.

For other problems that combine maps with ordering, the in-memory database assessment, time-based key-value stores and event and log processing problems use similar tools, and a job scheduler also keeps a heap ordered by time.

How to answer it in an interview

The spoken structure: name the two sides, name the three structures, walk one match, then state the amend rule. For design practice of this kind, the low level design interview questions list has neighbouring problems.

Common mistakes

• "I sort one list of all orders by price and time on every insert." (wrong) That costs linear time or worse per order. (right) "A heap of prices and a queue per price."
• "An amend edits the order in place." (wrong) It lets a trader keep a place they gave up. (right) "A price change or a quantity increase is a cancel plus a new order at the tail."
• "The trade happens at the incoming order's price." (wrong) The usual convention is the resting order's price. (right) "Trades execute at the price of the order already in the book."
• "I use wall-clock timestamps for priority." (wrong) Equal timestamps give arbitrary ties. (right) "A sequence number that only increases."
• "A partial fill means the order is rejected." (wrong) The filled quantity trades and the rest rests or continues. (right) "I fill what I can and rest the remainder of a limit order."

Follow-up questions

How do you save and restore an order book in a serialized format?

Write each side as price levels in best-first order, each holding its orders in queue order with id, quantity and sequence number. Restore by re-adding orders in that order, so queue positions match, and rebuild the id map as you go.

How do you filter trades by timestamp and calculate the profit?

Keep trades in sequence order, which is already sorted by time, and use binary search (bisect) on the timestamps to cut the window. For realised profit per trader, match each sell against that trader's earlier buys first in first out, so each matched unit adds sell price minus buy price; any figures you show are illustrative.

How do you handle a partial fill?

Trade the smaller of the two quantities, reduce both, and keep going. A resting order with quantity left stays at the front of its queue; an incoming limit order with quantity left rests at the tail of its own level.

What does a market order do when the book is empty?

It finds no opposite price, trades nothing and does not rest, because it has no limit price to rest at. Whether to reject or drop it is a rule you state; the engine here simply returns the unfilled quantity.

How do you find the bug in a matching engine?

Test the usual suspects with tiny books: a wrong trade price, queue jumping after an amend, a dropped partial remainder, an empty level left behind, and a self-trade. Write each as a small book, one incoming order and an expected trade list.

What happens to queue position when an order is amended?

A quantity increase or a price change sends the order to the back, as the CME documentation, read in October 2026, describes. A decrease varies by venue; say which rule you choose.

Sources

1. Supported Matching Algorithms - CME Group Client Systems Wiki — Chicago Mercantile Exchange Group (page undated; accessed 2026-10-26), 26 Oct 2026
2. heapq - Heap queue algorithm (Python 3 documentation) — Python Software Foundation (accessed 2026-10-26), 26 Oct 2026
3. collections - deque objects (Python 3 documentation) — Python Software Foundation (accessed 2026-10-26), 26 Oct 2026