Adobe Interview Question
Implement the logic(with data structure and code). A stream of data (consider integer) is coming to you, one has to predict the top k elements out of the stream at any given time. As the stream is real time there might be 1000 per second or 50 per second.
Interview Answer
Anonymous
Feb 15, 2015
Storing the stream in heap is a viable option. For k elements implement min heap of size k if the newer element is greater than root, then it deserves to be in the heap else discard it. It would take O(nlogn) time on average. I guess the interviewer was looking for a O(n) answer, which I could not give, but he seemed satisfied with the DS and algo I gave him