## Amazon Interview Question for Software Trainees

• 0

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
5
of 9 vote

Using a stack we can push the element's index on the stack till the next element is smaller. Once we get a larger number we can pop till the number is larger. The poped index can be used to modify the array.

stack<int> st;
st.push(0);
for(i=1;i<n;i++)
{
while(!st.empty()&&a[i]>a[st.top()])
{
a[st.top()] = a[i];
st.pop();
}
st.push(i);
}
while(!st.empty())
{
a[st.top()] = -1;
st.pop();
}

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

@Downvoter Care to explain the reason

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

The solution has the time complexity of O(n).

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

@Ashish: good solution

Its hard to understand but great solution time complexity is O(n)
Given input ascending or descending in two cases it is O(n)

+1 d

Note: In stack adding only indexes and doing in-place good

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

@Venkatesh Not only for ascending or descending cases, but for all the cases the time complexity is O(n) or more generally O(2n) which gives us O(n) only.

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

Ashish, you are replacing the last element which has not yet got a greater number. Once it gets a greater number, its pop-ed out and never processed again, which will fail in the below case:
Input: {3, 4, 1, 5, 2} gives {4, 5, 5, -1, -1} as output as per your solution.
Actual output should be: {4, 5, 2, -1, -1}.

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

@KP23 The output for 3,4,1,5,2 should be 4,5,5,-1,-1 . Question asks for the nearest greater on the right. For 1 the nearest greater is 5 and not 2. So the output given by my code is correct.

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

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

The stack based solution does not work for this input
3 1 2 7 6 10 9 15 0 1 2 8

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

For this input
3 1 2 7 6 10 9 15 0 1 2 8, the output shud be
7 2 7 10 15 15 15 1 8 8
I don't see the stack based solution give a correct answer to this...

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

do we really need a stack here?

why can't we save value and index of an element and when a larger element is found update every element from saved index to current index..

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

@Ashish Elegant solution!!

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

There is no need to use any extra stack or other DS..
simple O(n) solution without extra space....

#include<stdio.h>

#define SIZE 10

int main(void)
{
int arr[SIZE];
int i, j;
for(i=0; i<SIZE; i++)
{
printf("Enter the Element for Array[%d] :  ", i);
scanf("%d", &arr[i]);
}
printf("\n Original Array :  ");
for(i=0; i<SIZE; i++)
printf("    %d", arr[i]);

j=0;
for(i=0; i<SIZE-1; i++)
{
if(i == j)
for(j=i+1; j<SIZE && arr[i]>=arr[j]; j++);
if(j > i && j < SIZE)   //Extra condition has been added to see whether have to replace or not.
arr[i] = arr[j];
}

printf("\n Modified Array :  ");
for(i=0; i<SIZE; i++)
printf("    %d", arr[i]);
printf("\n\n");

return 0;
}

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

Good Solution......
Thanks
:)

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

This solution takes O(n*n) complexity. Not O(n)

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

An elegant solution in O(n) is given here
geeksforgeeks.org/replace-every-element-with-the-greatest-on-right-side/

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

this solution replaces the current element with the greatest number which is present on the right side not the nearest greater element

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

Yes question asking near greater element not greatest on right.

Same solution with minor change:
Replace every element with the maximum element only if it is greater than current element otherwise -1.

input {16, 17, 4, 3, 5, 2},
output {17, -1, 5, 5, -1 -1}

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

You can see my solution below its updated with time complexity of O(n)

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

Here is a O(n) solution:
a. Keep the first element in temp and its index stored in k.
b. For every element see the difference with the next element
c. When the difference is greater than 0 then update the k variable and also the j variable.
d. Note for finding the difference of the element there are two pointers in the array that is j and k k runs the loop and j finds the difference.
e. If the element does not have a large element then it is updated to -1.

#include <stdio.h>
#include <conio.h>

void findNextGreater(int arr[],int n)
{
int j,temp,k=0;
temp=arr[k];
j=1;
while(k!=n-1)
{
if(arr[j]-temp<0&&j==n-1)
{
arr[k]=-1;
k=k+1;
temp=arr[k];
j=k;
}
if(arr[j]-temp>0)
{
arr[k]=arr[j];
k=k+1;
j=k;
temp=arr[k];

}
else
{
j=j+1;
}
}
arr[n-1]=-1;
for(j=0;j<n;j++)
printf(" %d ",arr[j]);
}
int main()
{
int arr[]={11,13,21,32,10};
int n=sizeof(arr)/sizeof(arr[0]);
findNextGreater(arr,n);
}

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

@vgeek:

Good try I appreciate, program gives correct solution but problem in time complexity in worst case.

If given input is in descending and last value is greatest then this time complexity is O(n^2) where everytime your j variable goes end.

ex: 10,9,8,7,6,5,4,3,2,1,11

@Ashish: solution always gives O(N)

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

@Venkatesh
Yes I was just trying to do without stack. But it seems that in some cases it will give time complexity of O(n2) as pointed out by you. Yes the solution with stack is correct.
Thanks anyways

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

@Ashish, If I understand your solution correctly, it replaces element with next greater element on right side. But problem is is element should be replaced with NEAREST GREATER element.

Correct me if I am wrong.

Input: 22 5 4 20 13 17 12 3
Output: 22 7 7 20 17 17 12 3

I also didn't understand why people are replacing with -1. If we don't have greater element on right side, I believe we should keep that element as it is. am I right?

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

