Implement price-based order matcher
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
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.
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.
Input: ([[1, 10], [-1, 9]],)
Expected Output: 10
Explanation: The buy at 10 rests first. The later sell at 9 matches that resting buy, and the trade occurs at the resting buy price 10.
Input: ([[-1, 7], [1, 10]],)
Expected Output: 7
Explanation: The sell at 7 rests first. The later buy at 10 matches that resting sell, and the trade occurs at the resting sell price 7.
Input: ([[1, 10], [1, 12], [-1, 11], [-1, 9], [-1, 13], [1, 14]],)
Expected Output: 35
Explanation: Sell 11 matches resting buy 12 for price 12, sell 9 matches resting buy 10 for price 10, and buy 14 matches resting sell 13 for price 13. Total = 12 + 10 + 13 = 35.
Input: ([[-1, 5], [-1, 5], [1, 5], [1, 5]],)
Expected Output: 10
Explanation: Two sell orders at price 5 rest in arrival order. Each buy at 5 matches one sell at trade price 5, for a total of 10. If tie-breaking matters, the earlier sell is matched first.
Solution
def solution(orders):
import heapq
# sells: min-heap by (price, arrival_index)
# buys: max-heap simulated with (-price, arrival_index)
sells = []
buys = []
total = 0
seq = 0
for order_type, price in orders:
if order_type == 1: # buy
if sells and sells[0][0] <= price:
sell_price, _ = heapq.heappop(sells)
total += sell_price # trade at resting order price
else:
heapq.heappush(buys, (-price, seq))
else: # sell
if buys and -buys[0][0] >= price:
neg_buy_price, _ = heapq.heappop(buys)
total += -neg_buy_price # trade at resting order price
else:
heapq.heappush(sells, (price, seq))
seq += 1
return total
Time complexity: O(n log n). Space complexity: O(n).
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.