Select K largest number from N

Question

Anonymous · Accepted Answer

The answer is something called quickselect.  It's similar to quicksort, only that once an array is partitioned, you simply ignore the portion that does not contain the Kth position.  You aim for the pivot to fall on the Kth position.  Interestingly enough, the complexity for an average case is O(n).

Anonymous · Answer

To use a heap other than list, will improve the performance

Anonymous · Answer

As mentioned previously, find the Kth largest element in linear time (using median of medians) and then go over the array to find those that are larger than it, also in linear time.

Cedric · Answer

I would sort it using quicksort then return the n-5 element.

Anonymous · Answer

Keep a list of K elements. Go through N, and adjust the list whenever you find a new element that is larger than any element in the K list. Time complexity is O(K*N)

Google

Google Interview Question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?