PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCoaches

Quick Overview

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.

  • medium
  • Two Sigma
  • Coding & Algorithms
  • Software Engineer

Implement Price-Time Order Matching

Company: Two Sigma

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a simplified limit-order matching engine for a stock exchange. You receive a stream of orders. Each order has: - `order_id`: unique identifier - `side`: `BUY` or `SELL` - `price`: limit price - `quantity`: positive integer share quantity - `timestamp`: arrival time, or an equivalent sequence number Matching rules: 1. A buy order can match a resting sell order when the buy price is greater than or equal to the sell price. 2. A sell order can match a resting buy order when the sell price is less than or equal to the buy price. 3. Among eligible resting orders, match by best price first: highest bid for buys, lowest ask for sells. 4. If multiple resting orders have the same price, match the earliest order first. 5. A trade quantity is the minimum of the incoming order's remaining quantity and the resting order's remaining quantity. 6. Partially filled orders keep their remaining quantity. Fully filled orders leave the book. Any unfilled remainder of the incoming order is added to the book. Implement an API such as `add_order(order)` that processes one order and returns the trades generated by that order. Each trade should include the buy order id, sell order id, execution price, and executed quantity. Also maintain the current order book state so that future orders can match against it. Discuss the data structures you would use and handle partial fills, price-time tie breaking, heap updates, and order ids correctly.

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.

Implement a simplified limit-order matching engine for a stock exchange. You are given a stream of orders in arrival order. Each order is a 5-tuple: (order_id, side, price, quantity, timestamp) Rules: 1. A BUY order can match resting SELL orders with sell_price <= buy_price. 2. A SELL order can match resting BUY orders with buy_price >= sell_price. 3. Match against the best resting price first. - BUY incoming order matches the lowest ask first. - SELL incoming order matches the highest bid first. 4. If multiple resting orders have the same price, match the earliest resting order first. 5. Trade quantity is the minimum of the incoming remaining quantity and the resting remaining quantity. 6. Partially filled orders keep their remaining quantity. Fully filled orders leave the book. 7. Any unfilled remainder of the incoming order is added to the book. 8. The execution price of each trade is the resting order's price. Instead of writing a class, implement a function `solution(orders)` that simulates repeated `add_order(order)` calls from left to right. Return a tuple: - trades: a list of trades in the exact order they occur. Each trade is (buy_order_id, sell_order_id, execution_price, executed_quantity) - buy_book: the remaining BUY orders, sorted by descending price, then ascending timestamp. Each entry is (order_id, price, remaining_quantity, timestamp) - sell_book: the remaining SELL orders, sorted by ascending price, then ascending timestamp. Each entry is (order_id, price, remaining_quantity, timestamp) Do not aggregate orders at the same price; keep individual resting orders.

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

  1. Keep each price level as a FIFO queue so that orders at the same price are matched by arrival time.
  2. 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.
Last updated: May 15, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Compute Piecewise Linear Interpolation - Two Sigma (medium)
  • Implement an In-Memory Database - Two Sigma (hard)
  • Merge two sorted linked lists - Two Sigma (hard)
  • Merge Two Sorted Lists - Two Sigma (hard)
  • Evaluate Piecewise Linear Function - Two Sigma (medium)