Rocket Fuel

www.rocketfuel.com
Employer Engaged

Interview Question

Rocket Scientist Interview Redwood City, CA

How to maintain a stack such that the minimum element of

  all the elements seen so far can be retrieved in constant time? O(1)
Tags:
problem solving
Answer

Interview Answer

1 Answer

0

The answer is better explained on stackoverflow.com, here's the link
http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1
based on that I did write a code, but haven't checked it for extreme cases

import java.util.Arrays;
import java.util.Stack;

public class test2 {

    static Stack<Integer> stack=new Stack<Integer>();
    static Stack<Integer> min_stack=new Stack<Integer>();

public static void main(String args[])
{

    push(5);
    push(1);
    push(3);
    push(2);
    push(1);
    push(0);
    push(3);

    System.out.println("Min in start ="+ getmin());
    System.out.println("Popped "+pop());
    System.out.println("Popped "+pop());
    System.out.println("Popped "+pop());
    System.out.println("Popped "+pop());
    System.out.println("Popped "+pop());
    System.out.println("Popped "+pop());
    System.out.println("Min now ="+ getmin());
}

 public static int getmin()
 {
     return min_stack.peek();
 }

 public static void push(int item)
 {

     if(min_stack.empty() || item<=min_stack.peek())
     {
         stack.push(item);
         min_stack.push(item);
     }
     else
         stack.push(item);
 }

 public static int pop()
 {
     if(stack.peek()==min_stack.peek())
     {
         min_stack.pop();
         //return stack.pop();

     }
         return stack.pop();
 }

}

Jaskaran Khalsa on Mar 24, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.