Electronic Arts
3.3 of 5 738 reviews
www.ea.com Redwood City, CA 5000+ Employees

Electronic Arts Software Engineer Interview Question

I interviewed in Philadelphia, PA and was asked:
"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
Add Tags [?]
Answer Flag Question

Part of a Software Engineer Interview Review - one of 191 Electronic Arts Interview Reviews

Answers & Comments

0
of 1
vote
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 Flag Response
2
of 2
votes
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 Flag Response
0
of 0
votes
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 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Electronic Arts interview questions and advice. All interview reviews posted anonymously by Electronic Arts employees and interview candidates.