## Amazon Interview Question for Software Engineer / Developers

• 0

Country: United States

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

Push the first element of array in a stack.
take rest of the elements one by one and follow following steps in loop.
a) Take second element of array as CURRENT element(i.e array)
b)Compare it with top of the stack.
c) If CURRENT element is greater
-Keep poping from the stack while the popped element is smaller than CURRENT. and CURRENT element is the next greater element for all such popped elements.
d)else just push the CURRENT element in the stack.
At the end of the loop, pop all the elements left in stack and print -1 as next element for them.

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

void set_next_grt(int a[],int l)
{
for(int i=l-1;i>=0;i--)
{
if(top==NULL)
{
push(a[i]);
a[i]=-1;
}
else
{
while(top!=NULL && top->data<a[i])
pop();
if(top==NULL)
{
push(a[i]);
a[i]=-1;
}
else
{
int k=top->data;
push(a[i]);
a[i]=k;
}
}
}
}

here is the code

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

what is tme complexity of this algorithm?

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

It's O(n) since worst-case scenario is that your are pushing and popping each element once.

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

good idea.Code in c follows as below

``````#include <stdio.h>
signed int count = 0;
struct s_
{
int data;
int index;
}s_t;

void push(int x, int i)
{
if(count == 0) {
++count;
s_t[count].data = x;
s_t[count].index = i;
} else {
count++;
s_t[count].data = x;
s_t[count].index = i;
}
}

int g_top()
{
int x = count;
if(count == 0) {
printf("%s\n", __func__);
return -1;
} else {
return s_t[x--].data;
}
}

struct s_ * pop()
{
if(count >= 1) {
return &s_t[count--];
} else
{
printf("do you know what you are doing?\n");
return NULL;
}
}

int i_empty()
{
return (count == 0)?1:0;
}
int main()
{
int i, x;
struct s_ *in;
int a[] = {4, 5, 9, 10, 1, 2, 3, 4, 7, 8};

push(a, 0);
for(i=1;i<(sizeof(a)/sizeof(a));i++) {
/* compare the element with top of the stack */
printf("top %d\n", g_top());
if(g_top() < a[i]) {
struct s_ *in = pop();
if(in != NULL) {
a[in->index] = a[i];
printf("first\n");
while(x = ((g_top() != -1)?g_top():100) < a[i]){
printf("second\n");
struct s_ *in = pop();
a[in->index] = a[i];
}
push(a[i], i);
}
} else {
push(a[i], i);
}
}
while((in = pop()) != NULL) {
a[in->index] = -1;
}
for(i=0;i<(sizeof(a)/sizeof(a));i++) {
printf("%d\n", a[i]);
}
return 0;
}``````

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

``````def nextGreatestElementArray(array):
c = len(array)*[-1]
b = []
for index, value in enumerate(array):
if len(b) > 0:
top_element = b[-1]
top_element_index = top_element
top_element_value = top_element
while top_element_value < value and len(b) > 0:
c[top_element_index] = value
b.pop()
if len(b) > 0:
top_element = b[-1]
top_element_index = top_element
top_element_value = top_element
else:
break
b.append((index, value))
return c``````

nextGreatestElementArray([4, 5, 2, 25]) = [5, 25, 25, -1]
nextGreatestElementArray([10, 9, 8, 6, 2, 3, 1, 7, 11]) = [11, 11, 11, 7, 3, 7, 7, 11, -1]

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

Push the first element of array in a stack.
take rest of the elements one by one and follow following steps in loop.
a) Take second element of array as CURRENT element(i.e array)
b)Compare it with top of the stack.
c) If CURRENT element is greater
-Keep poping from the stack while the popped element is smaller than CURRENT. and CURRENT element is the next greater element for all such popped elements.
d)else just push the CURRENT element in the stack.
At the end of the loop, pop all the elements left in stack and print -1 as next element for them.

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

@eugene.yarovoi. May be that i misunderstood the question. Can u tell me its correct interpretation?

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

@gyg , Time complexity is O(n).

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

@pritybhudolia: I was thinking the goal was to find, for each element X, the least element Y such that Y > X and Y is to the right of X in the array. In other words, find the element to the right that would the next element in order. "Next greatest element" suggests this kind of interpretation to me. The example works for both our interpretations, unfortunately.

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

