Match Limit Orders with Price-Time Priority

Question

The candidate is asked to implement a system that matches limit orders based on price-time priority, ensuring that the orders are processed in the correct sequence according to their prices and timestamps.

Codemia · Accepted Answer

To tackle the problem of matching limit orders with price-time priority, we need to understand the mechanics of limit orders in trading. A limit order is an order to buy or sell a stock at a specified price or better. The price-time priority means that orders are executed based on the best price available, and if there are multiple orders at the same price, they are executed in the order they were received. We can use a priority queue (or a min-heap) to manage the buy and sell orders. The priority queue will allow us to efficiently retrieve the best price available for matching. We will maintain two separate queues: one for buy orders and one for sell orders. When a new order arrives, we will check the queues to see if it can be matched with existing orders. 1. Initialize two priority queues: one for buy orders and one for sell orders. 2. When a new limit order arrives: - If it is a buy order, check the sell queue for the lowest sell price. - If it is a sell order, check the buy queue for the highest buy price. 3. Match orders based on price-time priority and remove matched orders from the queues. 4. If an order cannot be matched, add it to the appropriate queue. The time complexity for inserting an order into the priority queue is O(log n), where n is the number of orders in the queue. Matching orders involves checking the top of the queue, which is O(1), and removing matched orders, which is also O(log n). Therefore, the overall complexity for processing an order is O(log n). ```python import heapq class Order: def __init__(self, order_id, price, quantity, timestamp): self.order_id = order_id self.price = price self.quantity = quantity self.timestamp = timestamp def __lt__(self, other): if self.price == other.price: return self.timestamp < other.timestamp return self.price < other.price class OrderBook: def __init__(self): self.buy_orders = [] # max-heap self.sell_orders = [] # min-heap def add_order(self, order): if order.quantity <= 0: return if order.price > 0: heapq.heappush(self.sell_orders, order) else: heapq.heappush(self.buy_orders, order) def match_orders(self): while self.buy_orders and self.sell_orders: best_buy = -self.buy_orders[0].price best_sell = self.sell_orders[0].price if best_buy >= best_sell: # Match logic here pass else: break ```

Match Limit Orders with Price-Time Priority

Two Sigma

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Framing

Approach

Submit Your Answer

Two Sigma Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string