Facebook Interview Question Software Engineer / Developers
IS it possible to find even in linear time.
The best I can think of maintaining a min heap of size K, where K= log(n) or sqrt(n)
Even in this case complexity is O(n*log(K))
You can always use median-of-median approach to get K-th smallest (or largest) in O(n) time. The same technique also gives worst case O(n logn) complexity for deterministic heap sort.
Also i think you would like to maintain a MAX-head of k smallest numbers rather than max heap. For MAX-Heap replacement of a smaller number from current max in K-set is going to be O(logk), in case of min heap it will be O(n).
lol is correct. You can use quickselect (which is O(n)) to find the sqrt(n)^th or the log(n)^th element and do a partition around it in O(n) time. Now, outputting the K largest elements in sorted order is a different question, but we can do it in O(n+K*log(K)) time by sorting those elements after partitioning the array as above. As long as K=o(N/log(n)), this is linear time as well.
This is possible only when...
1. Array is sorted.
We can find out the intervals like top(sqrt(26)) and top(sqrt(36)) is 6 and so on.
keep jumping in the array 2 elements at a time or more according to your assumption... compare with apex values of interval...
I think "less than linear time" is not correct term in this case.
- Anonymous May 27, 2011I think they mean that such a raising function like log(x) or sqt(n) doesn't require to make calculations for each element in the array. You should simply find the largest element in the array and only then calculate the function.