void NextGreatestElement(int arr[],int size)
{
if(size==1)
{
printf("%d ----> %d\n",arr,-1);
return;
}
printf("%d ----> %d\n",arr[size-1],-1);
stack<int> mystack;
mystack.push(arr[size-1]);
for(int i=size-2;i>=0;i--)
{
if(!mystack.empty() && arr[i]<mystack.top())
{
printf("%d ----> %d\n",arr[i],mystack.top());
mystack.push(arr[i]);
}
else
{
while(!mystack.empty() && arr[i]>mystack.top())
mystack.pop();
if(!mystack.empty())
printf("%d ----> %d\n",arr[i],mystack.top());
else
printf("%d ----> %d\n",arr[i],-1);
mystack.push(arr[i]);
}
}
while(!mystack.empty())
{
mystack.pop();
}
}

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

findGreatestElementsToTheRight (int a[], int size)
{
int *greatestElements = malloc(size(int)*size));

int currentGreatest = -1;

for (int i = size - 1 ; i >= 0 ; i--)
{
if (a[i] < currentGreatest)
{
greatestElements[i] = currentGreatest;
}
else
{
greatestElements[i] = -1;
currentGreatest = a[i];
}
}

/// result is with greatestElements
}

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

I think this code will give 25 for the given input.
i.e., {4, 5, 2, 25} will return {25, 25, 25, -1} where as it should be {5, 25, 25, -1}

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

``````public class NextGreatestElement {

private static List<Integer> elementList_ = new ArrayList<Integer>(Arrays.asList(4,5,2,1,8,3,25));
private static List<Integer> currentStack_ = new ArrayList<Integer>();

public static void main(String[] args) {
findNextGreatestElement(elementList_);
}

private static void findNextGreatestElement(List<Integer> elements) {

int current=elements.remove(0);

//4,5,2,1,8,3,25
while(elementList_.size()>0) {
int nextGreatestElement=elements.remove(0);
if (nextGreatestElement>current) {
System.out.println(current+" --> "+nextGreatestElement);
if (currentStack_.size()>0) {
current=currentStack_.remove(0);
}
else {
current=nextGreatestElement;
}
}
else {
}
}
System.out.println(current+" --> -1");
}

}``````

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

Not enough Ruby around here. I'm not sure how efficient this is given it backtracks over the result array when it's necessary. But it works. The instructions don't say what to do if there is no next greatest integer (like in the example [4, 45, 2, 25]) so in those cases I print -1.

``````def next_greatest_element(input)
return if input.nil? || input.empty?

length = input.length

tmp = -1
(input.length - 2).downto(0) do |index|
if input[index + 1] > input[index]
else
tmp_index = index + 1
break
end
tmp_index += 1
end
end
end

end``````

``````>> next_greatest_element nil
=> nil
>> next_greatest_element  [4, 45, 2, 25]
=> "45, -1, 25, -1"
>> next_greatest_element [4, 5, 25, 2, 30]
=> "5, 25, 30, 30, -1"
>> next_greatest_element  [4, 5, 2, 25]
=> "5, 25, 25, -1"
>> next_greatest_element [10,  9,  8, 6, 2, 3, 1,  7,  11]
=> "11, 11, 11, 7, 3, 7, 7, 11, -1"``````

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

{{

minHeap = new MinHeap(a);

for(i = 1; i < ar.length; ++i) {
while(!minHeap.isEmpty && a[i] > minHeap.top) {
print minHeap.top -> a[i];
minHeap.pop();
}

minHeap.push(a[i]);
}

print minHeap.top -> -1

}}

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

No need to use a stack. Keep another array which will tell the greatest element corresponding to the elements of the input array.
Use a spl variable to_set: which will point to the position of the array for which greatest element is yet to be found.

Is somewhat O(n), definitely not O(n2).

``````#include<stdio.h>
#include<stdlib.h>

#define N 4

void next_greatest(int a[])
{
int i;

// holds next greatest elements corresponding to a
int b[N];

// holds the first position for which next greatest has to be set
int to_set=0;

// initialize b[N] to -1
for( i=0; i< N; i++ )
b[i] = -1;

// find next greatest
for( i=0; i< N; i++ )
{
while( to_set < i )
{
if( a[i] > a[to_set] )
{
b[to_set] = a[i];
to_set++;
}
else
{ break;
}
}
} // end for

// print elements
for( i=0; i<N; i++ )
{
printf("\n%d  ->  %d", a[i], b[i]);
}

} // end next_greatest

