Amazon Interview Question: Implement a Min Stack

[465 views]


Amazon Interview Question: Design a MinStack


Design a stack that supports operations:- push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.


Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

Initial takes on the question

The question asks us to create a stack which can support the following operations:
  1. push: Insert an element into the stack
  2. pop: Remove an element from the stack
  3. getMin: Display the smallest element in the current stack.
  4. getTop: Display the topmost element in the current stack

What do we know?

  • A Stack data structure follows the LAST IN FIRST OUT or the LIFO methodology
  • By virtue of which, the element that got inserted first is the element that will come out at last!
  • A Traditional stack supports the push,pop,peek operations to implement the first three requirements.
  • But to attain the minimum element at all times we need to make our own data structure and this is what this challange is all about.


Thinking about keeping a globalMinimum at all times sounds good but in reality, is not useful.
The moment we pop out the globalMinimum from the stack, we will be in no place to tell in Constant time that which is the smallest one.

Core idea

The idea is to use Two stacks! It might not be all that intuitive but makes a lot of sense when you see how it operates.
At all times we will maintain a parallel extra stack which will account for the minimum element anytime it is asked for.
Amazon Interview Question: Implement a Min Stack.

Let's see how each of these operations will pan out using this idea:

1. Push into the stack:

We make a simple append for the actual stack and the minStack, we will append the minimum minStack's top and the current element.
What this does is that it allows us to keep track of the minimum element at all times!

2. Pop out of stack:

This is a simple pop operation for both actual stack and minStack because we are simply reducing the height of stacks by one level, so we don't need the minimum value at that level.
Amazon Interview Question: Implement a Min Stack.
Amazon Interview Question: Implement a Min Stack.

3. getTop:

Geting the top element in obvious ways corresponds to knowing the actual top element, hence we just use the actual stack and display the top most guy.

4. getMin:

Getting the minimm element at any level, is plain simple now that we have our minStack ready all times! Whenever we are asked to tell the current minimm element, we can easily tell it by looking at the top of the minStack.


Pop opeations are done at places denoted by red arrow in the diagram below and getMin is denoted by green arrow
Amazon Interview Question: Implement a Min Stack.

Now instead of using two stacks, keeping a tuple within a single stack will also create the exact same effect.
Looks a lot more cleaner this way!
The example given at the beginning will make sense now:
Amazon Interview Question: Implement a Min Stack. Amazon Interview Question: Implement a Min Stack.

Implementation in Python for the minStack class

class MinStack: def __init__(self): self.stack = [(-1, float('inf'))] def push(self, x): self.stack.append([x, min(x, self.stack[-1][1])]) def pop(self): if len(self.stack) > 1: self.stack.pop() def top(self): if len(self.stack) == 1: return None return self.stack[-1][0] def getMin(self): return self.stack[-1][1]
        

Struggling to Understand Algorithm and Flowchart? Try our Notes



Want to Test Your Knowledge on Algorithm and Flowchart?



Comments



Recommended Deals End in



Search
Online Games
Play 2048 Game Online and Relax.
Play 2048 Game Online

Search Tags