Amazon Interview Question SDE1s
Country: India
hey why do we need to store all elements for max heap we could just store the top k elemts and every time a new number comes we need to check the leaves i am sure min heap would be better but please tell me why we need to store all elemenst for max heap
Build k max heap will work.
Every time a new element comes add it to k max heap if required.
K max heap will maintain K largest element at a give time.
I think this will work, the heap could be very big, but at any given time it will be accurate.
So each node has the number of times an element is searched for, as the key. Every time a data element comes in the corresponding node is incremented and the heap nodes with highest number of searches is always at the top and is continually updated.
I think you need min-heap. Every time you get an element in the stream, compare it against the top of the heap. If current is larger than the top, remove the top and insert the current, else discard the current.
This is right. If you need the max k, then you use a min-heap, and restrict yourself to O(k) space and O(k log k) time.
By using a max-heap, you will have to insert all elements and this will essentially be same as heap sort.
Either max heap or min heap. It depends on your available memory, because max heap has to store all elements while min heap just store k elements. Also they have different time complexity. Choose either solution depending on your needs.
- Yue March 26, 2013