int main()
{
int a[N] = { 4,5,2,25 };

next_greatest(a);

return 0;
}``````

OUTPUT:
4 -> 5
5 -> 25
2 -> 25
25 -> -1

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

Seems there's a lot of confusion around two common, but different problems.
Next GreatER Element is the hard one that wants to use fancy stack algorithms.
Replace each element with the next element in the array greater than this one.
Next GreatEST Element:
Replace each element with the greatest element to it's right.
This one seems straightforward with the most common solutions I found just being O(n) solutions which track a maximum and run from right to left. This is a combination of some great code I found plus my additions to make sure it got what I thought was the right answer:

``````/*
* crazyforcode.com/greater-element-array/
* Plus I added the hash table to fill the output array.
*/
public static void getNextGreaterElement(int[] a) {
/* Basic Stack operation - Push, Pop, isEmpty have been
left to implement for the readers */
int i = 0;
Stack<Integer> s = new Stack<Integer>();
Hashtable<Integer, Integer> hash = new Hashtable<Integer, Integer>();
int element, next;

for (i=0; i < a.length; i++)
{
/* push the first element to stack */
if(i == 0)
{
s.push(a);
continue;
}

next = a[i];

if (!s.isEmpty())
{
/* if stack is not empty, then pop
an element from stack */
element = s.pop();

while (element < next)
{
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
if(s.isEmpty())
break;
element = s.pop();
}

/* If element is greater than next,
then push the element back */
if (element > next)
s.push(element);
}

/* push next to stack so that we can
find next greater for it */
s.push(next);
}

while (!s.isEmpty())
{
element = s.pop();
next = -1;
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
}
for(i = 0; i < a.length; i++) {
a[i] = hash.get(a[i]);
}
}

/*
* url mycppexperiments.blogspot.com/2013/02/reorder-array-elements-with-1next.html
*/
public static void nextGreatestElement(int[] a) {
int max = a[a.length - 1];
a[a.length - 1] = -1;
for(int i = a.length - 2; i >= 0; i--) {
int temp = max;
if (a[i] > max)
max = a[i];
a[i] = temp;
}
}

public static void main(String[] args) {
System.out.println("Next Greater Element");
int[] a = {4, 5, 45, 2, 3, 25};
int[] b = Arrays.copyOf(a, a.length);
getNextGreaterElement(b);
System.out.println("In: " + Arrays.toString(a));
System.out.println("Out: " + Arrays.toString(b));

System.out.println("Next Greatest Element");
int[] c = {2, 3, 4, 45, 5, 2, 3, 25};
b = Arrays.copyOf(c, c.length);
nextGreatestElement(b);
System.out.println("In: " + Arrays.toString(c));
System.out.println("Out: " + Arrays.toString(b));
}``````

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

``````/*
* Works...
* crazyforcode.com/greater-element-array/
* Plus I added the hash table to fill the output array.
*/
public static void getNextGreaterElement(int[] a) {
/* Basic Stack operation - Push, Pop, isEmpty have been
left to implement for the readers */
int i = 0;
Stack<Integer> s = new Stack<Integer>();
Hashtable<Integer, Integer> hash = new Hashtable<Integer, Integer>();
int element, next;

for (i=0; i < a.length; i++)
{
/* push the first element to stack */
if(i == 0)
{
s.push(a);
continue;
}

next = a[i];

if (!s.isEmpty())
{
/* if stack is not empty, then pop
an element from stack */
element = s.pop();

while (element < next)
{
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
if(s.isEmpty())
break;
element = s.pop();
}

/* If element is greater than next,
then push the element back */
if (element > next)
s.push(element);
}

/* push next to stack so that we can
find next greater for it */
s.push(next);
}

while (!s.isEmpty())
{
element = s.pop();
next = -1;
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
}
for(i = 0; i < a.length; i++) {
a[i] = hash.get(a[i]);
}
}

/*
* mycppexperiments.blogspot.com/2013/02/reorder-array-elements-with-1next dot html
*/
public static void nextGreatestElement(int[] a) {
int max = a[a.length - 1];
a[a.length - 1] = -1;
for(int i = a.length - 2; i >= 0; i--) {
int temp = max;
if (a[i] > max)
max = a[i];
a[i] = temp;
}
}

