Katkat
Back

Implement price-based order matcher

OptiverSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

Design and implement a price-based order matcher for unit-sized orders. You are given an array orders where each element is [type, price]: type = 1 denotes a buy order and type = -1 denotes a sell order; price is a positive integer. Process orders in arrival order using these rules: (

  1. When a buy arrives, if there exists at least one resting sell with price <= buy price, execute a trade with the resting sell having the lowest price; remove both orders; repeat while matches exist. (
  2. When a sell arrives, if there exists at least one resting buy with price >= sell price, execute a trade with the resting buy having the highest price; remove both orders; repeat while matches exist. (
  3. Any unmatched arriving order is added to the order book. At the end, return the sum of trade prices across all executed transactions. Specify the data structures you would use to support efficient matching, give the time complexity, and handle ties deterministically.