Google

  www.google.com
Work in HR? Unlock Free Profile

Google Software Engineer Interview Question (student candidate)

I interviewed in Los Angeles, CA and was asked:
"Find max k elements among mostly sorted list."
Add Tags [?]
Answer

Part of a Software Engineer Interview Review - one of 3,100 Google Interview Reviews

Answers & Comments

2
of 10
votes

Pretty easy question.

- Interview Candidate on Jul 21, 2013
2
of 7
votes

Bubble sort k times.

- Skyler on Jul 23, 2013
0
of 1
vote

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
of 4
votes

Insertion Sort

- Nate on Oct 8, 2013
3
of 3
votes

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
of 2
votes

@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

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

Tags are like keywords that help categorize interview questions that have something in common.