Select K largest number from N

Question

Anónimo · 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).

Anónimo · Answer

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

Anónimo · 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.

Anónimo · 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

Pregunta de entrevista de Google

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo