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.
Saturday, September 3, 2011
Find 10 maximum integer out of 1 million integers
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment