Amazon Interview Question
Software Engineer / DevelopersTeam: AWS
Country: United States
Interview Type: Phone Interview
I don't think we can do this in O(1) time both for push and pop.
aside from the stack we should keep a sorted array to retrieve min elements where each element on the stack is linked to some position in the sorted array.
thus push/pop can be done in O(log n) amortized time using binary search to add/remove elements from the sorted array
while retrieving 'min' can be done in constant time
First answer with each stack element containing and extra field min :
//
// main.c
// MinStack
//
// Created by Srikant Aggarwal on 25/12/11.
// Copyright 2011 NSIT. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
typedef struct stack_element
{
int data;
int min;
struct stack_element *next;
} stack_element;
stack_element *top = NULL;
void push(int data)
{
stack_element *temp = (stack_element *)malloc(sizeof(stack_element));
temp -> data = data;
temp -> next = top;
if(top == NULL)
temp -> min = data;
else
{
if(data <= top -> min)
temp -> min = data;
else
temp -> min = top -> min;
}
top = temp;
}
int pop()
{
int data;
if(top != NULL)
{
data = top -> data;
stack_element *temp = top;
top = top -> next;
free(temp);
temp = NULL;
return data;
}
return -1;
}
int get_min()
{
if(top != NULL)
return top -> min;
return -1;
}
int main (int argc, const char * argv[])
{
int ans = 1;
while(ans == 1)
{
int op, min;
printf("\n1. Push\n2. Pop\n");
scanf("%d", &op);
if(op == 1)
{
int element;
printf("\nPush Element = ");
scanf("%d", &element);
push(element);
if((min = get_min()) != -1)
printf("Min = %d\n", min);
}
else if(op == 2)
{
int element;
if((element = pop()) != -1)
{
printf("\nPopping Element %d", element);
if((min = get_min()) != -1)
printf("\nMin = %d\n", min);
else
printf("\nStack Empty\n");
}
else
printf("\nStack Empty\n");
}
else
printf("\nInvalid operation\n");
printf("\nContinue ? \n1. Yes\n2. No\n");
scanf("%d", &ans);
}
}
The best solution will be..
Create one more stake say min_stake contains the min value at the top.
While pushing just check the element which is pushed is less then min
if yes push this also to the min else do nothing.
while poping check if element is min.. pop the top most element also from
the min_stack.
this min_stack will contain the min element always at the top. provided all elements are diff.
If we are gonna get same elements we can store address of first occrance of min element in the min stack along with its value.
what if you push the elements onto stack in the following order:
[1 5 3 2]
thus your min_stack would contain only element '1'
then, when you pop '1' from the stack, your min_stack would be empty..
if min-stack's top element is less than the new value
insert top element again to the min_stack.
else
insert new value to min stack
if you do a pop in original stack do a pop in min-stack also
so min-stack's top value will be minimum for the current state of original stack.
public class MinStack<T extends Comparable<T>> {
private Stack<T> s1 = new LinkedList<T>();
private Stack<T> s2 = new LinkedList<T>();
public void push(T obj) {
s1.push(obj);
if (s2.empty()) {
s2.push(obj);
} else if (obj.compare(s2.top()) <= 0) {
s2.push(obj);
}
}
public void pop() {
if (s1.empty()) {
return;
}
T obj = s1.top();
s1.pop();
if (s2.empty()) {
return;
}
if (obj.compare(s2.top()) == 0) {
s2.pop();
}
}
public T min() {
if (s2.empty()) {
return null;
}
return s2.top();
}
}
I think the solution is:
1. Suppose push 5 in a empty stack.
2. Since it is first value, the min is 5. So push 5 and 5. The first one is data and the second one is min value. The min value is always at the top.
3. If 20 is pushed, pop 5 and compare it with 20. Because 20 is bigger, push 20 and 5.
4. If 2 is pushed, pop 5 and compare it with 2. Push 2 and 2 because now 2 is min.
5. If pop is asked, pop min, 2, and pop one more item. The second item will be returned and push 2. So the min value is always maintained at the top and stack will works as it suppose to.
1. Add a data member name e.g. minValue to Stack Data structure, and create a new StackB (it means you need at least 2 stack.
2. every time when you push a data into the stack.
a. if the stack is empty, the minValue = current push data
b. otherwise, compare the current data with minValue,
c. if current data > min Value, push the data to original stack and minValue to StackB
d. if current data < min value, minValue = current data, and push data to both stack and stackB
3. everytime when you pop a data, please pop 2 stacks together.
4. when you want to get the min value, please get top data of stackB
p.s: the data member minValue many not be necessary.
we can do it with just one stack and any temporary variable storing the stack top.i will explain by example.
1.let the stack be empty.now you put 20 into the stack.now 20 is the minvalue.
2.now the next value entering the stack is 5.now pop the value in the stack & assign it to temporary variable p ,if p<5 ,push 5 onto the stack and then p also.
if p>5 ,push p onto the stack and then 5 also.
here p=20 so 5 is pushed onto the stack .
3.thus we can retain the minvalue on the stack top.so it can retrieved in constant time.
i think raghu is saying correct.we have to modify stack the stack so that it gives min value in constant time.every time when we push the value in stack we have to check it is less than min value then simply push into stack
if not less than then pop min value from stack,push other value in it and then push min value on the top of stack.
at every time we will have min value in top of the stack, so we can get min value in constant time....
correct if i am wrong.
suppose you popped the the element, then you will pop out the minimum element, and your min_var is still pointing to the popped out min element, now if i ask for min element it will return the min_var value which is actually wrong.
And tell me how its retain the property of stack, i.e LIFO.
If you are always pushing the min element at the TOP .. ?
perhaps i understood that only in one time we have to get min element from aray.but i think every time we pop a element and that value should b min value remaining element in stack... SO MY ANS R WRONG
read Gayle's book for the right answer lol
- sb December 23, 2011