Custom Data Structure for push, pop and finding minimum

Question

I was just asked an interview question with company A as follows:

Question : Design a data structure in which you have 3 operations, push, pop and find the minimum. You should be doing all the 3 operations in constant time.

My Answer : I would use a linked list in which i can do insertion and removal in constant time and i would use an extra memory to store the minimum.

He came up with a second question saying, if you pop the minimum, how do you find the second minimum? again, in constant time.

What would you tell him?

Answer 1

Minimum stack question - http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Practice_Questions_Person_A.pdf

From the PDF:

Question: Minimum Stack

Describe a stack data structure that supports "push", "pop", and "find minimum" operations. "Find minimum" returns the smallest element in the stack.

Good Answer: Store two stacks, one of which contains all of the items in the stack and one of which is a stack of minima. To push an element, push it onto the first stack. Check whether it is smaller than the top item on the second stack; if so, push it onto the second stack. To pop an item, pop it from the first stack. If it is the top element of the second stack, pop it from the second stack. To find the minimum element, simply return the element on the top of the second stack. Each operation takes O(1) time.