Custom Data Structure for push, pop and finding minimum

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?

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.

What if you do a linked list, like you said, but also store the current minimum value. When you add a new number it looks at the previous min and changes the current min to the current value if the current value is lower.

E.g... Assume you have the data: 3, 6, 4, 2, 7, 1. Then this is what the list would look like

value|min

3|3 -> 6|3 -> 4|3 -> 2|2 -> 7|2 -> 1|1

That'll keep track of the mins as you add/remove items.

EDIT: I mentioned going backwards, it would be something like this: 1|1 -> 7|2 -> 2|2 -> 4|3 -> 6|3 -> 3|3 Then you wouln't need the "footer".

Let every node keep another reference to the previously smallest item. So, when you pop the smallest item, you can restore the previously smallest. Because you can only push and pop it will be the correct node.

Here is the C code which implements the above algorithm given by Bryce Siedschlaw:

#include<stdio.h>
#include<stdlib.h>

#define minimumOf(a,b) (a<b) ? a : b;

struct node{
    int data;
    struct node* next;
    int min;
};

void push(struct node **head_ref, int new_data){
    struct node* new_node = (struct node *)malloc(sizeof(struct node));
    new_node->data = new_data;

    if(*head_ref == NULL)
        new_node->min = new_data;
    else
        new_node->min = minimumOf(new_data,(*head_ref)->min);

    new_node->next = *head_ref;
    *head_ref = new_node;
}

int minimum(struct node *head){
    return head->min;
}

int pop(struct node **head_ref){
    int pop_data = (*head_ref)->data;
    (*head_ref) = (*head_ref)->next;
    return pop_data;
}

void printList(node *head){
    while(head != NULL){
        printf("%d->", head->data);
        head = head->next;
    }
    printf("\b\n");
}

int main(){
    struct node* a = NULL;

    push(&a, 100);
    push(&a, 24);
    push(&a, 16);
    push(&a, 19);
    push(&a, 50);
    printList(a);
    printf("Minimum is:%d\n", minimum(a));
    printf("Popped:%d\n",pop(&a));
    printf("Minimum is:%d\n", minimum(a));
    printf("Popped:%d\n",pop(&a));
    printf("Minimum is:%d\n", minimum(a));
    printf("Popped:%d\n",pop(&a));
    printf("Minimum is:%d\n", minimum(a));
    printf("Popped:%d\n",pop(&a));
    printf("Minimum is:%d\n", minimum(a));
}

This will make you go wild - http://algods-cracker.blogspot.in/2011/09/design-data-structure-which-supports.html