Google Interview Question: Find max k elements among mos... | Glassdoor

## Interview Question

Software Engineer Interview(Student Candidate) Los Angeles, CA

# Find max k elements among mostly sorted list.

2

Pretty easy question.

Interview Candidate on Jul 21, 2013
2

Bubble sort k times.

Skyler on Jul 23, 2013
0

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

Nina on Sep 14, 2013
5

Insertion Sort

Nate on Oct 8, 2013
4

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

Santi on Dec 10, 2013
3

@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.

Dave on Feb 3, 2014
0

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

Anonymous on Apr 15, 2015