Yahoo Interview Question
Country: India
maintain 2 stacks
let the elements be 5,6,11,25,34,12,2,3
stack1 stack2
push 5
since 6>5 pop
elements from stack1 to
stack2 until top of stack>curr element.after finding the right position for current element empty stack2 to stack1
we can optimise by using a condition like ...
whenever there is a number going to be pushed check the element on top of stack 2 if only its smaller than that ...push it
else dont push ...
no need to push so many 2 in stack2, if it less than 2, push it, otherwise, do nothing to stack2
Maintain 2 stacks : Normal and minimumNoTracker.
Push: Everytime you push element in Normal stack, check the topmost element in MinimumNoTracker stack and if topmost element is greater than current, push the new element on MinimumNoTracker as well.
Pop: Everytime you pop element from Normal stack, check if it is same as top element of MinimumNoTracker, if yes pop out that number.
Can't we use a sort on initial input if we have them stored. then push them in decreasing order ?
if we already have the problem where we are randomly generating number than putting them in stack, we need to use atleast 3 stacks, and this problem will pretty much looks like Towers of Hanoi problem, and we can use a recursive approach to solve it.
Basically you to create a variable in you stack impl class. Every time to push and entry it should compare to this variable if it is min then store that min number. Also you add getMin an isMin API to get and compare again this number....
why cant we implement min-heap here:
For insertion: insert at the top and min-heapify
For popping: take the top element and min-heapify
Idea is to write a new function pushbubble() using push(), where an element is inserted into its sorted position (situation similar to insertion sort). In that case, the top element will always be the minimum element.
Full working code here : awesomecoder.blogspot.com/2012/08/push-elements-into-stack-pop-should.html
void stack::pushbubble(int elem){
int temp;
if(!this->isempty()){
temp = this->pop();
if(temp > elem){
this->push(temp);
this->push(elem);
} else {
this->pushbubble(elem);
this->push(temp);
}
} else {
this->push(elem);
}
}
Like others have explained, maintain two stacks; one with the value and one with the min value in the other stack.
template <typename T>
class MinStack {
private:
std::stack<T> stack;
std::stack<T> min;
public:
MinStack() {}
void push(T elem) {
stack.push(elem);
min.push(std::min(elem, min.top());
}
std::pair<T, T> popValAndMin() {
T val = stack.top();
T minVal = min.top();
stack.pop();
min.pop();
return std::make_pair(val, minVal);
}
};
- algos August 18, 2012