public static void main(String[] args) {
System.out.println("Next Greater Element");
int[] a = {4, 5, 45, 2, 3, 25};
int[] b = Arrays.copyOf(a, a.length);
getNextGreaterElement(b);
System.out.println("In: " + Arrays.toString(a));
System.out.println("Out: " + Arrays.toString(b));

System.out.println("Next Greatest Element");
int[] c = {2, 3, 4, 45, 5, 2, 3, 25};
b = Arrays.copyOf(c, c.length);
nextGreatestElement(b);
System.out.println("In: " + Arrays.toString(c));
System.out.println("Out: " + Arrays.toString(b));
}``````

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

public static void getNextGreaterElement(int[] a) {
/* Basic Stack operation - Push, Pop, isEmpty have been
left to implement for the readers */
int i = 0;
Stack<Integer> s = new Stack<Integer>();
Hashtable<Integer, Integer> hash = new Hashtable<Integer, Integer>();
int element, next;

for (i=0; i < a.length; i++)
{
/* push the first element to stack */
if(i == 0)
{
s.push(a);
continue;
}

next = a[i];

if (!s.isEmpty())
{
/* if stack is not empty, then pop
an element from stack */
element = s.pop();

while (element < next)
{
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
if(s.isEmpty())
break;
element = s.pop();
}

/* If element is greater than next,
then push the element back */
if (element > next)
s.push(element);
}

/* push next to stack so that we can
find next greater for it */
s.push(next);
}

while (!s.isEmpty())
{
element = s.pop();
next = -1;
hash.put(element, next);
System.out.format("\n %d -> %d", element, next);
}
for(i = 0; i < a.length; i++) {
a[i] = hash.get(a[i]);
}
}

public static void nextGreatestElement(int[] a) {
int max = a[a.length - 1];
a[a.length - 1] = -1;
for(int i = a.length - 2; i >= 0; i--) {
int temp = max;
if (a[i] > max)
max = a[i];
a[i] = temp;
}
}

public static void main(String[] args) {
System.out.println("Next Greater Element");
int[] a = {4, 5, 45, 2, 3, 25};
int[] b = Arrays.copyOf(a, a.length);
getNextGreaterElement(b);
System.out.println("In: " + Arrays.toString(a));
System.out.println("Out: " + Arrays.toString(b));

System.out.println("Next Greatest Element");
int[] c = {2, 3, 4, 45, 5, 2, 3, 25};
b = Arrays.copyOf(c, c.length);
nextGreatestElement(b);
System.out.println("In: " + Arrays.toString(c));
System.out.println("Out: " + Arrays.toString(b));
}

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

#include<bits/stdc++.h>
using namespace std;

int main()
{

int arr[]= {4,15,2,9,20,11,13};
int n = sizeof(arr)/sizeof(arr);

int i,next,element;
stack<int>s;
s.push(arr);

for (i=1; i<n; i++)
{
next = arr[i];

if (!s.empty())
{
// if stack is not empty, then pop an element from stack
element = s.top();
s.pop();

/* If the popped element is smaller than next, then
a) print the pair
b) keep popping while elements are smaller and
stack is not empty */
while (element < next)
{
printf("\n %d --> %d", element, next);
if(s.empty())
break;
else
{
element = s.top();
s.pop();
}

}

/* If element is greater than next, then push
the element back */
if (element > next)
//push(&s, element);
s.push(element);
}

/* push next to stack so that we can find
next greater for it */
//push(&s, next);
s.push(next);
}

/* After iterating over the loop, the remaining
elements in stack do not have the next greater
element, so print -1 for them */
while (!s.empty())
{
element = s.top();
s.pop();
next = -1;
printf("\n %d -- %d", element, next);
}

//printNGE(arr, n);

return 0;
}

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

``````#include<bits/stdc++.h>
using namespace std;

int main()
{

int arr[]= {4,15,2,9,20,11,13};
int n = sizeof(arr)/sizeof(arr);

int i,next,element;
stack<int>s;
s.push(arr);

for (i=1; i<n; i++)
{
next = arr[i];

if (!s.empty())
{
// if stack is not empty, then pop an element from stack
element = s.top();
s.pop();

/* If the popped element is smaller than next, then
a) print the pair
b) keep popping while elements are smaller and
stack is not empty */
while (element < next)
{
printf("\n %d --> %d", element, next);
if(s.empty())
break;
else
{
element = s.top();
s.pop();
}

}

/* If element is greater than next, then push
the element back */
if (element > next)
//push(&s, element);
s.push(element);
}

/* push next to stack so that we can find
next greater for it */
//push(&s, next);
s.push(next);
}

/* After iterating over the loop, the remaining
elements in stack do not have the next greater
element, so print -1 for them */
while (!s.empty())
{
element = s.top();
s.pop();
next = -1;
printf("\n %d -- %d", element, next);
}

//printNGE(arr, n);

return 0;
}``````

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

