Yahoo Interview Question
Software Engineer / Developersnode with two address part one for next node and one for contain address of next min which min to that node value .
This one looks promising. Each node maintains a pointer to the min value. Each time you push, you compare with the min value the top points to and set the appropriate pointer.
Below is an attempt.
/* No error checking done for simplicity */
struct MinStack {
MinStack *next;
MinStack *min;
int value;
}
MinStack *Push(MinStack * stack, int value) {
MinStack *top = (MinStack *)malloc(sizeof(MinStack));
top->value = value;
top->next = stack;
if (stack->min->value <= value) {
top->min = stack->min
}else {
top->min = top;
}
}
MinStack *Pop(MinStack * stack, int *poppedValue) {
*poppedValue = stack->value;
MinStack *top = stack->next;
free(stack);
return top;
}
int Min(MinStack *stack) {
return stack->min->value;
}
Just keep a min variable .. which always checks before pushing in an element and return that element.
If the question meant to say O(n) this is how I would do it:
assuming that we could check if stack is empty
pseudo code without any error checking
find_min(stack)
n = stack.pop()
m = stack.pop()
s = smaller of n and m
if stack is empty
return s
else
stack.push(s)
find_min(stack)
class Stack{
int top;
int[] stack;
MinimumStack miniStack;
// constructor for stack
Stack(int capacity){
top=0;
stack=new int[capacity];
miniStack = new MinimumStack(capacity);
}
boolean isFull(){
return(top==stack.length);
}
public void push(int val){
if(!isFull()){
stack[top++]=val;
miniStack.push(val);
}else{
System.out.println("The stack is full");
}
}
public Object pop(){
if(top!=0){
miniStack.pop(stack[top-1]);
return stack[top--];
}else{
return null;
}
}
public void displayStack(){
for(int i=0;i<top;i++){
System.out.println(stack[i]);
}
}
public void displayMinimum(){
System.out.println("The current minimum is"+miniStack.getMinimum());
}
}
class MinimumStack{
int topMin;
int[] Ministack;
public MinimumStack(int capacity) {
// TODO Auto-generated constructor stub
topMin=0;
Ministack=new int[capacity];
}
public int getMinimum() {
// TODO Auto-generated method stub
if(topMin!=0){
return Ministack[topMin-1];
}
return (Integer)null;
}
boolean isMinStackFull(){
return(topMin==Ministack.length);
}
public void push(int val){
if(!isMinStackFull()){
if(topMin!=0){
if(val<Ministack[topMin-1])
Ministack[topMin++]=val;
}
else{
if(topMin==0)
Ministack[topMin++]=val;
}
}else{
System.out.println("The stack is full");
}
}
public void pop(int val){
if(Ministack[topMin]==val){
int Minval=Ministack[topMin--];
}
}
}
take two stacks.in one stack put the value a/c to requirement,consecuitevily maintain the current min value in 2nd stack.
- ujjwal akash September 17, 2008if u do the pop operation then compare it with 2nd stack top value if equal then also pop the top of 2nd stack .