## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

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

Maintain another stack and keep pushing the min element on the stack as in when found.
Before each push on stack 1, just check if the current element is less than the top element of second stack if yes then push it on to stack 2.

While poping an element from stack1 check if the top of stack2 is same as the element in that case pop both the elements so that next min would show up on stack 2 for next min operation.

This would ensure that we pop out the min element in o(1) time.

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

but if the stack say an array is given as input... how can u find the min element from it in O(1)

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

I think mr has given the right solution.

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

@debajyothi
sorry i didn't get ur doubt clearly, but implementation of stack via array or link list doesn't change anything here. stack is stack ie LIFO.

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

Solution given by mr is to update a second stack to keep track of the minimum element while building the first stack.
The same can be done if we just keep a variable (say,min) and update its value every time we push a smaller element in the stack (compared to the element at the top).A second stack is not needed.
However, what is required is to find the minimum element in an already build stack, without losing it, in O(1) time complexity and the minimum possible space complexity.

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

@sp: what i think is u missed the point of finding min multiple times. with just 1 variable to track the min you won't be able to track the other min(as in 2nd min, 3rd min...so on ) when the 1st min has been popped out of the stack.

Keeping a second stack would solve that problem too and would return successive min also in o(1) time.

I hope i am not missing anything here, depending on what you mention.

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

Slight Modification.. Not only less then.. you have to push element less then and equal to.

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

Don't you think using two stacks will voilate the space complexity which is O(n)

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

@HunterCpp
Achieving what we want to find here can be done using this approach in o(1).

Regarding the complexity it would depend on the worst case or best case scenario and on an average the second stack wouldn't contain those many elements for a uniformly distributed data. But overall the space complexity will be o(n) != n (exactly).

Worst case: push order 4 3 2 1
in this case both stacks will contain 4 elements each

Best case: push order 1 2 3 4
in this case 1 stack will have 4 and other will have 1 only

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

but since you are checking top element every time, that means you are doing a primitive operation 'n' times. So the time complexity is O(n).

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

But that would mean the stack1 is empty at the beginning?

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

To understand this concept of finding minimum, maximum or range of stack in O(1) time watch this wonderful solution

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

Wonderful? LOL. -1.

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

Stop promoting your videos...it's getting annoying.

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

You really like describing your own videos as "wonderful", etc. They're not that wonderful. They're handwritten solutions on a virtual blackboard.

That said, they're usually correct solutions, which is much, much more than can be said for most of the solutions on this site. So just for that I would say keep posting links to them. It would be better if you promoted with a disclaimer that they are your videos, though, and if you let others decide for themselves if they are "wonderful" or not.

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

This is more of a question about picking the best data structure, under different circumstances. You need to structure the data in such a way as to *find* the minimum element in O(1). Space is O(n), which could be 2n,etc, suggesting we could use another data structure inside the Stack abstraction. A couple possible options:

1) Maintain a min-heap upon push/pop, O(nlogn) add/remove. Finding the min is simply a matter of peeking at the top of the min-heap. The advantage here over push/pop, is you don't need to shift all the elements in memory.

2) Maintain another array, but use Select Sort O(nlogn), which has an advantage over quicksort, in that it does not need to sort the entire array, but stops when it finds the element at rank n.

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

package amazon;

import java.util.Stack;

class MyStack{
public Stack<Integer> basic;
public Stack<Integer> hold_min;
public MyStack(){
this.basic=new Stack<Integer>();
this.hold_min=new Stack<Integer>();
}
public void push(int newItem){
if(newItem<=this.getmin()){
this.hold_min.push(newItem);
}
this.basic.push(newItem);
}
public int pop(){
if(this.basic.isEmpty()){
return Integer.MIN_VALUE;
}
int value=this.basic.pop();
if(value==this.getmin()){
this.hold_min.pop();
}
return value;
}
public int getmin(){
if(this.hold_min.isEmpty()){
return Integer.MAX_VALUE;
}
else{
return this.hold_min.peek();
}
}
}

public class pop_push_min_in_stack{

public static void main(String[] args) {
MyStack test=new MyStack();
test.push(6);
test.push(3);
test.push(7);
System.out.println(test.getmin());
System.out.println(test.pop());
}

}

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

If you can find the minimum of a stack in O(1) won't you be able to sort n numbers in O(n)?

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

are you kidding?

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

In addition to stack, maintain a min-heap and encapsulate both in a class. The idea of encapsulating both in a class is to hide from the user of the class that there is a min-heap in it. That should solve the problem.

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