``````int findNextLargest(int [] arr, int eleIndex)
{
if(arr.length() == eleIndex+1)
return -1;
int minIndex = eleIndex+1;
for(int i = eleIndex+2; i < arr.length(); i++)
{
if(arr[i] < minIndex && arr[i] > arr[eleIndex])
minIndex = i;
}
return minIndex;
}``````

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

Question is not clear how O(n^2) will come if need to check for specified element..??

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

suppose we have an array a[]={55,77,11,43,66}
what one is supposed to do is take each element, compare it with every other elements to its right.
why would you compare it with every other elements to its right?
First do it for 1st element, say x=a.
55<77
55>11
55>43
55<66
here two elements(77,66) are greater than 55 to its right.
55 is ith element
77 is (i+1)th element
66 is (i+5)th element
here you shouldn't stop after seeing very first element say y>x (77>55)
cause y may be the next greatest element in this particular array
but not in the number line.
but here we've 66 which is greater than 55 and nearest to it.
so you should printf 55 --> 66
same way it can be done for other elements
77 --> -1
11 --> 43
43 --> 66
66 --> -1
that's why time complexity is o(n^2).

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

this can be done using dynamic programing

``````#include<iostream>
using namespace std;
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int a,i,n;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
int result[n];
for(i=0;i<n-1;i++)
result[i]=max(a[i],a[i+1]);
result[n-1]=-1;
for(i=n-1;i>=0;i--)
{
if(result[i]==a[i])
if(result[i+1]<result[i])
result[i]=-1;
else
result[i]=result[i+1];
}
for(i=0;i<n;i++)
cout<<a[i]<<"--->"<<result[i]<<"\n";
}``````

Comment hidden because of low score. Click to expand.
-2

nicely done!

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

Does not work. try the following input:
2,14,10,11,12,53,1,2

instead of having it display 14->53, it will display it as -1

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

Doesn't it fail for : 10 9 8 6 2 3 1 7 11 ?

10--->-1
9--->-1
8--->-1
6--->-1
2--->3
3--->7
1--->7
7--->11
11--->-1

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

it's not working for a[] = {4, 5, 2, 25, 15, 18, 42, 38, 98, 54};
it shows
4--->5
5--->25
2--->25
25--->-1
15--->18
18--->42
42--->98
38--->98
98--->-1
54--->-1

which is not true.

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

``````#include <iostream>
#include <stack>

using namespace std;

void findNextGreater(int [] a, int size) {
stack s;
int i;

for(i=0; i<size; i++)  {
while(!s.empty() && s.top() <a[i]) {
cout <<s.top() <<"-->" << a[i]<<endl;
s.pop();
}
s.push(a[i]);
}
while(!s.empty() ) {
cout <<s.top() <<"--> -1" <<endl;
s.pop();
}
}``````

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

@jzhu

If you directly print it in the while loop, due to stack out put will be in reverse for some element in the stack..
for 4,5,2,25 output will be
4 --> 5
2 --> 25
5 --> 25
25 --> -1

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

``````void printGreatestElement(int* a, int len)
{
stack s;
int*arr = new int[len];
for(int i=0; i<len;i++) arr[i] = -1;

for(int i=0; i<len-1; i++)
{
if(a[i] < a[i+1])
{
while(!s.empty() && a[s.top()] < a[i+1]) { arr[s.top()] = a[i+1]; s.pop(); }
}
s.push(i);
}

for(int i=0;i<len;i++) std::cout<< arr[i];
}``````

Time Complexity O(n)

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

@Downvoter
can you explain why you downvoted this solution?

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

Hey guys. I'm certain this piece of code works!

``````static int nextElement(int array[],int elem){
// Find the index of [elem]
int index=-1;
for(int i=0;i<array.length;i++){
if(array[i]==elem){
index=i;
break;
}
}
// if [elem] is the last element of the array or elem doesn't exist
// then return -1
if(index==array.length-1 || index==-1){
return -1;
}
// Find the next largest element
int max=Integer.MAX_VALUE;
while(index<array.length){
int nextElem=array[index];
if(nextElem>elem && nextElem<max){
max=nextElem;
}
index++;
}
return max;
}``````

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

