Interview Question

Software Engineer Interview(Student Candidate) Los Angeles, CA

Find max k elements among mostly sorted list.

Answer

Interview Answer

6 Answers

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
4

Insertion Sort

Nate on Oct 8, 2013
3

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
2

@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