Interview Question

Software Engineer Interview(Student Candidate) Los Angeles, CA

Find max k elements among mostly sorted list.


Interview Answer

6 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

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up