Create a stack of numbers where the maximum number is always known.

Question

Interview Candidate · Accepted Answer

To Job Seeker:

The basic idea is that when a new number is being pushed onto the stack, you need to see if that number is greater than or equal to the current top of the maximums-stack. If it is, you push the number onto maximums-stack as well. 

Also, when pop is called, you look to see if the number being popped is equal to the number on the top of the maximums-stack. If it it, pop that stack as well.

Dr Zhang · Answer

sorry, typo
while(top>p)

jobSeeker · Answer

I was asked of this question as well.  I not sure how to implment a second stack in a way that the max number is always on top.

Dr Zhang · Answer

maintain a sorted stack, the insert would look like

insert(int p,stack s){
   stack large;
   int top = s.peek();
   while(top>s){
       large.push(s.pop());
       top = s.peek();
   }
  s.push(p);
  while(!large.empty()){
     s.push(large.pop());
   }
}

jobSeeker · Answer

I was asked of this question as well.  I not sure how to implment a second stack in a way that the max number is always on top.

Anónimo · Answer

Create a separate stack for the maximums.

rands · Answer

just saw this, i think u can just map your number into an object, that has both the maximum number, and the last number that you've pushed in

just peek the stack before you push, compare the peek'd value 'vs' your new pushed number, then replace or update the max number as you see fit?

if you're only allowed to push numbers into your stack, just push your number in the stack more than once (at-least three times) indicating that every value that you put in is a sequence of 2 numbers, and so, push another one (the 3rd, which will always be your maximum number)

so on every 3 pushes, you've stored the maximum value, then everytime you push something in,  just peek the last 3 values in the stack, knowing that the 2nd and 3rd value was probably the number you pushed in, and the first 1 was the max value

it's funny

Anónimo · Answer

Sort the array so that the numbers are in descending order this way you know for sure the first element is the maximum number.

Aditya Singh · Answer

Maintain your Stack ADT like this:

class Node {
    T data;
    T max;
    Node next;
}

class Stack {
    Node top;
    push(T value) {
        
    }
}

Aditya Singh · Answer

Maintain your Stack ADT like this:

class Node {
    T data;
    T max;
    Node next;
}

class Stack {
    Node top;

    void push(T value) {
         Node node = new Node();
         node.value = value;
        if(top == null) {
            node.max = value;
        } else {
            node.max = value.compareTo(top.max) > 1 ? value : top.max;
        }
         node.next = top;
        top = node;
    }
 
    T pop() {
        if(top == null) {
            return null;
        }
        T val = top.val;
        top = top.next;
        return val;
    }

    T max() {
        return top == null ? null : top.max;
    }
}



public static void main(String[] args) {
    Stack stack = new Stack();
    stack.push(3);
    stack.push(2);
    stack.push(5);

    System.out.println(stack.max()); // 5
    System.out.println(stack.pop()); // 5
    System.out.println(stack.max()); // 3
    System.out.println(stack.pop()); // 2
    System.out.println(stack.max()); // 3
    System.out.println(stack.pop()); // 3
}

Google

Pregunta de entrevista de Google

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo