Implement the functions for a stack and function getMinimum() all with O(1) complexity.

Question

Sheldon · Accepted Answer

We need two stacks to solve this problem.
For stack 1, it is used to implement the normal push(), pop() and top() functions. And for stack 2, we maintain the minimum element in stack 1 as its top.
We maintain stack 2 in the following way: 
1) While pushing an element into stack 1, we compare this element with the top element in stack 2. If it is smaller, we push this element into stack 2 at the same time. Otherwise, we do nothing.
2) When pop an element out from stack 1, we compare this element with the top element in stack 2. If they are equal, we pop out the top element from stack 2 at the same time. Otherwise, we do nothing.

Harry · Answer

There is a blog discussing this interview question: http://codercareer.blogspot.com/2011/09/no-02-stack-with-function-min.html

szilard · Answer

Sheldon's solution does not work in case the min appears multiple times. Otherwise its good. In order to fix this we also need the number off occurences in the min stack.

Lokesh · Answer

This cant be done. The reason is that if we are to support minimum operation in O(1) time, that would imply that we can sort the stack in O(n) time.. by repeatedly calling min and removing the min element. 
Keep a stack, augmented with a Min heap..., and heapify if the minimum element is being popped off. Also heapify on every insert...

Meta

Question d’entretien chez Meta

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois