Electronic Arts Interview Question: Given a stack containing valu... | Glassdoor

Find your next job here

Interview Question

Software Engineer Interview Philadelphia, PA

Given a stack containing values, implement min() operation

  to find minimum of all the values in O(1) time. Push() and Pop() should run in O(1) as well.

Interview Answer

3 Answers


struct StackGetMin {
  void push(int x) {
    if (minStack.empty() || x elements;
  stack minStack;

yigit on Oct 25, 2012

To retrieve the current minimum, just return the top element from minimum stack.

This solution suggests using an extra stack to keep tracking of the min. value

Each time you perform a push operation, check if the pushed element is a new minimum. If it is, push it to the minimum stack too.

When you perform a pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the minimum stack too.

yigit on Oct 25, 2012

The question is on CCI. Actually you are not given a stack that already contains numbers. You are asked to design a stack that can maintain metadata while user pushing data into it so that the stack can provide min information in constant time.

Anonymous on Feb 8, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.