Order Matching Engine
Updated
Problem statement
An exchange keeps an order book of buy and sell orders for one stock. Orders arrive one at a time. Each order is orders[i] = [orderId, side, price, quantity], where side is 0 for a buy and 1 for a sell. Orders arrive in the order they appear in orders.
When an order arrives, it trades against orders already resting in the book, using price-time priority:
- A buy can trade with resting sells whose price is at most its own price. It takes the lowest-priced sell first.
- A sell can trade with resting buys whose price is at least its own price. It takes the highest-priced buy first.
- Among resting orders with the same price, the one that arrived earlier trades first.
- Each trade is at the resting order's price, for the smaller of the two remaining quantities.
- The incoming order keeps trading until it is fully filled or nothing it can trade with is left. Any quantity left over then rests in the book.
Record each trade as a fill [buyOrderId, sellOrderId, price, quantity]. Return all fills in the order they happen.
Function
matchOrders(orders: int[][]) → int[][]Examples
Example 1
orders = [[1,1,101,5],[2,1,100,3],[3,0,99,4],[4,0,101,6]]return = [[4,2,100,3],[4,1,101,3]]Orders 1 and 2 are sells, and they rest in the book. Order 3 buys at 99, but the cheapest sell is 100, so it rests too. Order 4 buys 6 at up to 101. It first takes all 3 from order 2 at 100, the cheapest sell, then 3 from order 1 at 101. Order 1 keeps 2 in the book.
Example 2
orders = [[10,0,50,2],[11,0,50,2],[12,1,50,3]]return = [[10,12,50,2],[11,12,50,1]]Buys 10 and 11 have the same price, and order 10 arrived first, so the sell fills it first: 2 units. The last unit goes to order 11.
Example 3
orders = [[5,0,30,4],[6,0,32,1],[7,1,29,3]]return = [[6,7,32,1],[5,7,30,2]]The sell of 3 at 29 first meets the highest buy, order 6 at 32, and trades 1 unit at 32, the resting price. It then trades 2 units with order 5 at 30. Order 5 keeps 2 in the book.
Example 4
orders = [[1,0,10,1],[2,1,11,1]]return = []The buy at 10 is below the sell at 11, so the orders never cross and there are no fills.
Constraints
1 <= orders.length <= 5000orders[i].length == 41 <= orderId <= 109, and allorderIdvalues are different.sideis0or1.1 <= price, quantity <= 106
More Jane Street interview questions
- Code Editor FoldingONSITE INTERVIEW · Seen Oct 2026
- Exact-Sixty Dice Game ValueONSITE INTERVIEW · Seen Oct 2026
- Expected Value of Modified DiceONSITE INTERVIEW · Seen Oct 2026
- Spaceship Equipment LoadoutONSITE INTERVIEW · Seen Oct 2026
- Two-Tower Strategy GameONSITE INTERVIEW · Seen Oct 2026
- Wizard Scroll Allocation StrategyONSITE INTERVIEW · Seen Oct 2026
- Sort TradesPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Order Book Data ValidationONSITE INTERVIEW · Seen Nov 2025
- Biggest Daily Move and Longest Rising StreakOA · ONSITE INTERVIEW · Seen Apr 2021
- Maximum-Scoring Consecutive Tree LevelsPHONE SCREEN · Seen Nov 2026
Similar questions at other companies
- Design Authentication ManagerOracle · ONSITE INTERVIEWOracle interview questions
- Delayed Job SchedulerWalmart Labs · ONSITE INTERVIEW
- Thread-Safe Task Storage and Worker DispatchNuro · ONSITE INTERVIEWNuro interview questions
- Notification Deduplication WindowGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Implement a Min-Priority QueueAmazon · ONSITE INTERVIEW
- Helpdesk Ticket ProcessingThe Walt Disney Company · ONSITE INTERVIEWThe Walt Disney Company interview questions
- Execute Tasks by PrioritySnowflake · ONSITE INTERVIEWSnowflake interview questions
- Priority Job Scheduler with CooldownsGoogle · ONSITE INTERVIEWGoogle interview questions
- Trip Booking with the Earliest Free DriverRippling · ONSITE INTERVIEWRippling interview questions
- Reusable Number AllocatorDropbox · ONSITE INTERVIEWDropbox interview questions