Amazon Interview Question Software Engineer / Developers
0of 0 votesgiven a million integers find the largest k elements
Country: United States
I think this the best solution except possibly the case where you are given some additional information, say, all the integers can be either 1, 2, or 3.
Nope, there are faster solutions. Look up the rank algorithm. There's an algo that runs in O(n) and can be done in-place on an array.
Well, I guess the heap solution can also be done in-place if you're clever. But the rank algorithm avoids the logarithmic factor.
The average execution time is not O(n log k), but rather O(k log k), since not every number has to be put into the heap.
@tsichevski: No, afraid that's not right. For all you know, every number *could* be put into the heap, so the worst case is, in fact, O(n log k). Consider the situation where the elements are supplied to you in monotonely increasing order.
Note the word *average* in my comment. As for the worst case, yes, it should be O(n log k)
@aqs : turns out it's not as easy to find by the name "RANK algorithm" as I thought. "Quickselect" is a sure way to find it, and is the algorithm's proper name.
/**
* Time complexity: O(n * k ^ 2)
* Space complexity: O(k);
* @param a the array
* @param k the k largest elements
* @return
*/
public static int[] getKBiggest(int[] a, int k) {
if (a == null || a.length == 0) {
return null;
}
int[] kBig = new int[k];
kBig[0] = Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < kBig.length; j++) {
if (a[i] > kBig[j]) {
for (int l = kBig.length - 1; l > j; l--) {
kBig[l] = kBig[l - 1];
}
kBig[j] = a[i];
break;
}
}
}
return kBig;
}
The above code will do ok when k si much smaller than n: i.e. k=7, n = 1000K. When k si somewhat closer to n than building a MAX-HEAP and extracting those k largest elements should provide the optimal answer
The above code will do ok when k si much smaller than n: i.e. k=7, n = 1000K. When k si somewhat closer to n than building a MAX-HEAP and extracting those k largest elements should provide the optimal answer
Sort it first, cost nlogn ,then use any searching method to find the kth largest element and count on base on the index to find the rest,
it will cost 1 more loop
total cost is nlogn,
I think its thats what vijay is doing, but he is he is also eliminating smaller elements at the same time. for smaller k , nlog(k) can be much lesser than nlog(n)
- vijay January 14, 20120. if k <= million, return everything 1. create a min heap 2. insert first k elements to the heap 3. for each of the remaining integer x in the input if x is greater than top of the heap delete the top element add x to the heap 4. remove and return all the elements in the heap O(nlogk) time (n is the input size, in this case a million), needs extra O(k) storage