Interviewing for Application Engineer at Google in Sunnyvale.

The interview started with implementing a stack that supports push(), pop() and min() in O(1)
This was fairly easy as I had already practiced the question.
https://leetcode.com/problems/min-stack

Next question:

Add a max() and popMax() method.

This one's pretty easy too.
https://leetcode.com/problems/max-stack/

public class GoogleInterview {

    Stack<Integer> stack;
    Stack<Integer> min;
    Stack<Integer> max;

    GoogleInterview() {
        stack = min = max = new Stack<>();
    }

    void push(int data) {
        stack.push(data);

        if (min.size() == 0 || min.peek() >= data) {
            min.push(data);
        }

        if (max.size() == 0 || max.peek() <= data) {
            max.push(data);
        }
    }

    int pop() throws StackEmptyException {
        if (stack.isEmpty()) {
            throw new StackEmptyException();
        }

        int data = stack.pop();
        if (data <= min.peek()) {
            min.pop();
        }

        if (data >= max.peek()) {
            max.pop();
        }

        return data;
    }

    int popMax() throws StackEmptyException {
        if (max.isEmpty()) {
            throw new StackEmptyException();
        }

        int maxData = max.peek();
        Stack<Integer> temp = new Stack<>();

        while (stack.peek() != maxData) {
            temp.push(stack.pop());
        }

        stack.pop();
		max.pop();

        while (!temp.isEmpty()) {
            push(temp.pop());
        }

        return maxData;
    }

    int max() throws StackEmptyException {
        return max.peek();
    }


    int min() throws StackEmptyException {
        if (min.isEmpty()) {
            throw new StackEmptyException();
        }

        return min.peek();
    }

}

Next question:

How will you implement an avg() method?

Me:- Keep a running sum of the stack everytime we do a push() and subtract whenever we pop() from the stack. We can always get the size by calling stack.size(). The average, then, is just sum/stack.size() and can be done in O(1).

Follow up:
You are doing a lot of operations during push() and pop(), How will you keep your code clean?
Me:- I will create a template version of each method and add hook methods pre() and post() inside every method and move any extra code in there. Something like

void push(int data){
	beforePush(data);
	stack.push(data);
	afterPush(data);
}

Final question:

How can you find the most frequent element in the stack? Calculate mode()

I think its this one
https://leetcode.com/problems/maximum-frequency-stack/
Me:- I will use a HashMap() to keep track of count of elements in the stack and another variable to keep track of the maximum count that there is in the hashmap. Whenever I call the mode() method, I will get the element corresponding to max count. But the solution is O(n).

Follow up:
How will you do it in O(1)?
I think we can do it in O(1).
By the time we could discuss this, we ran out of time.
Him:- "Do you have any questions for me?"
I asked about the job and about the team.

Code editor:- Google docs

Waiting for response.