Find max k elements among mostly sorted list.

Question

Santi · Accepted Answer

Why would you sort the whole thing when you only need the top k? Any sort algorithm will take you at least nLog(n). But maybe, and probably, n>>k. 
You go over the original list O(n) and insert in a Heap, keeping only k elements.
It's gonna be O(n Log(k)).

Nate · Answer

Insertion Sort

Dave · Answer

@santi, should use a min-heap. fill it up with first k elements, then if a new element is greater than heap min, pop the top and push new val.  heap will have top k elements.  this is o(n), since log(k) reduces to constant time.

Utilisateur anonyme · Answer

Pretty easy question.

Skyler · Answer

Bubble sort k times.

Anonymous · Answer

@Dave can you explain why you want to use a min-heap instead of a max-heap?  I don't get this part.

Utilisateur anonyme · Answer

Max-heap will have largest number at top - min heap has smallest number at top, so when you insert new number the smallest gets popped out, leaving all k max in heap

Nina · Answer

Are you kidding? "Bubble sort k times" is going to be kn^2. Too expensive.
Use a merge sort.

Google

Question d’entretien chez Google

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois