Adobe Interview Question
Country: India
I didn't understand, why the double push and pop? Why not just a single placeholder for the min value which will updated during Push and Pop by simply comparing with the current element?
Push into stack in sorted order.
As you can modify PUSH and POP.
implement both in sorted fashion.
the top of stack will have minimum element.
so every pop will give you the minimum element.
It can be done using two stacks. One for the element and other for the min.
Else you can modify the structure.
struct node
{
int element;
int min;
}
If even that can't be done. You can always push the minimum element behind the element.
class stack
{
int* array;
int size;
int top;
int min;
stack(int s) { size = s; array = new int[2*s]; top = -1; min = INT_MAX; }
~stack() { delete [] array };
int pop();
void push(int value);
int get_min();
};
int stack::pop()
{
if(top == -1)
return INT_MIN;
else
{
int t = array[top - 1];
top = top - 2;
}
}
int stack::get_min()
{
if(top == -1)
return INT_MIN;
else
return array[top];
}
void stack::push(int value)
{
if(min > value)
min = value;
array[++top] = value;
array[++top] = min;
}
While pushing elements, take a min pointer which always point to the minimum element. Every time you push, compare the coming element with the min element and change the min pointer accordingly. While retrieving the min element, push till you pop the min element.
It is okay. But is there any way that we can do it logarithmic time rather linear time?
This can be done using two stack. One, which is the actual stack and another stack which holds the minimum value seen till now at the top.
class MinStack {
private Stack<Integer> theStack;
private Stack<Integer> minStack;
public MinStack() {
this.theStack = new Stack<Integer>();
this.minStack = new Stack<Integer>();
}
public void push(int value) {
if(value <= this.min()) {
this.minStack.push(value);
}
this.theStack.push(value);
}
public int pop() {
int value = theStack.pop();
if(value == this.min()) {
value = this.minStack.pop();
}
return value;
}
public int min() {
if(this.minStack.size() == 0) {
return Integer.MAX_VALUE;
}
return this.minStack.peek();
}
}
use another stack to keep track of minimum
stack 1 : stack 2:
push 2 push 2
stack 1: stack 2:
push 4 dont do anything
stack 1: stack 2:
push 1 push 1
Stacks contain the following:
stack 1: 1 4 2
stack 2: 1 2
When we pop from S1 check if it is equal to top of stack 2, if so pop from both stacks
- Shock March 22, 2013