Implement price-based order matcher

Company: Optiver

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

Design and implement a price-based order matcher for unit-sized orders. You are given an array orders where each element is [type, price]: type = 1 denotes a buy order and type = -1 denotes a sell order; price is a positive integer. Process orders in arrival order using these rules: ( 1) When a buy arrives, if there exists at least one resting sell with price <= buy price, execute a trade with the resting sell having the lowest price; remove both orders; repeat while matches exist. ( 2) When a sell arrives, if there exists at least one resting buy with price >= sell price, execute a trade with the resting buy having the highest price; remove both orders; repeat while matches exist. ( 3) Any unmatched arriving order is added to the order book. At the end, return the sum of trade prices across all executed transactions. Specify the data structures you would use to support efficient matching, give the time complexity, and handle ties deterministically.

Overview: This question evaluates competency in data structures and algorithmic design for price-based order matching systems, including priority-based matching, efficient order book maintenance, and deterministic tie-breaking requirements.

Design and implement a price-based order matcher for unit-sized orders. You are given an array `orders` where each element is `[type, price]`: - `type = 1` means a buy order - `type = -1` means a sell order - `price` is a positive integer Process the orders in arrival order using these rules: 1. When a buy order arrives, if there is at least one resting sell order with `sell_price <= buy_price`, execute a trade with the resting sell that has the lowest price. 2. When a sell order arrives, if there is at least one resting buy order with `buy_price >= sell_price`, execute a trade with the resting buy that has the highest price. 3. Among multiple resting orders with the same best price, match the earliest one that arrived. 4. Every order has size 1, so an arriving order can execute at most one trade. If it does not trade, add it to the order book. 5. The trade price is the price of the resting order already in the book. Return the sum of trade prices across all executed trades.

Constraints

0 <= len(orders) <= 200000
Each order is of the form [type, price]
type is either 1 or -1
1 <= price <= 10^9
The answer fits in a signed 64-bit integer

Examples

Input: ([],)

Expected Output: 0

Explanation: There are no orders, so no trades occur.

Input: ([[1, 100]],)

Expected Output: 0

Explanation: A single buy order cannot trade because there is no resting sell order.

Hints

You need fast access to the cheapest resting sell and the most expensive resting buy.
To break ties deterministically for equal prices, store an arrival index along with each order.

Approach

Approach: two priority queues (one per side of the book)

This simulates a price-time-priority matching engine for unit-sized orders using two heaps:

sells — a min-heap of resting sell orders keyed by (price, seq). The cheapest sell sits at the top; ties go to the order that arrived first (smaller seq).
buys — a max-heap of resting buy orders, emulated with Python's min-heap by storing (-price, seq). The negation makes the highest buy price surface first; among equal prices the smaller seq (earliest arrival) is popped first.

seq is an incrementing counter giving each order a unique arrival index, which enforces rule 3 (earliest-arrived wins on a price tie).

Per-order logic

For each [order_type, price]:

Buy (type == 1): peek at sells[0]. If the best (lowest) sell price <= price, the buy is marketable — pop that sell and add its price to total (rule 5: trade at the resting order's price). Otherwise the buy rests: push (-price, seq) onto buys.
Sell (type == -1): peek at buys[0]. The best buy price is -buys[0][0]; if it's >= price, pop that buy and add the resting buy price to total. Otherwise push (price, seq) onto sells.

Each arriving order executes at most one trade (size 1, rule 4), so we pop exactly one resting order or rest the new one — never both.

Why it's correct

Heaps guarantee O(1) access to the best resting price on each side, and the seq tiebreak reproduces FIFO ordering at equal prices. The trade price always comes from the popped resting order, matching the spec. Returning total gives the sum of all executed trade prices.

Time complexity:

O(n log n)

Space complexity:

O(n)

Quick Overview