ruk
BAN USER
Comments (5)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Using a lazy-enough merge sort it's possible to find Kth largest element in O(n+K*log n) time. The idea is to build the binary tree of merge operations from the elements in O(n) time and getting the next element from the tree in O(log n) time. There is an algorithm how to do it in the lazy functional languages. But, probably, it will require some effort to implement it in Java.
- ruk April 09, 2011Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
From my understanding all quicksort based solutions to find the median have expected (average) O(n) time complexity and the worst O(n2) time depending how good the pivot will be chosen. There is the median of medians algorithm with best/worst performance O(n) which is always better than O(n log n).
- ruk April 09, 2011