Rocket Fuel
3.3 of 5 44 reviews
www.rocketfuel.com Redwood City, CA 500 to 999 Employees

Rocket Fuel Rocket Scientist Interview Question

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

Part of a Rocket Scientist Interview Review - one of 39 Rocket Fuel Interview Reviews

Answers & Comments

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

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


Rocket Fuel – Why Work for Us?

​ ​​​Work for us. Launch your career into orbit.​​ Rocket Fuel is the fast-growing digital advertising technology company in Silicon Valley that has grown quickly from its founding in 2008. The company is a leader in… Full Overview

Provided by employer [?]

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

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