Custom data structure for push, pop and finding a minimum

Question

I was just asked a question with company A as follows:

Question: Create a data structure in which you have 3 operations, click, pop and find the minimum. You must perform all 3 operations at a constant time.

My answer . I would use a linked list in which I can do insertion and deletion at a constant time, and I would use additional memory to keep the minimum.

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

What would you tell him?

Answer 1

What if you make a linked list, as you said, but also keep 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.

For example ... Suppose you have data: 3, 6, 4, 2, 7, 1. Then it will look like

value | min

3 | 3 → 6 | 3 → 4 | 3 → 2 | 2 → 7 | 2 → 1 | 1

This will keep track of the minutes when adding / removing items.

EDIT: I mentioned going back, it would be something like this: 1 | 1 → 7 | 2 → 2 | 2 → 4 | 3 → 6 | 3 → 3 | 3 Then you do not need a footer.

Answer 2

Minimum Stack Question - http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Practice_Questions_Person_A.pdf

From PDF:

Question: minimum stack

Describe the stack data structure that supports push, pop, and find minimum operations. Find Min returns the smallest item on the stack.

Good answer: save two stacks, one of which contains all the elements in the stack and one of them is a stack of minima. To click an item, click it on the first stack. Check if it is smaller than the top element in the second stack; if so, then push this onto the second stack. To place an item, pull it from the first stack. If this is the top element of the second stack, pull it out of the second stack. To find the minimal element, just return the element at the top of the second stack. Each operation takes time O (1).

Answer 3

Let each node keep a different reference to the previously smallest element. That way, when you type the smallest item, you can restore the smallest previously. Since you can only click and place, this will be the correct node.

Answer 4

Here is the C code that 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)); } 

Answer 5

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