## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Written Test

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

Looks like below is not correct
B[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

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

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)

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

deletion of element A[K+i-1] is O(k) operation. So, time complexity of solution is O(nk).

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

this algorithm is so cool.........I did it for another problem today..

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

you can add an index point to a[k+i-1], then the deletion is O(1)

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

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}

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

I think question is that k is some given number and length of B is N-k+1,
So can be done in O(n) Time Complexity
Traverse the array from i=N-k+1 to i=0{
keep one min variable if(a[i]<min) min=a[i]
b[i]=min;
}

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

Is it not a sliding window problem ?

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

That's definitely a sliding window problem and it's solved in O(n) time and with O(k) additional space.

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

yes it should be i+k -1.

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

segment tree concept will be used

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

In segment tree the extra space order will not be maintained within O(k)

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

``segment tree concept will be used``

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

segment tree concept will be used

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

It won't work - b[1] may be between a[0] and a[k-1], but not b[0].

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

It won't work - b[1] may be between a[0] and a[k-1], but not b[0].

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

It won't work - b[1] may be between a[0] and a[k-1], but not b[0].

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

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)

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

how will you find out a[k+i-1] in the min heap.you have to linearly search for the element for that.so it will be O(Nk).

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

we can use selection to find the min. number and complexy will be o(n) and space used will be o(1).....

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

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);
}``````

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

It seems you missed the full code

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

We can use binary search for it.
Step-1: Add 1st k elements to bst tree.
Step-2: Print the min element from bst tree
Step-3: Print min element and Remove the ith element
Step-4: Add the i+k+1 th element..i++
Step-5: Repeat Step-2,3,4 until no more elements

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

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()]);
}``````

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

Bullsh**

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

Bullsh**

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.