algorithm - Write a program to find 100 largest numbers out of an array of 1 billion numbers -

i attended interview asked "write program find 100 largest numbers out of array of 1 billion numbers."

i able give brute force solution sort array in o(nlogn) time complexity , take last 100 numbers.

arrays.sort(array); 

the interviewer looking better time complexity, tried couple of other solutions failed answer him. there better time complexity solution?

you can keep priority queue of 100 biggest numbers, iterate through billion numbers, whenever encounter number greater smallest number in queue (the head of queue), remove head of queue , add new number queue.

edit: dev noted, priority queue implemented heap, complexity of insertion queue o(logn)

in worst case billionlog2(100) better billionlog2(billion)

in general, if need largest k numbers set of n numbers, complexity o(nlogk) rather o(nlogn), can significant when k small comparing n.

edit2:

the expected time of algorithm pretty interesting, since in each iteration insertion may or may not occur. probability of i'th number inserted queue probability of random variable being larger @ least i-k random variables same distribution (the first k numbers automatically added queue). can use order statistics (see link) calculate probability. example, lets assume numbers randomly selected uniformly {0, 1}, expected value of (i-k)th number (out of numbers) (i-k)/i, , chance of random variable being larger value 1-[(i-k)/i] = k/i.

thus, expected number of insertions is:

and expected running time can expressed as:

(k time generate queue first k elements, n-k comparisons, , expected number of insertions described above, each takes average log(k)/2 time)

note when n large comparing k, expression lot closer n rather nlogk. intuitive, in case of question, after 10000 iterations (which small comparing billion), chance of number inserted queue small.