Twitter Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Good point but one thing I think need extra attention is that the minStack need to have a push_back operation if (e<=minStack.back()) as this can ensure consistency when you pop if the current min can be more than one.
Hi, can a push_back work here? I do not think so. Consider the sequence: 3, 1, 4, 1. When you pop the top 1, you will have no idea whether there will be another 1 inside the stack. Thus I suggest when stack.push(num), if(num<=minStack.peek()), minStack.push(num).
Correct me if I am wrong.
I could think of following quickly.. pls verify..
With the help of recursion, we should able to find the minimum using single stack. I have written the pseudo code below. It's two step process.
In the first step, find the minimum.
In the second step, delete the min which was found in the first step.. i.e we don't push back the minimum..
find_min(stack s, int *min)
{
if (empty(s)) return;
ele = pop(s);
find_min(s);
if (ele < *min)
*min = ele;
push(ele);
}
delete_min(stack s, int min)
{
if (empty(s)) return;
ele = pop(s);
find_min(s);
if (ele != *min)
push(ele);
}
So you have to think about the complexity of the function find_min and how often does it get called. If you didnt realize it, its very expensive to do find_min upon every push and pop operation.
You can make use of a temp variable where you store the topmost element of the stack initially.then go on popping the elements of the stack one by one into another stack and compare it with the temp,if it is smaller than the temp,copy its value to temp.finally,pop the elements of the temporary stack to the initial stack.And you will be left with the minimum value in temp variable.
import random
class MinStack:
stack=[]
minTrack=[]
def pop(self):
if(len(self.stack)==0):
return None
popped=self.stack.pop()
if(popped==self.minTrack[-1]):
self.minTrack.pop()
return popped
def push(self, value):
if(len(self.minTrack)==0 or self.minTrack[-1]>=value):
self.minTrack.append(value)
self.stack.append(value)
def show(self):
print self.stack
def min(self):
if (len(self.minTrack)>0):
return self.minTrack[-1]
ms=MinStack()
for i in range(10):
ms.push(random.randint(0,100))
ms.show()
print ms.min()
for i in range(10):
ms.pop()
ms.show()
print ms.min()
public class StackGetMin {
private static final int MAX_SIZE = 100;
int[] stack = new int [MAX_SIZE];
int[] stackMin = new int [MAX_SIZE];
int min = Integer.MAX_VALUE;
int pos = -1;
void push(int value) {
if (pos > (MAX_SIZE-1)) return;
pos++;
stack[pos] = value;
if (value < min) min = value;
stackMin[pos] = min;
}
int pop() {
if (pos<0) return Integer.MIN_VALUE;
int popped = stack[pos];
stack[pos] = 0;
stackMin[pos] = 0;
pos--;
return popped;
}
int getMin() {
return stackMin[pos];
}
make each node in the stack have two members, say two ints
int data;
int min_data;
when pushing data into the stack, check min_data
void getmin(stack){
return stack->min_data;
}
void push(stack_t *stack, int new_data){
int old_min = getmin(stack);
int new_min = old_min > new_data ? new_data : old_min;
insert(stack, new_data, new_min);
}
import java.util.*;
class stacks{
int maxsize;
int[] stackArr;
int top=-1;
Stack<Integer> minStack;
stacks(int x){
maxsize=x;
stackArr=new int[x];
top=-1;
minStack = new Stack<Integer>();
}
public void push(int p){
if(maxsize==top){
System.out.println("Stack Overflow");
}
else{
stackArr[++top]=p;
if(p<=getMin()){
minStack.push(p);
}
}
}
public int pop(){
int ret=0;
if(top==-1){
System.out.println("Stack Underflow");
}
else{
ret = stackArr[top--];
if(ret==getMin()){
minStack.pop();
}
}
return ret;
}
public int getMin(){
if(minStack.isEmpty()){
return Integer.MAX_VALUE;
}else{
return minStack.peek();
}
}
}
public class stacky {
public static void main (String[] args){
stacks s = new stacks(5);
s.push(5);
s.push(4);
s.push(2);
s.push(8);
s.push(1);
s.pop();
System.out.println("Min is: "+s.getMin());
}
}
Design simple stack with one variable called min to track variable. I am supposing we dont need deletemin functionality
Not exactly right. If you pop one element which also happens to be minimum, then calling min() would give you a wrong answer. Imagine this stack:s = 7 | 8 | 3. s.min() returns 3. s.pop(); s.min() should return 7.
To achieve this, you keep the track of min (or max) in the node structure. That will give you this: s[7].min = 7 (the min when 7 is pushed), s[8].min = 7 (min when 8 is pushed), s[3].min = 3 (min when 3 is pushed.
just a thought on this:
node can have an extra value as min.
Now, first node will have its value as min when second node come; compare it with the current node in Stack and see which value is less.
Add the new node in the stack and update the min variable of this current top of the stack with the min value.
Keep going like this. let me know if I am mistaken somewhere. The only extra cost I see is to have an extra field in the node and that way we are modifying the node data structure.
take a second stack which will keep the minimum till now and if new minimum comes it will be pushed in the stack, as example ----
- Anonymous March 08, 2012suppose number are coming in order 7,8,9,6,15,12,10,8,3,6,1
then min stack will be , 7,6,3,1.