Amazon Interview Question for SDE-2s


Country: United States




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

C++ Version:

O(n2) version:

void ReplaceNextLargest ( int * Arr, int N ) {
    for ( int i = 0; i < N; i++ ) {
        for ( int j = i + 1; j < N; j++ ) {
            if ( Arr[j] > Arr[i] ) {
                Arr[i] = Arr[j] ;
                break;
            }
        }
    }
}

O(n) Version:

> Take stack and Initially push the Index 0 on to the stack.
> Traverse All Elements of the Array from left to right.
>> If the stack is Empty push the element in the stack.
>> If the stack is Non-Empty AND Current-Element > Stack-Top-Index-Element, then replace the Stack-Top-Index element in Array with Current-Element and Pop the Stack. Else Push the Index on to the Stack.

void ReplaceNextLargest ( int * Arr, int N ) {
    stack<int> stk;
    stk.push(0);

    for( int idx = 1; idx < N; idx++ ) {
        while( !stk.empty() && (Arr[idx] > Arr[stk.top()]) ) {
            Arr[stk.top()] = Arr[idx];
            stk.pop();
        }
        stk.push(idx);
    }
}

- R@M3$H.N March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No explicit Stack needed, I build array walking backwards, as a max of current input index and prev output index

- CT March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@CT - Can you please elaborate your answer.

- R@M3$H.N March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain how you arrived at the time complexity?....the way i see it both algorithms are using two loops..and both have comparisons..

- heman March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The elements in the stack will always be stored in descending order.
So, each element will be pushed once and popped once. Hence O(n).
Thus for all the cases the time complexity is O(n) or more generally O(2n) which gives us O(n) only.

- NDJP123 March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

while( !stk.empty() && (Arr[idx] > Arr[stk.top()]) )

is this line correct?
i am talking about the check -- Arr[idx] > Arr[stk.top()])

Arr[stk.top()] may lead to index out of bound error?

- ST March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, my bad

- ST March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ramesh N: Good solutions to a subtly tricky problem.

- maitreyak March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you run your algorithm with i/p in o/p's example, you will run into problem when processing 1 and 2. You will pop out 1 after assigning 2 to 1. Then when you meet 10, u will only assign 10 to item 8 6 and 5.

- Jerry Fan March 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 for Stack usage.

- Tapas April 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is asking to replace each element with the next element in the list which is larger than it.

Which is not at all clear from the phrase "Next Largest Element".

stack = Stack.new
stack.push(ary[len(ary)-1])
for i in range(len(ary)-2,0,-1):
	while(ary[i]>stack.peek()):
		stack.pop()
	if(stack.peek()>ary[i]):
		ary[i]=stack.peek()
		stack.push(ary[i])

- zack.kenyon March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

replace each element with its Next Largest Element == replace each element with the next element in the list which is larger than it

- Anonymous March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@zack.kenyon --- The i/p and o/p clearly showed what is required. Anyway,I have updated the question for clarity.

- R@M3$H.N March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ramesh I agree that the input and output you listed convey what you mean. just that, there is a formal statement of the question which is precise and accurate, and not at all complex.

the next largest element in english would most commonly mean the least element in the array with is larger than it, whereas the "next, largER element" would probably be closer.

- zack.kenyon March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@zack.kenyon --- I just gave tech description of the question. I didn't think of the Literal meaning of the same :-)

- R@M3$H.N March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@zack.kenyon --- this is Hieghts...

- Anonymous March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ramesh I understood the question only after I read zach's comment.

- Anonymous March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

main()
{
int a[10] = {2,12,8,6,5,1,2,10,3,2},i,j;

for(i = 0;i<9;i++)
{
for(j = i+1;j<10;j++)
{
if(a[i] < a[j])
{
a[i] = a[j];
break;
}
}
}

for(i = 0;i<=9;i++)
{
printf("%d ",a[i]);
}
}

- mahesh March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ReplaceNextGreaterElement {

	public static void main(String[] args) {
		int a[] = { 2, 12, 8, 6, 5, 1, 2, 10, 3, 2 };
		greaterElement(a);
		display(a);
	}
	
	public static void display(int a[])
	{
		for(int a1:a)
		{
			System.out.print(a1+",");
		}
	}

	public static void greaterElement(int a[]) {
		int len = a.length;
		for (int i = 0; i < len-1; i++) {
			for (int j = 0; j < len-1; j++) {

				if(a[j]<a[j+1])
				{
					a[j]=a[j+1];
				}
			}
		}
	}
}

- Ravi Kumar March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Output: -
12,12,10,10,10,10,10,10,3,2,

- Ravi Kumar March 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is a solution in C#. The number of arrays used can be minimized further. The time complexity is o(n)