Yes for that you can just ignore the -1 step that is if you use a stack or if you are doing an array traversal so you can skip that step where in an array if we reach the last element then it ignore the -1 step and also in stack you can pop the elements if they are left while storing the numbers

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

@kallu: I agree with -1
but what is the difference between next greater and nearest greater on right.
your Input: 22 5 4 20 13 17 12 3
output : 22 20 20 20 17 17 12 3

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

@kallu If you dont want -1 then dont use the last while loop which marks all the remaining indexes of stack with -1. The output you mentioned is incorrect. The output mentioned by Venkatesh is correct.

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

Using stack:

public static void Replace(int[] arr)
{
var s = new Stack<int>();
int i = 0;
while (i < arr.Length )
{
if (s.Count == 0 || arr[i] <= arr[s.Peek()])
{
s.Push(i);
i++;
}
else
{
arr[s.Pop()] = arr[i];
}
}
}

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

public static int[] getReplacement(int[] data){
int[] index = new int[data.length];
int[] newData = new int[data.length];
index[index.length - 1] = -1;
for(int i = data.length - 1; i >= 1; i--){
int j = i;
while(true){
if(data[i - 1] < data[j]){
index[i - 1] = j;
break;
}else{
j = index[j];
if(j == -1){
index[i - 1] = -1;
break;
}
}
}
}

for(int i = 0; i < newData.length; i++)
newData[i] = index[i] == -1 ? data[i] : data[index[i]];

return newData;
}

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

void replaceWithNearestGreatest(vector<int>& a)
{
stack<int> S;
for (int i=0; i < n; i++)
{
if (!s.empty() && a[i] > s.top()) s.pop();
a[i] = s.empty() ? -1 : s.top();
s.push(a[i]);
}
}

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

if you do this, try replace next greatest (in terms of magnitude)

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

val=a[n-1]; //I am assuming the left-most element is not replaced with any value. Alternatively, we can replace with -1
for(i=n-2;i>=0;i--)
{
tmp=a[i];
a[i]=val;
if(tmp>val)
val=tmp;
}

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

public int[] ReplaceWithNextGreatestElements(int[] array)
{
int maxElement = array[array.Length - 1];
array[array.Length - 1] = -1;

for (int i = array.Length - 2; i >= 0; i--)
{
int temp = array[i];
array[i] = maxElement;
if (maxElement < temp)
{
maxElement = temp;
}
}
return array;
}

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

public int[] ReplaceWithNextGreatestElements(int[] array)
{
int maxElement = array[array.Length - 1];
array[array.Length - 1] = -1;

for (int i = array.Length - 2; i >= 0; i--)
{
int temp = array[i];
array[i] = maxElement;
if (maxElement < temp)
{
maxElement = temp;
}
}
return array;
}

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

public int[] ReplaceWithNextGreatestElements(int[] array)
{
int maxElement = array[array.Length - 1];
array[array.Length - 1] = -1;

for (int i = array.Length - 2; i >= 0; i--)
{
int temp = array[i];
array[i] = maxElement;
if (maxElement < temp)
{
maxElement = temp;
}
}
return array;
}

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

Replace all elements using one traversal of the array.

The idea is to start from the rightmost element, move to the left side one by one, and keep track of the maximum element. Replace every element with the maximum element only if it is greater than current element otherwise -1.

input {16, 17, 4, 3, 5, 2},
output {17, -1, 5, 5, -1 -1}

void nearGreater(int arr[], int size)
{
int max_from_right =  arr[size-1];
int current;
arr[size-1] = -1;
for(int i = size-2; i >= 0; i--)
{
current = arr[i];
if(max_from_right > current)
arr[i] = max_from_right;
else {
arr[i] = -1;
max_from_right = current;
}
}

O(n)

modified http://www.geeksforgeeks.org/replace-every-element-with-the-greatest-on-right-side

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

for input {14,11,3,13,15,20}
actual output = {15,13,13,15,20,-1}

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

@3139a1m good catch!

My solution won't work in this case. Let me try other with O(n)

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

geeksforgeeks.org/next-greater-element/

This one's related

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

Can you explain the question with a example?

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

It cannot be done in O(n).
In below case
13,12,11,10,9,8,7
for above example array will remain unchanged after replacing near greater element on the right. But for each element we have to check all the elements to its right. Best solution will be of nlogn complexity.

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

@Anonymous, the solution may not be done in O(n), but for your case/example it can be done in O(n), if you maintain the right largest element. Start from right side and check whether current element is greater than largest element traversed so far. If it is greater than that then no need to traverse the right side list again. Perhaps, this should be the one if the optimization step in solution.

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

check my solution using stack. It doesn't require to keep track of largest so far which may be erroneous. It is O(n).

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

public static void replaceWithGreaterNumber(int[] A)
{
int len = A.length;
int grt = -1; // assign with default value -1

for(int i = len-1; i >= 0; i--)
{
int tmp = A[i];
if (grt > tmp) // ith index value smaller than previous greater value, then assign A[i] with grt
{
A[i] = grt;
}
else
{
A[i] = -1; // else assign A[i] with -1
if (tmp > grt)
{
grt = tmp; // updating grt (greater value) with A[i] that is with tmp
}
}
}

for(int i = 0;i < len; i++)
System.out.print(A[i] + " ");

}

Time complexity : O(n)
Space complexity : O(1)
Pls point out if there is any bug

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.