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?

So, there ya go. 3 decent answers saying the same thing, implemented in different ways :P — Bryce Siedschlaw, May 23 '11 at 21:55
Possible duplicate: http://stackoverflow.com/questions/4092690/implement-stack-push-pop-and-findmin-in-o1 and http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1 — finnw, May 24 '11 at 00:07
Sorry the link in my close vote is wrong, but this is still a duplicate of 685050 — finnw, May 24 '11 at 00:09

score 10 · Answer 1 · answered May 23 '11 at 21:43

10

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.

answered May 23 '11 at 21:43

Ryan Reeves

10,209
3
42
26

This assumes there are no duplicates, but adapting it to allow them means just replacing “smaller” with “smaller or equal”. – svick May 23 '11 at 21:50
@Jim Mischel: If that's the case, then you won't have to worry because you'll have to remove both 4 and 3 before you can get rid of 1. This means that the minima stack will contain the minimum value in the list – Bryce Siedschlaw May 23 '11 at 21:53
did you read the question in the pdf? it doenst say constant time, you can do it with linear time using a list or using min heap u can even do in logn – DarthVader May 23 '11 at 21:56
3

Yes I did. The question asks you to build a data structure with operations push, pop, and find min. Their solution does all three operations in constant time. – Ryan Reeves May 23 '11 at 22:07

score 9 · Accepted Answer · answered May 23 '11 at 21:39

9

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".

answered May 23 '11 at 21:39

Bryce Siedschlaw

4,136
1
24
36

Granted you'll need to have a root node and a node designated as a "footer" so you can access the end in O(1) – Bryce Siedschlaw May 23 '11 at 21:40
Or you could go backwards with it and add things to the front and change the root node every insert... that would work too – Bryce Siedschlaw May 23 '11 at 21:42
but if you remove 1, you have to update all the elements in the list, so your `pop` operation is not constant – vlad May 23 '11 at 21:44
But you can't just "update" 2... you can only insert and pop. Unless I'm understanding it wrong – Bryce Siedschlaw May 23 '11 at 21:44
@Bryce Siedschlaw you're right, but in that case, the number you store isn't the minimum anymore, right? – vlad May 23 '11 at 21:46
Sure it is. At least at that current node's position anyway. As you remove the minimum nodes, the next nodes will have the 2nd lowest minimum, and so on. – Bryce Siedschlaw May 23 '11 at 21:47
@Bryce Siedschlaw doh, I forgot that you can only `push` and `pop` – vlad May 23 '11 at 21:53

score 4 · Answer 3 · answered May 23 '11 at 21:43

4

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.

answered May 23 '11 at 21:43

Ishtar

11,542
1
25
31

I think you and I are talking about the same thing, yes? – Bryce Siedschlaw May 23 '11 at 21:48

score 3 · Answer 4 · edited Oct 12 '12 at 19:51

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));
}

score -2 · Answer 5 · answered Jul 23 '12 at 22:44

-2

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

answered Jul 23 '12 at 22:44

Karan Bajaj

3,292
2
14
2

Custom Data Structure for push, pop and finding minimum

5 Answers5