Amazon Interview Question for Software Trainees


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

- Ashish July 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Downvoter Care to explain the reason

- Ashish July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ashish July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- pirate July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ashish July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- KP23 July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ashish July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Right, my bad.

- KP23 July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Saket August 01, 2013 | Flag
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...

- Saket August 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ashish Elegant solution!!

- Nomad August 29, 2013 | Flag
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....
Please comment on it.

#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;
}

- Rahul September 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good Solution......
Thanks
:)

- rajmalraj567 September 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- KurinchiMalar February 16, 2016 | Flag
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/

- vgeek July 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 3139a1m July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- pirate July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vgeek July 31, 2013 | Flag
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);
}

- vgeek July 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- pirate July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- vgeek August 01, 2013 | Flag
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?

- Kallu July 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vgeek July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- pirate July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ashish July 31, 2013 | Flag
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];
                }
            }
        }

- Anonymous August 03, 2013 | Flag Reply
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;
	}

- Jialiang Bao August 03, 2013 | Flag Reply
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]);
}
}

- Anonymous August 03, 2013 | Flag Reply
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)

- Anonymous August 03, 2013 | Flag Reply
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;
}

- Anonymous September 06, 2013 | Flag Reply
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;
        }

- Rammy February 22, 2015 | Flag Reply
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;
        }

- Rammy February 22, 2015 | Flag Reply
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;
}

- Rammy February 22, 2015 | Flag Reply
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

- pirate July 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 3139a1m July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@3139a1m good catch!

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

- pirate July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

geeksforgeeks.org/next-greater-element/

This one's related

- Dsa July 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Can you explain the question with a example?

- Ajay July 31, 2013 | Flag Reply
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.

- Anonymous July 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kallu July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ashish July 31, 2013 | Flag
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

- coder July 31, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More