Didn't see anything that said there are no duplicates in the stack, so simply tracking the minimum followed by the next minimum in another stack won't work in that case. But it seems like its on the right track in that every time someone pushes a new element that equals the previous min, you have to push it again onto the tracking stack. So if your stack contains 2, 1, 3 (top to bottom) then the tracking stack should contain 1, 3. If someone pushes another 1 your stack will have 1,2,1,3 and the tracking stack will contain 1,1,3. Then if someone pops the first 1, you tracking stack will change to 1,3 and you will still know the minimum is 1. Popping the 2 keeps tracking stack as 1,3 and then popping the other 1 changes the tracking stack to 3, the new minimum.

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

2) m=first element
3) merge each additional element in O(n) running time after each push
4) Find smallest element in O(1) time, m

If the smallest element K is popped, m == K, pop m from m. Then, the next smallest element will be m=m, and so on.

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

@Jack : I didnt get you exactly. However I guess we wont be able to find the min value in O(1) time complexity.

@mr:
The problem statement is find the minimum value in a stack .. no that how to maintain a min value while creating a stack. For that matter with every structure you can keep track of the min values .. need not be stack.

@Victor:

even if you encapsulate the things running times wont change from the perspective of algorithmics.. so I guess thats not going to help us.

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

Algo:
Have a custom stack object and always have minimum value along with actual value on the stack top

package com.santosh.career;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Career14462745 {
public static void main(String[] args) {
Stack<CustomStack> stack = new Stack<CustomStack>();
CustomStack s1 = new CustomStack();
CustomStack s2 = new CustomStack();
CustomStack s3 = new CustomStack();
s1.currentValue = 5;
s2.currentValue = 3;
s3.currentValue = 1;
List<CustomStack> stacks = new ArrayList<CustomStack>();
for (CustomStack customStack : stacks) {
if (stack.isEmpty()) {
customStack.minimumValue = customStack.currentValue;
stack.push(customStack);
} else {
CustomStack temp = stack.pop();
if (temp.minimumValue < customStack.currentValue) {
customStack.minimumValue = temp.minimumValue;
} else {
customStack.minimumValue = customStack.currentValue;
}
stack.push(temp);
stack.push(customStack);
}
}
System.out.println(stack.pop().minimumValue);
}
}

class CustomStack {
int currentValue;
int minimumValue = Integer.MAX_VALUE;
}

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

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

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

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

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

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

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

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

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

if there are n comparisons! how could it be O(1)????

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

pop stack, store the value in a variable say min
again pop and compare with min, if it is less than min, replace it with the min
but in this case also we are iterating the n elements, so it will be O(n)

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

pop stack, store the value in a variable say min
again pop and compare with min, if it is less than min, replace it with the min
but in this case also we are iterating the n elements, so it will be O(n)

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

simple solution:
use two stacks both of same size and intially empty.
say a and b
start pushing elements in them.how?
say 18,19,89,11,42have to be pushed
a will contain all elements in normal way but b will contain only minimum elements encountered.(how b will contain minimum elements?by comparing them with first element pushed,here 18)
step1:
18 in a and 18 in b
step2:
19 in a and nothing to be done with b.
step3:
89 in a and nothing to be done with b.
step4:
11 in a and 11 in b(why?beacause 11 is less than 18)
step5:
42 in a and nothing to be done with b.
YOU ARE DONE
Now pop top element from b, you get the answer.

explaination of O(1) :
we are using push and pop only, which have O(1) time complexity.
push/pop has O(1) time complexity.Why?we deal with only one element i.e top element in push/pop.
Hope this helps.
Cheers
:)

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

``````package com.pocketlab.practice.ds;

import java.util.ArrayList;
import java.util.List;

public class MinStack {
List<Node> items;

public void push(int num) {
if (items == null) {
items = new ArrayList<Node>();
}
Node node = new Node(num);
if (items.size() > 0) {
node.min = Math.min(items.get(items.size() - 1).min, num);
node.max = Math.max(items.get(items.size() - 1).max, num);

} else {
node.min = num;
node.max = num;
}
// System.out.println("Pushed > " + node.data);
printStack();
}

public Node pop() {
Node popThis = null;
if (items != null && items.size() > 0) {
popThis = this.items.get(items.size() - 1);
items.remove(items.size() - 1);
// System.out.println("Popped > " + popThis.data);
}
printStack();
return popThis;
}

public int getMin() {
if (items != null && items.size() > 0) {
int min = this.items.get(items.size() - 1).min;
System.out.println("Minimum Element > " + min);
return min;
}
return -1;
}

public int getMax() {
if (items != null && items.size() > 0) {
int max = this.items.get(items.size() - 1).max;
System.out.println("Maximum Element > " + max);
return max;
}
return -1;
}

public void printStack() {
int i = 0;
for (Node n : items) {
System.out.print(n.data + " > ");
if (i == items.size() - 1) {
System.out.print(" | Min = " + n.min + " |");
System.out.print(" | Max = " + n.max + " |");

}
i++;
}
System.out.println();
}

public static void main(String args[]) {
MinStack stack = new MinStack();
stack.push(10);

stack.push(13);
stack.push(19);
stack.push(3);
stack.push(2);
stack.push(2);
stack.printStack();
stack.pop();
//stack.getMin();
stack.printStack();

}
}

