## Amazon Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
4
of 4 vote

``````0. 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``````

Comment hidden because of low score. Click to expand.
0

How do you think, Is there faster solution?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Well, I guess the heap solution can also be done in-place if you're clever. But the rank algorithm avoids the logarithmic factor.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

Note the word *average* in my comment. As for the worst case, yes, it should be O(n log k)

Comment hidden because of low score. Click to expand.
0

for average case its O((n/2)log(k))

Comment hidden because of low score. Click to expand.
0

@eugene which rank algorithm are you talking about? any links that u can give?

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

If we assume that the integers stored are in the form of a BST. The we can do inorder traversal with a twist.
We can do
node->right;
node->data;
node->left;

We can get the largest k numbers keeping a static counter while traversing the tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
* 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;
}

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

During sorting of Heap it takes nlogn time 2 sort n elemnts. to sort k elements it will take klogn time. This kth sort will give kth largest value. so klogn is much faster than nlogk as n is much greater than k generally.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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,

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

Yep. There's also an algo that avoids the logarithmic factor entirely and just computes the answer in O(n). Look up the rank algorithm

Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.