Implement Price-Time Order Matching
Company: Two Sigma
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Quick Answer: This question evaluates understanding of limit-order book mechanics, priority-based matching, stateful stream processing, and data-structure management for handling partial fills and price-time tie-breaking.
Constraints
- 0 <= len(orders) <= 2 * 10^5
- order_id values are unique
- side is either 'BUY' or 'SELL'
- 1 <= price, quantity <= 10^9
- timestamps are strictly increasing, and the input list is already in arrival order
Examples
Input: [('B1', 'BUY', 100, 10, 1), ('S1', 'SELL', 100, 7, 2)]
Expected Output: ([('B1', 'S1', 100, 7)], [('B1', 100, 3, 1)], [])
Explanation: B1 rests first. S1 arrives and sells 7 into B1 at the resting BUY price 100. B1 remains on the book with quantity 3.
Input: [('S1', 'SELL', 101, 5, 1), ('S2', 'SELL', 101, 4, 2), ('B1', 'BUY', 101, 6, 3)]
Expected Output: ([('B1', 'S1', 101, 5), ('B1', 'S2', 101, 1)], [], [('S2', 101, 3, 2)])
Explanation: B1 matches the best asks. S1 and S2 have the same price, so S1 trades first because it arrived earlier.
Input: [('B1', 'BUY', 100, 5, 1), ('B2', 'BUY', 100, 4, 2), ('S1', 'SELL', 100, 6, 3)]
Expected Output: ([('B1', 'S1', 100, 5), ('B2', 'S1', 100, 1)], [('B2', 100, 3, 2)], [])
Explanation: The incoming SELL matches the highest bid. B1 and B2 have the same bid price, so B1 fills first due to earlier time priority.
Input: [('S1', 'SELL', 102, 2, 1), ('S2', 'SELL', 101, 4, 2), ('B1', 'BUY', 103, 5, 3)]
Expected Output: ([('B1', 'S2', 101, 4), ('B1', 'S1', 102, 1)], [], [('S1', 102, 1, 1)])
Explanation: B1 buys from the lowest ask first, so S2 at 101 is matched before S1 at 102.
Input: [('B1', 'BUY', 99, 2, 1), ('S1', 'SELL', 101, 1, 2), ('B2', 'BUY', 100, 3, 3), ('S2', 'SELL', 102, 4, 4)]
Expected Output: ([], [('B2', 100, 3, 3), ('B1', 99, 2, 1)], [('S1', 101, 1, 2), ('S2', 102, 4, 4)])
Explanation: No order crosses the spread, so there are no trades. The final books are just sorted by the required price-time order.
Input: []
Expected Output: ([], [], [])
Explanation: With no orders, there are no trades and both books are empty.
Hints
- Keep each price level as a FIFO queue so that orders at the same price are matched by arrival time.
- Use a max-heap for BUY prices and a min-heap for SELL prices. If a price level becomes empty, remove stale heap entries lazily when they reach the top.