class Node {

int data;
int min;
int max;

public Node(int data) {
super();
this.data = data;
}

public Node() {
super();
}

}``````

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

Implementation of code in C with test cases and also finds max min and range:
overall time complexity : O(n)
overall space complexity : O(n)
time complexity for min max range operations:O(1)

``````#include<stdio.h>
#include<stdlib.h>
#define MAX 5

struct stack
{
int tos;
int array[MAX];
};

int is_empty(struct stack*st)
{
return (st->tos==-1)?1:0;
}

int is_full(struct stack*st)
{
return (st->tos==MAX-1)?1:0;
}

int top(struct stack*st)
{
return st->array[st->tos];
}

void printStack(struct stack*st)
{
int i;
for(i=0;i<=(st->tos);i++)
printf("%d ",st->array[i]);
printf("\n");
}

void simple_push(struct stack*st,int n)
{
if(!is_full(st))
st->array[++(st->tos)]=n;
}

void pushMinMax(struct stack*st,struct stack*maxst,struct stack*minst,int n)
{
if (!is_full(st))
{
simple_push(st,n);
if (is_empty(maxst))
simple_push(maxst,n);
else
{
if (n>=top(maxst))
simple_push(maxst,n);
else
simple_push(maxst,top(maxst));
}
if (is_empty(minst))
simple_push(minst,n);
else
{
if (n<=top(minst))
simple_push(minst,n);
else
simple_push(minst,top(minst));
}
}
}

int simple_pop(struct stack*st)
{
if(!is_empty(st))
return st->array[(st->tos)--];
}

int popMinMax(struct stack*st,struct stack*maxst,struct stack*minst)
{
int x=simple_pop(st);
simple_pop(maxst);
simple_pop(minst);
}

int getMin(struct stack*minst)
{
}

int getMax(struct stack*maxst)
{
}

int getRange(struct stack*maxst,struct stack*minst)
{
}

int main()
{
struct stack st;
struct stack maxst;
struct stack minst;
int arr[]={2,4,4,1,3};
int i;
st.tos=-1;
maxst.tos=-1;
minst.tos=-1;
for(i=0;i<5;i++)
{
pushMinMax(&st,&maxst,&minst,arr[i]);
}
printStack(&st);
printStack(&maxst);
printStack(&minst);
printf("min:%d ",getMin(&minst));
printf("max:%d ",getMax(&maxst));
printf("range:%d \n",getRange(&maxst,&minst));
popMinMax(&st,&maxst,&minst);
popMinMax(&st,&maxst,&minst);
popMinMax(&st,&maxst,&minst);
printStack(&st);
printStack(&maxst);
printStack(&minst);
printf("min:%d ",getMin(&minst));
printf("max:%d ",getMax(&maxst));
printf("range:%d \n",getRange(&maxst,&minst));
}``````

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

public class MinStack {

Node top;

public void push(int x)
{
if(top == null)
{
top = new Node(x);
}
else
{
Node temp = new Node(x);
temp.next = top;
temp.min = Math.min(top.min, x);
top = temp;
}
}

public void pop()
{
if(top == null)
{
System.out.println("Stack empty!");
return;
}

top = top.next;
}

public int top()
{
if(top == null)
{
System.out.println("Stack empty!");
return Integer.MAX_VALUE;
}

}

public int min()
{
if(top == null)
{
System.out.println("Stack empty!");
return Integer.MAX_VALUE;
}

}

public static void main(String args[])
{
MinStack mStack = new MinStack();
mStack.push(7);
mStack.push(8);
System.out.println(mStack.min());
mStack.push(5);
mStack.push(9);
System.out.println(mStack.min());
mStack.push(5);
mStack.push(2);
System.out.println(mStack.min());
mStack.pop();
mStack.pop();
System.out.println(mStack.min());
}

}

class Node {
int value;
int min;
Node next;

Node(int x)
{
value = x;
next = null;
min = x;
}
}

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

We can take two stacks and push all the elements one by one in stack 1. stack 2 stores the current minimum element present in stack 1 ,at the end print the top of the element of stack 2.

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