``````private static void printNextLargest(int[] array) {

int[] index_array = new int[array.length];

for (int i = array.length - 1; i >= 0; i--) {
if (i == array.length - 1) {
index_array[i] = -1;
continue;
}
if (array[i] > array[i+1]) {
if (index_array[i+1] != -1) {
if (array[i] > array[index_array[i+1]]) {
index_array[i] = -1;
} else {
index_array[i] = index_array[i+1];
}
} else {
index_array[i] = -1;
}
} else {
if (index_array[i+1] != -1) {
index_array[i] = index_array[i+1];
} else {
index_array[i] = i+1;
}
}
}

// print the values
for (int j = 0; j < array.length; j++) {
if (index_array[j] != -1) {
System.out.println (array[j] + " -> " + array[index_array[j]]);
} else {
System.out.println (array[j] + " -> -1");
}
}
}``````

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

This code assumes that all the integers are unique (no duplicates), though it can be modified to take care of duplicates too. It also runs in O(n)

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

index_array[i] gives the index of largest element to right if i'th element not the next largest. So for array such as [4,5,2,25] it would give 4-->25

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

And this is correct output. Since 25 is the largest integer in this array, the output of this will be
4 -> 25
5 -> 25
2 -> 25
25 -> -1

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

I think the problem asks to find the "next immediate largest to the right" not the "absolute largest to the right" so for 4 it should be 4-->5

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

Anybody go thru this code and let me know if it works?

{
a = [10 9 8 6 2 3 1 7 11 ];
j=1,i=0; // j for backtracking
flag=0; // if set backtrack already done
while(i<n-1) // 'n' is the size of the list
{
if(a[i]<a[j])
{
printf(%d--%d\n",a[i],a[j]);
if (j<n)
{
j++;
}
else
{
i++;
j=i+1;
}
}
else
{
j++;
}
}

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

void set_next_grt(int a[],int l)
{
for(int i=l-1;i>=0;i--)
{
if(top==NULL)
{
push(a[i]);
a[i]=-1;
}
else
{
while(top!=NULL && top->data<a[i])
pop();
if(top==NULL)
{
push(a[i]);
a[i]=-1;
}
else
{
int k=top->data;
push(a[i]);
a[i]=k;
}
}
}
}

o(n) complexity.if u look deeply then each element is pop only once.

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

why not check from the right?
It's simple in O(n).

``````public static void findMaxOnTheRight(int[] input){
int[] max = new int[input.length];
int maxNow = input[input.length-1];
max[input.length-1] = -1;
for(int i=input.length-2; i>=0; i--){
if(input[i+1] > maxNow){
maxNow = input[i+1];
}
max[i] = maxNow;
}
}``````

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

Start from right to left keeping track of maximum.
arr = [4, 45, 2, 25]
barr= [45,25,25,-1] // new array that gives next greatest element

``````let length of array be n
b[n-1] = -1; // as there is no next greatest
int temp = arr[n-1]
for (i=n-2; i>=0; i--)
{
barr[i] = temp;
if(arr[i] > temp)
{
temp = arr[i];

}
}``````

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

This is my version in C#.

``````public void NextGreatestElement(int[] inp)
{
Stack<int> stack = new Stack<int>();

stack.Push(inp);

for (int i = 1; i < inp.Length; i++) {
while (stack.Count>0 && stack.Peek() < inp[i])
{
Console.WriteLine("{0} -> {1}", stack.Peek(), inp[i]);
stack.Pop();
}
stack.Push(inp[i]);
}

foreach(int i in stack) Console.WriteLine("{0} -> {1}", i, -1);
}``````

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

1) find the min and max values from the integer array.
2) create an array of (max - min + 1) with initial value 0s
3) put array[a[i] - min] = a[i];
4) loop the array, output non-zero values one by one.

O(n)

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

``````int NextGreatestElement(int[] array, int index)
{
if (index == array.Length - 1)
return -1;
int max = array[index+1];
int i = index +2;
while(i < array.Length && max < array[i])
{
max = array[i];
i++;
}
return max;
}``````

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

for output {4, 5, 25, 2, 30} it would return 25 for index 0 which is 4.

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

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.