Interview Question

Software Developer Interview Seattle, WA

implement a stack with a method which can return the

  minimal value in the stack without remove this value.

Interview Answer

4 Answers


implement a stack in which each element record the reference of the minimal value in the previous elements. (or just keep an array to record the reference. can further reduce the space by just recording the decreasing numbers)

Interview Candidate on Feb 21, 2012

I would have approached it like this:

Implement a stack with
- fields: size = size of stack, first = first node, min = min node
- methods/functions: pop, push, peek, min

Then as you insert each element, you update the reference to min.
When you call stack.min() - you get a reference to min

anon on Mar 2, 2012

It's not sufficient just to update the min on push(0.
Need to be able to "backtrack" if pop() removes that min as well.

Whoever on Mar 4, 2012

use a second stack to track the min

Ronny Vikes on Oct 15, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.