Interview Guides

Heap-Based Order Book Matcher | Dataford Interview Questions - Dataford - Ace your Interview

Heap-Based Order Book Matcher

Medium

Coding

Problem

Scenario

You’re building a simplified matching engine for a fintech brokerage app that processes hundreds of thousands of order events per minute during volatile markets. A bug in matching logic can directly impact execution quality and regulatory reporting, so correctness matters.

Problem

Implement an order book for a single asset. You will receive a sequence of operations ops, each being either:

("POST", order_id, side, price, qty)
("CANCEL", order_id)

Where:

side is either "BUY" or "SELL"
price and qty are positive integers
order_id is unique across all POSTs

Matching Rules (Price-Time Priority)

After each POST, repeatedly match as long as the book is crossed:

Best BUY = highest price (tie-breaker: earlier arrival)
Best SELL = lowest price (tie-breaker: earlier arrival)
A match occurs when best_buy.price >= best_sell.price
Trade quantity = min(buy_remaining_qty, sell_remaining_qty)
Trade price = the resting order’s price (the order that arrived earlier)
If an order is fully filled, it is removed from the book; otherwise it remains with reduced quantity.

Cancellation

CANCEL makes the order immediately inactive if it is still resting with remaining quantity. Canceling an unknown or already-filled order is a no-op.

Output

Return a list of executed trades in the order they occur. Each trade is: (buy_order_id, sell_order_id, trade_price, trade_qty)

Examples

Example 1

Input: ops = [("POST","b1","BUY",100,5), ("POST","s1","SELL",90,2), ("POST","s2","SELL",95,10)]
Output: [("b1","s1",100,2), ("b1","s2",100,3)]
Explanation: Both sells cross the resting buy at 100. Trades are priced at the resting order (b1), so price is 100 for both fills.

Example 2

Input: ops = [("POST","b1","BUY",100,5), ("POST","b2","BUY",105,4), ("POST","s1","SELL",103,10)]
Output: [("b2","s1",105,4), ("b1","s1",100,5)]
Explanation: The sell matches the best buy (b2 at 105) for 4, then continues matching the next buy (b1 at 100) for 5. Each trade is priced at the resting buy.

Notes

Use lazy deletion for canceled/filled orders in heaps.
FIFO must be respected within the same price level.

Examples

Example 1

Inputops = [("POST","b1","BUY",100,5), ("POST","s1","SELL",90,2), ("POST","s2","SELL",95,10)]Output[("b1","s1",100,2), ("b1","s2",100,3)]WhyBoth sells cross the resting buy at 100. The buy fills 2 with s1, then 3 with s2, priced at the resting buy’s price.

Example 2

Inputops = [("POST","b1","BUY",100,5), ("POST","b2","BUY",105,4), ("POST","s1","SELL",103,10)]Output[("b2","s1",105,4), ("b1","s1",100,5)]WhyThe sell matches the best buy (105) for 4, then continues to the next buy (100) for 5. Each trade is priced at the resting buy.

Constraints

1 <= len(ops) <= 2 * 10^5
1 <= price <= 10^9
1 <= qty <= 10^9
order_id is unique across all POST operations
CANCEL may reference an unknown or already-fully-filled order (no-op)

Function Signature

def process_marketplace_ops(ops: list[tuple]) -> list[tuple[str, str, int, int]]:

Problem

Scenario

Problem

Implement an order book for a single asset. You will receive a sequence of operations ops, each being either:

("POST", order_id, side, price, qty)
("CANCEL", order_id)

Where:

side is either "BUY" or "SELL"
price and qty are positive integers
order_id is unique across all POSTs

Matching Rules (Price-Time Priority)

After each POST, repeatedly match as long as the book is crossed:

Best BUY = highest price (tie-breaker: earlier arrival)
Best SELL = lowest price (tie-breaker: earlier arrival)
A match occurs when best_buy.price >= best_sell.price
Trade quantity = min(buy_remaining_qty, sell_remaining_qty)
Trade price = the resting order’s price (the order that arrived earlier)
If an order is fully filled, it is removed from the book; otherwise it remains with reduced quantity.

Cancellation

CANCEL makes the order immediately inactive if it is still resting with remaining quantity. Canceling an unknown or already-filled order is a no-op.

Output

Return a list of executed trades in the order they occur. Each trade is: (buy_order_id, sell_order_id, trade_price, trade_qty)

Examples

Example 1

Input: ops = [("POST","b1","BUY",100,5), ("POST","s1","SELL",90,2), ("POST","s2","SELL",95,10)]
Output: [("b1","s1",100,2), ("b1","s2",100,3)]
Explanation: Both sells cross the resting buy at 100. Trades are priced at the resting order (b1), so price is 100 for both fills.

Example 2

Input: ops = [("POST","b1","BUY",100,5), ("POST","b2","BUY",105,4), ("POST","s1","SELL",103,10)]
Output: [("b2","s1",105,4), ("b1","s1",100,5)]
Explanation: The sell matches the best buy (b2 at 105) for 4, then continues matching the next buy (b1 at 100) for 5. Each trade is priced at the resting buy.

Notes

Use lazy deletion for canceled/filled orders in heaps.
FIFO must be respected within the same price level.

Examples

Example 1

Example 2

Constraints

1 <= len(ops) <= 2 * 10^5
1 <= price <= 10^9
1 <= qty <= 10^9
order_id is unique across all POST operations
CANCEL may reference an unknown or already-fully-filled order (no-op)

