Implement price-based order matcher
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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.
Quick Answer: 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.