Amazon Interview Question
Country: India
Working code
int a[6] = {2,5,3,4,6,1};
for (int i = 0;i < 6; i++)
{
cout << a[i] << endl;
}
cout << endl;
vector<int> nNum;
nNum.push_back(0);
for(int i = 1; i< 6; i++)
{
while (nNum.size() && a[i] > a[nNum.back()])
{
a[nNum.back()] = a[i];
nNum.pop_back();
}
nNum.push_back(i);
}
while (nNum.size())
{
a[nNum.back()] = -1;
nNum.pop_back();
}
for (int i = 0;i < 6; i++)
{
cout << a[i] << endl;
}
//use stack. traverse from last elem. O(n)
for (i = n-1; i >= 0; i--) {
if (stack.empty()) {
printf("%d->%d", A[i], -1);
} else if (A[i] < stack.top()) {
printf("%d->%d", A[i], stack.top());
} else if (A[i] > stack.top()) {
// pop all smaller elements to see if there is bigger one.
while (!stack.empty() && A[i] > stack.top()) {
stack.pop();
}
printf("%d->%d", A[i], stack.empty() ? -1 : stack.top());
}
stack.push(A[i]);
}
This also becomes O(n^2) considering each element is being compared by the whole stack.
try taking an example. take the amortized cost of whole operation. it can never be > O(n).
Pseudocode:
1) Create a BST.
2) Whenever a node becomes bigger than the parent node, traverse through the tree(which has only left childre) and for all its children print the current node as the next bigger node.
3) Delete all nodes smaller than current node.
4) Repeat the same process.
Eg:
1) 2
... / \
2) 2
... \
... 5
Now print 2 ->5 and delete 2.
3) 5
... /
... 3
... ... \
... ... ... 4
Now print 3->4 and delete 3.
4) 5
... /
...4
5) 5
... / \
... 4 6
Now print 5->6 and 4->6 and delete 5 and 4
Now it becomes,
6) 6
... /
... 1
Now once array becomes null, traverse through the tree and print -1.
O(n) time and O(n) space algorithm
Maintain a stack
1.start from the first element.push it's position into the stack
2.now check the second element with top of stack.if it is greater pop the stack and set its value to this second element.
else push this element to the stack.
3.do the same for rest of the elements.
4.elements left in the end are set to -1
Note:pop is to be performed till either stack is empty or top is stack is greater than current element
eg {2,5,3,4,6,1}
Stack Array
1.{2}
2.{5} {2} {5,5,3,4,6,1} //pop 2 and set its value to 5
3.{3} {5} {5,5,3,4,6,1} //do nothing
4.{4} {5,3} {5,5,4,4,6,1} //pop 3
5.{6} {5,4} {5,6,4,6,1} //pop 4 and 5
6.{1} {6} {5,6,4,6,6,1}
7. {5,6,4,6,-1,-1} //set left elements to -1
#include <stdio.h>
int nextBiggerInList(int *a, int arrayLength,int num)
{
int index = -1;
int nextLargest = -1;
//Get the index of the num
for(int i = 0;i<arrayLength;i++)
{
if(a[i] == num)
{
index = i;
break;
}
}
//Element not found
if(index == -1)
return -1;
//Find some number greater than num if present
for(int i=index+1;i<arrayLength;i++)
{
if(a[i]> num)
{
nextLargest = a[i];
break;
}
}
//Handle all elemets same as num after num
if(nextLargest == -1)
return -1;
//Find next largest number
for(int i=index+1;i<arrayLength;i++)
if(a[i]> num && nextLargest > a[i])
nextLargest = a[i];
return nextLargest;
}
int main()
{
//Driver program
int a[10] = {2,5,3,4,6,1};
for(int i = 0;i<7;i++)
printf("nextBigger of %d = %d \n",i,nextBiggerInList(a,10,i));
return 0;
}
Should be O(n).
psuedo code, stack push pop operation assumed.
Prints the proper results but order is not maintained, can someone suggest some other method to print it in correct order as well.
for(int i=0; i<arraylen;i++) {
if(stack.empty()) {
stack.push(a[i]);
}
else {
if(a[i] >stack.top() ) {
while(stack.top() < a[i] && !stack.empty()) {
printf("%d->%d",stack.top(),a[i]);
stack.pop();
}
}
stack.push(a[i]);
}
}
while(!stack.empty()) {
printf("%d->%d",stack.top(),-1);
stack.pop();
}
Dry run of algo on sample.
2,6,3,4,5,1,8
-----------
push(2)
-----------
2->6
pop(2)
push(6)
----------
push(3)
-----------
3->4
pop(3)
push(4)
-----------
4->5
pop(4)
push(5)
-----------
push(1)
-----------
1->8
pop(1)
5->8
pop(5)
6->8
pop(6)
push(8)
-----------
8->-1
pop(8)
Wait till you find the number. then return the next number bigger than that. if end of loop return -1.
public static int nextBigger(int []arr,int k){
boolean begin=false;
for(int i=0;i<arr.length;i++){
if(!begin&&arr[i]==k){
begin=true;
}
else if(begin&&arr[i]>k){
return arr[i];
}
}
return -1;
}
This is hilariously simple. Don't know why people are building stacks and bst.
Traverse the array and find the number. Keep traversing the array and return the next num that appears which is bigger than input number.
Indeed.
It takes O(n) time to find the number, so say, num appears at n/2th index on avg. Now to find bigger num after this index, search in remaining array in right part of avg size(n- k/2) = O(n)
Total = O(n) + O(n) = O(n) < O(nlgn)
Space complexity = none
Its better soln than any BST/stack.
I really do not see why we need to over complicate things. We can do everything in O(n) complexity with no extra space aside from a couple variables. Just like this
public class arrayFunctions {
public static void main(String args[]) {
int temp[] = {3,2,6,1,1,1,2,4,7,8,9};
arrayFunctions test = new arrayFunctions();
System.out.println(test.nextLargest(temp,4));
}
public int nextLargest(int arr[], int value) {
int currDiff = -1*(int)Math.pow(2,31);
int nextVal = value;
int diff = 1;
for (int i = 0;i<arr.length;i++) {
diff = value-arr[i];
if (arr[i] > value && diff > currDiff && diff != 0) {
nextVal = arr[i];
currDiff = diff;
}
}
return nextVal;
}
}
You simply put in an array, and the integer for which you want to find the next largest value of. It wil run in O(n) time. Simple
package Numbers;
import java.util.HashSet;
import java.util.Stack;
public class NextLargestInArray {
int[] arr;
Stack<Integer> stack = new Stack<Integer>();
public NextLargestInArray() {
arr = new int[] {1,9,5,3,4,12,7};
findNextLargest();
}
private void findNextLargest() {
int temp= 0;
for(int i :arr)
{
if(stack.isEmpty())
{
stack.push(i);
continue;
}
while(!stack.isEmpty())
{
temp = stack.peek();
if(i > temp)
{
System.out.println(temp + "->" + i);
stack.pop();
}
else break;
}
stack.push(i);
}
while(!stack.isEmpty())
{
System.out.println(stack.pop() + "->" + -1);
}
}
}
#include<stdio.h>
#include<stack>
using namespace std;
int main(void){
int arr[]={2,5,3,4,6,1};
stack<int> s;
int sz=7;
s.push(arr[0]);
for(int i=1;i<6;i++){
if(s.top()<arr[i]){
printf("%d->%d\n",s.top(),arr[i]);
s.pop();
if(!s.empty()){
int flag=0;
while(!flag){
if(!s.empty() && s.top()<arr[i])
{
printf("%d ->%d\n",s.top(),arr[i]);
s.pop();
}
else{
flag=1;
s.push(arr[i]);
}
}
}
else
s.push(arr[i]);
}
else{
s.push(arr[i]);
}
}
while(!s.empty()){
printf("%d ->%d\n",s.top(),-1);
s.pop();
}
return 0;
}
bool PrintNextBigger(int[] data, uint count)
{
stack<int> pending;
for (int index = 0 ; index < count; ++index)
{
if(pending.size() == 0)
pending.push(data[index]);
else if (pending.top() > data[index])
pending.push(data[index])
else
{
while(pending.size() > 0 && pending.top() < data[index])
print("%ud->%ud", pending.pop(), data[index]);
pending.push(data[index]);
}
}
while(pending.size())
printf("%ud->%ud", pending.pop(), -1);
}
#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int> d;
//int arr[] = {2,5,3,4,6,1};
int arr[] = {5,6,7,8,9,10,4,3,2,1,0,1};
int size = sizeof(arr)/sizeof(arr[0]);
for(int i=0; i<size; i++)
{
for(int k=i; k<size; k++)
{
if (k == size-1)
{
d.push_back(-1);
break;
}
else if ( arr[i] < arr[k+1] )
{
d.push_back(arr[k+1]);
break;
}
}
}
for(int i=0; i<size; i++)
{
cout << arr[i] << " -> " << d[i] << endl;
}
return 0;
}
{2,5,3,4,61}
Use the min Heap. Insert the element inside it in order. Whenever you encounter a element larger then heap value. Delete all the elements of min value from it and print it.
1. minHeap --> 2
2. minHeap --> 2,5 (delete 2 as lower then 5 and print "2 5") (minHeap --> 5)
3. minHeap --> 3, 5
4. minHeap --> 3,4,5 (delete the 3 and print "3 4") (min Heap --> 4, 5)
5. minHeap --> 4, 5,6 (delete 4,5 and print "4 6" and "5 6") (minHeap 6)
It is an O(nlogn) and extra space of O(n).
#include<stdio.h>
#include<conio.h>
struct stack{
int *arr;
int top;
};
struct stack * createStack(int capacity){
struct stack * s = (struct stack*)malloc(sizeof(struct stack));
s->top = -1;
s->arr = (int *)malloc(sizeof(int)*capacity);
int i = 0;
for(i=0;i<capacity;i++){
s->arr[i] = 0;
}
return s;
}
void push(struct stack * s, int data){
s->top++;
s->arr[s->top] = data;
}
int pop(struct stack * s){
return s->arr[s->top--];
}
int top(struct stack *s){
return s->arr[s->top];
}
int isEmpty(struct stack *s){
if(s->top==-1){
return 1;
}
else{
return 0;
}
}
void findnext(int a[],struct stack *s,int start,int end){
int next =0,temp,i;
push(s,a[0]);
for(i = start+1;i<end+1;i++){
next = a[i];
while(!isEmpty(s) && next>top(s)){
printf("%d -> %d \n",pop(s),next);
}
push(s,next);
}
while(!isEmpty(s))
{
next = -1;
printf("%d -> %d\n", pop(s), next);
}
}
int main(){
int a[]={2,5,3,4,6,1};
int size = sizeof(a)/sizeof(a[0]);
struct stack * s = createStack(size);
findnext(a,s,0,size-1);
getch();
return 0;
}
One way could be to go through the list and create a binary search tree. This would take time of O(nlogn). Then for each node in the tree, the correct answer is it's right child which would take again O(nlogn) so total complexity is O(nlogn)
I guess it will fail, because
input: {2,5,3,4,6,1}
output:
2->5
5->6
3->4
4->6
How 6 can be right child for both 5 and 4?
Vandana, it's not the right child always.
The next bigger element will be the successor of the current element in "in-order" traversal of binary tree viz left - root - right.
It may not be performance wise efficient in average case because, sorting the elements in array itself and find the next element performs better. If we use a good sorting algorithm on source array that runs in O(nlog(n)) time, the next bigger element is the next element itself, taking almost no time, compared to finding successor in in-order traversal.
O(n) time and O(n) space algorithm
Maintain a stack
1.start from the first element.push it's position into the stack
2.now check the second element with top of stack.if it is greater pop the stack and set its value to this second element.
else push this element to the stack.
3.do the same for rest of the elements.
4.elements left in the end are set to -1
Note:pop is to be performed till either stack is empty or top is stack is greater than current element
- guneesh December 17, 2012eg {2,5,3,4,6,1} Curr Stack Array 1.{2} 2.{5} {2} {5,5,3,4,6,1} //pop 2 and set its value to 5 3.{3} {5} {5,5,3,4,6,1} //do nothing 4.{4} {5,3} {5,5,4,4,6,1} //pop 3 5.{6} {5,4} {5,6,4,6,1} //pop 4 and 5 6.{1} {6} {5,6,4,6,6,1} 7. {5,6,4,6,-1,-1} //set left elements to -1