An online computer system for trading stocks needs to process orders of the form
ID: 3685230 • Letter: A
Question
An online computer system for trading stocks needs to process orders of the form “buy 100 shares at $x each” or “sell 100 shares at $y each.” A buy order for $x can only be processed if there is an existing sell order with price $y such that y x. Likewise, a sell order for $y can only be processed if there is an existing buy order with price $x such that y x. If a buy or sell order is entered but cannot be processed, it must wait for a future order that allows it to be processed. Describe a scheme that allows buy and sell orders to be entered in O(log n) time, independent of whether or not they can be immediately processed.
Explanation / Answer
Two heaps are required , one to maintain sell orders, the other for buy orders. We need to store both the quantity and price in the same node of the heap taking price as the key. When an order comes in, pop the items one after the other from the corresponding priority queue, until a large enough quantity has been removed, subject to the constraint. On failure, add the popped items back onto the priority queue. Add the other orders onto the othre queues available.
On average we would expect this algorithm to run inO(logn)time, however in the worst case, it will take O(nlogn)time,because in order to full an order we may have to empty the queue.