Market Order Book
Headlands Technologies● MediumFULLTIMEPHONE SCREENProblem statement
Implement a finite in-memory order book for one instrument. Process the operations in operations from left to right.
ADD id BUY price quantityadds a new active buy order.ADD id SELL price quantityadds a new active sell order.CANCEL idremoves that active order completely.QUERYrecords the current best bid and best ask.
The best bid is the highest active buy price. The best ask is the lowest active sell price. At either best price, aggregate the quantities of all active orders at that price.
For every QUERY, append one output string in the exact format bestBidPrice bestBidQuantity bestAskPrice bestAskQuantity. If one side is empty, use price -1 and quantity 0 for that side.
This book does not match or execute orders. An add remains active until it is canceled.
Function
processMarketOrderBook(operations: String[]) → String[]Examples
Example 1
operations = ["ADD b1 BUY 100 5","ADD b2 BUY 100 3","ADD s1 SELL 104 7","QUERY","CANCEL b1","QUERY"]return = ["100 8 104 7","100 3 104 7"]The first query aggregates both buy orders at price 100. After canceling b1, only quantity 3 remains at the best bid.
Example 2
operations = ["QUERY","ADD s1 SELL 105 4","ADD s2 SELL 103 2","ADD b1 BUY 99 6","QUERY"]return = ["-1 0 -1 0","99 6 103 2"]The empty book uses the required sentinels. After the adds, price 103 is a better ask than 105.
Example 3
operations = ["ADD x BUY 10 2","ADD y BUY 12 5","QUERY","CANCEL y","QUERY"]return = ["12 5 -1 0","10 2 -1 0"]Canceling the only order at price 12 exposes price 10 as the next best bid.
Constraints
1 <= operations.length <= 100000.- Each operation has exactly one of the four documented forms.
- Order IDs are unique among all
ADDoperations and contain only ASCII letters and digits. - Every
CANCELnames an active order. 1 <= price, quantity <= 10^9.- Every aggregated quantity fits in a signed 64-bit integer.