Select K largest number from N

Question

Anonimo · 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).

Anonimo · Answer

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

Anonimo · 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.

Anonimo · 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

Domanda di colloquio di Google

Risposte di colloquio

Aziende seguite

Ricerche di lavoro