Amazon Interview Question Software Engineer / Developers
Country: United States
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
It's O(n) since worst-case scenario is that your are pushing and popping each element once.
good idea.Code in c follows as below
#include <stdio.h>
signed int count = 0;
struct s_
{
int data;
int index;
}s_t[100];
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], 0);
for(i=1;i<(sizeof(a)/sizeof(a[0]));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[0]));i++) {
printf("%d\n", a[i]);
}
return 0;
}
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[0]
top_element_value = top_element[1]
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[0]
top_element_value = top_element[1]
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]
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[1])
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.
@eugene.yarovoi. May be that i misunderstood the question. Can u tell me its correct interpretation?
@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.
void NextGreatestElement(int arr[],int size)
{
if(size==1)
{
printf("%d ----> %d\n",arr[0],-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();
}
}
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
}
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);
elements.add(0, nextGreatestElement);
}
else {
current=nextGreatestElement;
}
}
else {
currentStack_.add(currentStack_.size(), nextGreatestElement);
}
}
System.out.println(current+" --> -1");
}
}
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
answer = [-1] * (length)
tmp = -1
(input.length - 2).downto(0) do |index|
if input[index + 1] > input[index]
answer[index] = input[index + 1]
else
tmp_index = index + 1
while tmp_index < answer.length
if answer[tmp_index] > input[index]
answer[index] = answer[tmp_index]
break
end
tmp_index += 1
end
end
end
answer.join(', ')
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"
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
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[0]);
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));
}
/*
* 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[0]);
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));
}
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[0]);
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));
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int arr[]= {4,15,2,9,20,11,13};
int n = sizeof(arr)/sizeof(arr[0]);
int i,next,element;
stack<int>s;
s.push(arr[0]);
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;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int arr[]= {4,15,2,9,20,11,13};
int n = sizeof(arr)/sizeof(arr[0]);
int i,next,element;
stack<int>s;
s.push(arr[0]);
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;
}
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[0].
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).
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[20],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";
}
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
Doesn't it fail for : 10 9 8 6 2 3 1 7 11 ?
Your code outputs :
10--->-1
9--->-1
8--->-1
6--->-1
2--->3
3--->7
1--->7
7--->11
11--->-1
#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();
}
}
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)
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;
}
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");
}
}
}
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)
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
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
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++;
}
}
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.
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;
}
}
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];
}
}
This is my version in C#.
public void NextGreatestElement(int[] inp)
{
Stack<int> stack = new Stack<int>();
stack.Push(inp[0]);
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);
}
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;
}
Push the first element of array in a stack.
- Anonymous April 02, 2013take 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[1])
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.