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.


Interview Answer

7 Answers


Pretty easy question.

Interview Candidate on Jul 21, 2013

Bubble sort k times.

Skyler on Jul 23, 2013

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

Nina on Sep 14, 2013

Insertion Sort

Nate on Oct 8, 2013

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

@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

@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

Add Answers or Comments

To comment on this, Sign In or Sign Up.