Find 10 maximum integer out of 1 million integers.
You Have File of Containing 1 Million Integers You need To Find 10
Maximum Integer Out of Them.How You Will Do That. What is Time &
space Complexity of Algorithm that you will use then optimize the
solution..
Constraints- U can't Store Whole File in memory at one time.
Maximum Integer Out of Them.How You Will Do That. What is Time &
space Complexity of Algorithm that you will use then optimize the
solution..
Constraints- U can't Store Whole File in memory at one time.
Use a min-heap of 10 elements.Initialize the heap with first 10 elements in O(10) [constant] time.For each of the next element,check whether it is greater than root of min heap,if it is,replace that element by the next element and heapify the heap again in O(log10) [constant] time.At last extract all the 10 elements one by one in O(log10) constant time each.so space complexity O(1) time complexity O(N).
ReplyDeletevery good explanation.....
ReplyDeleteNice Explanation
ReplyDelete