Amazon Interview Question Software Engineer / Developers
even in an unsorted array kth element can be found in O(n),then travel the array to find all numbers greater than that
How do you break ties ? Say k=4 from the array 123333445, SELECT returns 3, obviously cannot just pick all the 3s.
So far heap seems best with O(klgn).
David - its easy to fix that. After finding the (n-k+1)th element(since we are looking for k largest elements), make a pass and print all numbers GREATER than the this element. If we printed less than k numbers then we ran into your case. So we make another pass and print the remaining elments which are same as the n-k+1 th element.
O(k logn)?
Isn't this O(n) in the worst case? You have to look at each element at least once... don't you?
There are selection algorithms to select the kth largest in O(n) time. Use that, then do a pass of the array and just pick elements >= the kth largest you just found.
O(n), not matter what your k is.
To use a max-heap:
First heapify the array: O(n) time.
Then get the max k times : O(k log n).
So depending on k, it could potentially be worse than the selection of kth largest, O(n) time solution.
For small k, max-heap is probably better, but probably depends on the implementation etc.
i dont understand why people are unnecessarily writing craps even the first couple of responses nails the problem. Have a max heap of size K, and traverse the full list each time putting the element in the heap and maintaining the max-heap property, by the end you've all the k-largest elements in the heap and we're done. Time: O(n) as we have to traverse the whole list to fill the maxheap.
the complexity should be O(n), please check introduction to algorithm, finding the Kth number in the array, its complexity is O(n), but anything on the left of that number is also larger than K.
- anonymous September 25, 2008