Yahoo Interview Question Software Development Managers
Country: United States
Interview Type: Phone Interview
My solution was to maintain a max-heap and a map that maps ticker to the corresponding node in the heap. At every update, we look-up the node and update the value, but also note if it is an increase or decrease in value. If increase, we do a sift-up, if decrease, we do a sift-down on the heap for that node. For giving the top five values at any point of time, we don't want to disturb the order in the heap so we would copy the top five levels to a different memory and then perform 5 extract and heapifies on it.
I don't think we need to often delete the tickers. And even if we need to, we can always update the value of stock to 0 to push it down.
But you think the operations if we would use a min-heap. I believe that a max-heap can finish the task.
Sorry did not understand what u meant by "finish the task". We do want the task to be finished, don't we?
Sorry, I mean using a max-heap can display the top 5 stock prices at any given point of time. But a min-heap may be better considering the time complexity.
if the number of elements in the heap is smaller than 5, push the new element and update the heap. Otherwise, compare the new element (say n) with the first element (say m) in heap, if n<m, discard n, otherwise, replace m with n and adjust the heap.
What if you have a stock value in top-5, say MSFT and the value goes down. You need to check if there is a new contender for the top-5 spot among all those other tickers that were discarded while building the heap last time. One way is to build it all over again - O(n). Expensive, isn't it?
How about a max heap of size 5. One of the last two elements in the Heap Array(List) is the smallest. Therefore,
1) lastElem = list.get(list.length()-1))
2) lastButOneElem = list.get(list.length()-2))
3) int smallestIndex = lastElem .compareTo(lastButOneElem) > 0 ? list.length()-2 : list.length()-1
4) list.set(smallestIndex , newElemFromStream)
5) heapUp(smallestIndex)
Yeah, but if it's a minheap, than it's guaranteed that the root node will be the minimum, so you can just compare it against that node. Than, if the new element is greater in value than the root node, than we delete the root node, which will take O(log n), and we insert the new node O(log n); here n is 1 since it's a root node, so it's relatively easy.
The first idea is maintaining a min-heap of size 5 at any ticker. I will update this post if I have a better solution.
- Jason November 22, 2013