Electronic Arts

www.ea.com

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.
Tags:
technical
Answer

Interview Answer

3 Answers

0

struct StackGetMin {
  void push(int x) {
    elements.push(x);
    if (minStack.empty() || x <= minStack.top())
      minStack.push(x);
  }
  bool pop() {
    if (elements.empty()) return false;
    if (elements.top() == minStack.top())
      minStack.pop();
    elements.pop();
    return true;
  }
  bool getMin(int &min) {
    if (minStack.empty()) {
      return false;
    } else {
      min = minStack.top();
      return true;
    }
  }
  stack<int> elements;
  stack<int> minStack;
};

yigit on Oct 25, 2012
3

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
1

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.