Saturday, September 3, 2011

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 @ one time e.g. if u
will do that gigabyte of memory may be required so that should be
avoided.

Answer:
Using the first 10 numbers, build a max heap. Then add each
number into the 11th array position (always the 11th position) and
perform the up-heap operation. At the end of the input, discard the
11th number in the heap. The remaining numbers will be the 10 maximum.
O(n log k) where n = the number of items in the list and k = the
number of maximum items you want.

No comments:

Post a Comment