Select K largest number from N

Question

Utilisateur anonyme · 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).

Utilisateur anonyme · Answer

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

Utilisateur anonyme · 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.

Utilisateur anonyme · 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

Question d’entretien chez Google

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois