Matching Engine with Order Cancellation
IMC Trading● HardNEW GRADONSITE INTERVIEWProblem statement
Process a finite sequence of limit-order operations for one asset. Each operation has one of these forms:
["BUY", orderId, price, quantity]["SELL", orderId, price, quantity]["CANCEL", orderId]
Process operations in input order. A new buy may trade with resting sells whose prices are at most its limit, while a new sell may trade with resting buys whose prices are at least its limit.
Always match the best available price first: the lowest sell price for a buy, or the highest buy price for a sell. Within one price level, resting orders match in arrival order. Each trade uses the resting order's price and the largest possible quantity between the incoming and resting orders. A partially filled incoming order keeps matching; any remainder rests at the back of its price level.
A CANCEL operation removes the unfilled remainder of the named resting order. Cancelling an unknown, already filled, or already cancelled order has no effect. Order IDs from BUY and SELL operations are globally unique and are never reused.
Return every trade in execution order as "buyOrderId|sellOrderId|price|quantity". Cancellations and submissions that do not trade produce no output.
Function
processOrders(operations: String[][]) → String[]Examples
Example 1
operations = [["BUY","b1","100","5"],["SELL","s1","90","2"],["CANCEL","b1"],["SELL","s2","95","4"],["BUY","b2","100","4"]]return = ["b1|s1|100|2","b2|s2|95|4"]Sell s1 trades two units with resting buy b1. Cancelling b1 removes its remaining three units, so s2 rests until b2 arrives.
Example 2
operations = [["SELL","s1","103","3"],["SELL","s2","103","2"],["BUY","b1","105","4"],["CANCEL","s2"],["BUY","b2","104","2"],["SELL","s3","104","1"]]return = ["b1|s1|103|3","b1|s2|103|1","b2|s3|104|1"]At price 103, FIFO priority fills s1 before s2. The cancellation removes the last unit of s2. Later, resting buy b2 trades one unit with s3 at b2's resting price.
Example 3
operations = [["BUY","b1","100","2"],["SELL","s1","100","2"],["CANCEL","b1"],["CANCEL","missing"],["SELL","s2","99","1"],["BUY","b2","99","1"]]return = ["b1|s1|100|2","b2|s2|99|1"]Order b1 is already fully filled when it is cancelled, and missing never existed, so both cancellations are no-ops.
Constraints
1 <= operations.length <= 100000- Every operation has one of the three forms described above.
orderIdcontains only ASCII letters, digits, hyphens, and underscores, has length from1through40, and does not contain|.- Every
BUYorSELLorder ID is unique and is never reused. 1 <= price, quantity <= 10^9, written as base-10 integers.- The number of generated trades and every remaining quantity fit in memory and signed 64-bit arithmetic.