Function Signature

def process_marketplace_ops(ops: list[tuple]) -> list[tuple[str, str, int, int]]:

Practice Python

Python 3.10

Open on desktop for the full Python editor with syntax highlighting and autocomplete.

Up next

Cluster Marketplace Users for PersonalizationMedium

Design Marketplace Listing RankerHard ADesign Personalized Marketplace Search RankingHard

Next question

Heap-Based Order Book Matcher

Medium

Coding

Problem

Scenario

Problem

Implement an order book for a single asset. You will receive a sequence of operations ops, each being either:

("POST", order_id, side, price, qty)
("CANCEL", order_id)

Where:

side is either "BUY" or "SELL"
price and qty are positive integers
order_id is unique across all POSTs

Matching Rules (Price-Time Priority)

After each POST, repeatedly match as long as the book is crossed:

Best BUY = highest price (tie-breaker: earlier arrival)
Best SELL = lowest price (tie-breaker: earlier arrival)
A match occurs when best_buy.price >= best_sell.price
Trade quantity = min(buy_remaining_qty, sell_remaining_qty)
Trade price = the resting order’s price (the order that arrived earlier)
If an order is fully filled, it is removed from the book; otherwise it remains with reduced quantity.

Cancellation

CANCEL makes the order immediately inactive if it is still resting with remaining quantity. Canceling an unknown or already-filled order is a no-op.

Output

Return a list of executed trades in the order they occur. Each trade is: (buy_order_id, sell_order_id, trade_price, trade_qty)

Examples

Example 1

Input: ops = [("POST","b1","BUY",100,5), ("POST","s1","SELL",90,2), ("POST","s2","SELL",95,10)]
Output: [("b1","s1",100,2), ("b1","s2",100,3)]
Explanation: Both sells cross the resting buy at 100. Trades are priced at the resting order (b1), so price is 100 for both fills.

Example 2

Input: ops = [("POST","b1","BUY",100,5), ("POST","b2","BUY",105,4), ("POST","s1","SELL",103,10)]
Output: [("b2","s1",105,4), ("b1","s1",100,5)]
Explanation: The sell matches the best buy (b2 at 105) for 4, then continues matching the next buy (b1 at 100) for 5. Each trade is priced at the resting buy.

Notes

Use lazy deletion for canceled/filled orders in heaps.
FIFO must be respected within the same price level.

Examples

Example 1

Example 2

Constraints

1 <= len(ops) <= 2 * 10^5
1 <= price <= 10^9
1 <= qty <= 10^9
order_id is unique across all POST operations
CANCEL may reference an unknown or already-fully-filled order (no-op)

Function Signature

def process_marketplace_ops(ops: list[tuple]) -> list[tuple[str, str, int, int]]:

Problem

Scenario

Problem

Implement an order book for a single asset. You will receive a sequence of operations ops, each being either:

("POST", order_id, side, price, qty)
("CANCEL", order_id)

Where:

side is either "BUY" or "SELL"
price and qty are positive integers
order_id is unique across all POSTs

Matching Rules (Price-Time Priority)

After each POST, repeatedly match as long as the book is crossed:

Best BUY = highest price (tie-breaker: earlier arrival)
Best SELL = lowest price (tie-breaker: earlier arrival)
A match occurs when best_buy.price >= best_sell.price
Trade quantity = min(buy_remaining_qty, sell_remaining_qty)
Trade price = the resting order’s price (the order that arrived earlier)
If an order is fully filled, it is removed from the book; otherwise it remains with reduced quantity.

Cancellation

CANCEL makes the order immediately inactive if it is still resting with remaining quantity. Canceling an unknown or already-filled order is a no-op.

Output

Return a list of executed trades in the order they occur. Each trade is: (buy_order_id, sell_order_id, trade_price, trade_qty)

Examples

Example 1

Input: ops = [("POST","b1","BUY",100,5), ("POST","s1","SELL",90,2), ("POST","s2","SELL",95,10)]
Output: [("b1","s1",100,2), ("b1","s2",100,3)]
Explanation: Both sells cross the resting buy at 100. Trades are priced at the resting order (b1), so price is 100 for both fills.

Example 2

Input: ops = [("POST","b1","BUY",100,5), ("POST","b2","BUY",105,4), ("POST","s1","SELL",103,10)]
Output: [("b2","s1",105,4), ("b1","s1",100,5)]
Explanation: The sell matches the best buy (b2 at 105) for 4, then continues matching the next buy (b1 at 100) for 5. Each trade is priced at the resting buy.

Notes

Use lazy deletion for canceled/filled orders in heaps.
FIFO must be respected within the same price level.

Examples

Example 1

Example 2

Constraints

1 <= len(ops) <= 2 * 10^5
1 <= price <= 10^9
1 <= qty <= 10^9
order_id is unique across all POST operations
CANCEL may reference an unknown or already-fully-filled order (no-op)

Function Signature

def process_marketplace_ops(ops: list[tuple]) -> list[tuple[str, str, int, int]]:

Practice Python

Python 3.10

Open on desktop for the full Python editor with syntax highlighting and autocomplete.

Up next

Cluster Marketplace Users for PersonalizationMedium

Design Marketplace Listing RankerHard ADesign Personalized Marketplace Search RankingHard

Next question