Logic::Create own stack class using link list and add extra variable min_elem in stack ,which will contain the minimun of stack.While pushing the data also check if new data is less than minmum_element else set new data as minimum elem.A function get_minmum will return the minimum element in stack at any time i.e O(1) complexity

C++ prog::

#include <iostream>
#include <cstdlib>

using namespace std;
struct node
{
int data;
int min_elem;

struct node *next;

};

class stack
{
public:
int min_elem;

int get_min()
{
return min_elem;
}

void push( int );
int pop();

int count;
int capacity;
node *root;

stack(int stack_size)
{
std::cout << "\n Stack Consructior";

root = NULL;
count = 0;
min_elem=0;
capacity = stack_size;

}

~stack()
{

std::cout << "\n Stack Desrtuctor";
}

};

void display(struct node *);

int main()
{

std::cout <<"\n func===" << __func__;

struct node *root=NULL ;
stack own_stack(10);
own_stack.push(109);
own_stack.push(2);
own_stack.push(8);
own_stack.push(9);
own_stack.push(5);
own_stack.push(6);
own_stack.push(7);

std::cout <<"\n min value in stack" << own_stack.get_min();

}

void stack::push (int data)
{

std::cout <<"\n we are in push";

if(count == capacity)
{
std::cout <<"\n stack full completely";
return;

}

struct node *tmp = (struct node *) malloc(sizeof(struct node));

tmp->data = data;
tmp->next =NULL;

if(root ==NULL)
{
root=tmp;
min_elem= root->data;
count++;
return ;
}

if(min_elem > tmp->data)
{
min_elem = tmp->data;
}

tmp->next =root;
root=tmp;

count++;

}

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

Logic::Create own stack using link list and add extra element min_elem in stack class .
Before pushing the data check whether the new data is less than min_elem, if its not than set min_elem value as new_data and also push the new data into stack

``````{
#include <iostream>
#include <cstdlib>

using namespace std;
struct node
{
int data;
int min_elem;

struct node *next;

};// *root;

class stack
{
public:
int min_elem;
// node stack_node;
/* void set_min(int data )
{
stack_node.min_elem = data;

}
*/
int get_min()
{
return min_elem;
}

void push( int );
int pop();

int count;
int capacity;
node *root;

stack(int stack_size)
{
std::cout << "\n Stack Consructior";
// stack_node.data = 0;
//stack_node.min_elem = 0;
// stack_node.next=NULL;
root = NULL;
count = 0;
min_elem=0;
capacity =  stack_size;

}

~stack()
{

std::cout << "\n Stack Desrtuctor";
}

};

void display(struct node *);

int main()
{

std::cout <<"\n func===" << __func__;
int vertex = 5;
int option;
int data;

struct node *root=NULL ;//= (struct node *  start) malloc ( sizeof(struct node) );
stack own_stack(10);
own_stack.push(109);
own_stack.push(2);
own_stack.push(8);
own_stack.push(9);
own_stack.push(5);
own_stack.push(6);
own_stack.push(7);

std::cout <<"\n min value in stack" << own_stack.get_min();

}

void stack::push (int data)
{

std::cout <<"\n we are in push";

if(count == capacity)
{
std::cout <<"\n stack full completely";
return;

}

struct node *tmp = (struct node *) malloc(sizeof(struct node));

tmp->data = data;
tmp->next =NULL;

if(root ==NULL)
{
root=tmp;
min_elem= root->data;
count++;
return ;
}

if(min_elem > tmp->data)
{
min_elem = tmp->data;
}

tmp->next =root;
root=tmp;

count++;

}``````

}

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

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

class MinStack {
public:
void push(int n) {
stack_.push(n);
// track all multiple min values
if (min_stack_.empty() || n <= min_stack_.top())
min_stack_.push(n);
}

void pop() {
if (stack_.empty())
return;

auto n = stack_.top();
stack_.pop();
if (n == min_stack_.top())
min_stack_.pop();
}

int top() {
return stack_.top();
}

int min() {
return min_stack_.top();
}

bool empty() {
return stack_.empty();
}

private:
std::stack<int> stack_;
std::stack<int> min_stack_;
};

int main() {
MinStack stack;
for (auto n : {10, 9, 20, 8, 8, 30, 8, 7}) {
stack.push(n);
std::cout << "stack.top() is " << stack.top() << ", stack.min() is " << stack.min() << std::endl;
}
std::cout << std::endl;
while (!stack.empty())
{
std::cout << "stack.top() is " << stack.top() << ", stack.min() is " << stack.min() << std::endl;
stack.pop();
}
}``````

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

O(1) solution? Kidding huh?
You have to go through all elemnts of stack to find minimum..that will make it O(n) for sure..

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

abcd

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.