static void Main(string[] args)
        {
          

            int[] retArray = GetChangedArray(intArray); // intArray is the integer array and retArray is the final array
            
        }

        public static int[] GetChangedArray(int[] origArr)
        {
            if (origArr == null || origArr.Length == 0) return origArr;
            int len = origArr.Length;
            int max = origArr[len - 1];
            int[] MaxArr = new int[len];

            for (int i = len - 1; i >= 0; i--)
            {
                MaxArr[i] = GetMax(max, origArr[i]);
                max = MaxArr[i];
            }

            for (int i = 0; i < len; i++)
            {
                origArr[i] = GetMax(origArr[i], MaxArr[i]);
            }

            return origArr;
        }

        private static int GetMax(int x, int y)
        {
            return x > y ? x : y;
        }

- Am March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be solved in O(n) with two pointers.
1) slow and fast pointer initially points to zero'th element.
2) start moving fast pointer forward until its in increasing order.
3) on fast pointer reach a element that is less than prev.
4) start copying fast[i-1] to slow[j] until j reaches i-1.

- sathya March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void doChange(int[] array) {
		for(int i=0; i<array.length; i++){
			int big=array[i];
			for(int right=i+1;right<array.length;right++){
				if(big < array[right]){
					big=array[right];
					break;
				}else continue;				
			}
			if(array[i] !=big)
				array[i]=big;
		}

}

- Sumit March 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Work backwards. Last element of array will always be max element in that position. Previous element should be compared with last element. If it is smaller then copy last element to previous element position. Similarly continue till the first element in array.

public class ReplaceLargestRHS {

	private static void replaceLargestRHS(int a[])
	{
		int output[] = new int[a.length];
		output[a.length -1] = a[a.length -1] ;
		for(int i = a.length -2; i >=0; --i)
		{
			if(a[i] < output[i+1])
			{
				output[i] = output[i+1];
			}
			else
				output[i] = a[i];
		}
		
		System.out.println("Input :" + Arrays.toString(a));
		System.out.println("Output:" + Arrays.toString(output));
	}
	
	public static void main(String[] args) {
		
		replaceLargestRHS(new int[]{2,12,8,6,5,1,2,10,3,2});
	}
}

- Anonymous April 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

With Ruby

def replace_next_largest(arr)
  arr.map.with_index do |v,i|
    next_index = i+1
    arr.slice(next_index, arr.length).find {|x| x > v} || v
  end
end

- Anonymous April 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby version

def replace_next_largest(arr)
  arr.map.with_index do |v,i|
    next_index = i+1
    arr.slice(next_index, arr.length).find {|x| x > v} || v
  end
end

- Hrishikesh April 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(n)

void replaceNextLargest(int *arr, size_t size)
{
	int max = arr[size - 1];

	for (int i = size - 2; i >= 0; --i)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		else
		{
			arr[i] = max;
		}
	}
}

- LiMingjie0719 March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Code is wrong. It outputs:
{12, 12, 10, 10, 10, 10, 10, 10, 3, 2}

It is Next Larger Element not the Largest...
O/p: {12,12,10,10,10,2,10,10,3,2}

- R@M3$H.N January 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Just go from right to left keeping the max value found so far. Replace every element with such value (which can be the current element). O(N) time and O(1) space.

- carlos March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why is it incorrect? I think it makes sense to go from right to left. But I think it is not to keep max. Instead, we record the value of current index from right to left in a variable which initially is minus infinity. During each step backward, we compare current value V.S value saved in the variable. If V<current value, then we replace current value. Continue stepping backward.

- Jerry Fan March 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int A[] = {2,12,8,6,5,1,2,10,3,2};
    const int N = sizeof(A) / sizeof(A[0]);

    int m = A[N - 1];

    for (int i = N - 2; i >= 0; i--) {
        m = max(m, A[i]);   // m = max(A[i], A[i+1], .... A[N-1]
        A[i] = m;
    }

    for_each(A, A + N, [](int n) { cout << n << " "; });
    cout << endl;
}
// output: 12 12 10 10 10 10 10 10 3 2

- Westlake March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Did you read the question.. the output should be {12,12,10,10,10,2,10,10,3,2}

- Royal March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is Next Larger Element not the Largest...
O/p: {12,12,10,10,10,2,10,10,3,2}

- R@M3$H.N March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If it's the next largest, how come the first element becomes 12. When we consider A[0], the largest element from A[0] is 12, and the second largest is 10. If you want the second largest, A[0] should become 10.

The code can be easily adapted to handle the second largest case.

- Westlake March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Westlake - The question is clearly finding the Next Largest Element. I think to be more specific it is Next Immediate Largest Element.
So, for the First Element is 2 and the Next Immediate Largest Element is 12. So, it is 12.

I didn't understand how you came to finding Second Largest?

- NDJP123 March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question is misleading. I think it asks to replace A[i] with the first A[j] with condition i < j and A[i] <A[j]. If no such element exists, no change is needed.

- Westlake March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Westlake --- The i/p and o/p clearly showed what is required. Anyway,I have updated the question for clarity.

- R@M3$H.N March 03, 2014 | Flag


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