Select K largest number from N

Question

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

Sigiloso · Answer

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

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

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

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas