Pergunta de entrevista da empresa Flipkart
Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, etc.
Respostas da entrevista
Use two stacks: one to store actual stack elements and other as an auxiliary stack to store minimum values. The idea is to do push() and pop() operations in such a way that the top of auxiliary stack is always the minimum.
how it can be in O(1) all these operations
In that case complexity for push and pop will be o(n) as we are finding and replacing the correct position in the stack containing minimum values, push and pop should also be constant according to question
You have to maintain 2 stack. One is where first latest element is being added second is where the top element is the minimum one.
While adding the element itself you can sort the stack to find perticular position with the help of a temporary stack(third stack)
Below is the code for how can you add element
public void push(int n) {
mainStack.push(n);
if(sortedStack.isEmpty()) {
sortedStack.push(n);
} else {
int topnumber = -1;
if(n= sortedStack.peek() && !sortedStack.isEmpty()) {
topnumber = sortedStack.pop();
temp.push(topnumber);
}
sortedStack.push(n);
while(!temp.isEmpty()) {
topnumber = temp.pop();
sortedStack.push(topnumber);
}
}
}
}
How to get minimum with O(1)
public int getMin() {
int n = -1;
if(!sortedStack.isEmpty()) {
n = sortedStack.pop();
}
return n;
}
This will always return with complexity as O(1)