Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
the algo could go on like this....
1.scan the array in reverse order and create a min heap of k elements.
2.the element B[i] would be the element at the root of min heap.
3. now delete the element at A[K+i -1] and insert the element A[i-1]
4.reheapify the heap.
TC-O(nlogk)
deletion of element A[K+i-1] is O(k) operation. So, time complexity of solution is O(nk).
How this algo will work for following input :
arr[] = {9,8,7};
N=3;
k=2;
So, as per step (i),starting from last K elements we will maintain MIN heap.
So, at first, heap will be {7,8} with 7 sitting at top. << b[1] = 7
But as per step (iii), 8 will be replaced by 9
So next time b[0] will be 7 as 7<9, and resulted output will be {7,7} instead of {8,7}
the algo could go on like this....
1.scan the array in reverse order and create a min heap of k elements.
2.the element B[i] would be the element at the root of min heap.
3. now delete the element at A[K+i -1] and insert the element A[i-1]
4.reheapify the heap.
TC-O(nlogk)
Solution: O(n) time and excluding the result space + O(1) space if there are no duplicates (if there are duplicates we can move them to the end of the array and use extra HashMap to count the duplicates)
Here is the java code for nonDuplicate version (can be easyly modified for duplicates) :
public int[] getFirstElements(int[] arr, int k) {
int[] result = new int[k];
int currK = 0;
for (int i = 0; i < arr.length && currK < k; i++)
if (arr[i] != 0)
result[currk++] = arr[i];
return result
}
//O(n) time
private void sortArr(int[] arr) {
for (int i = 0; i < arr.length; i++)
while (arr[i] != i || arr[i] != 0)
swap(arr, arr[i], i);
}
Using queue.
int arr[1000001];
void printKMax(int n, int k) {
deque<int> Qi(k);
int i;
for (i = 0; i < k; ++i) {
while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back(); // Remove from rear
Qi.push_back(i);
}
for ( ; i < n; ++i) {
printf ("%d ", arr[Qi.front()]);
while ( (!Qi.empty()) && Qi.front() <= i - k)
Qi.pop_front(); // Remove from front of queue
while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back();
Qi.push_back(i);
}
printf ("%d", arr[Qi.front()]);
}
Looks like below is not correct
- Anonymous May 13, 2012B[i] = min(A[i], A[i+1], ......., A[i-K+1]), where K will be given.
here A[i-K+1] should be A[i+k-1]
if i=0, and k=4 then i-K+1 will be negative, which is not correct