Пользовательская структура данных для push, pop и поиска минимума

Question

Мне только что задали вопрос об интервью с компанией А следующим образом:

Вопрос: Создайте структуру данных, в которой у вас есть 3 операции, нажмите, нажмите и найдите минимум. Вы должны выполнять все 3 операции в постоянное время.

Мой ответ : Я бы использовал связанный список, в котором я мог бы выполнять вставку и удаление в постоянное время, и я использовал бы дополнительную память для хранения минимума.

Он придумал второй вопрос, в котором говорилось: если вы выдвинете минимум, как вы найдете второй минимум? снова в постоянном времени.

Что бы вы ему сказали?

Answer 1

Вопрос минимального стека - http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Practice_Questions_Person_A.pdf

Из PDF:

Вопрос: Минимальный стек

Опишите структуру данных стека, которая поддерживает «push», «pop» и «find минимум» операции. «Найти минимум» возвращает наименьший элемент в стеке.

Хороший ответ: Храните две стопки, одна из которых содержит все предметы в стопке и один из которых является стеком минимумов. Чтобы вставить элемент, нажмите на первый стек. Проверьте, меньше ли он верхнего элемента во втором стеке; если это так, нажмите это на второй стек. Чтобы вытолкнуть предмет, вытолкните его из первого стека. Если это вершина элемент второго стека, вытолкните его из второго стека. Чтобы найти минимум элемент, просто верните элемент в верхней части второго стека. Каждая операция занимает O (1) раз.

Answer 2

Что если вы сделаете связанный список, как вы сказали, но также сохраните текущее минимальное значение.Когда вы добавляете новый номер, он просматривает предыдущий мин и меняет текущий мин на текущее значение, если текущее значение ниже.

Например. Предположим, у вас есть данные: 3, 6, 4, 2, 7, 1. Тогда вот как будет выглядеть список

value | min

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

Это будет отслеживать минуты, когда вы добавляете / удаляете элементы.

РЕДАКТИРОВАТЬ: я упоминал, что в обратном направлении это будет примерно так: 1 |1 -> 7 | 2 -> 2 | 2 -> 4 | 3 -> 6 | 3 -> 3 | 3 Тогда вам не понадобится «нижний колонтитул».

Answer 3

Пусть каждый узел сохраняет другую ссылку на ранее наименьший элемент.Таким образом, когда вы выталкиваете самый маленький предмет, вы можете восстановить ранее самый маленький.Поскольку вы можете только нажать и выдвинуть, это будет правильный узел.

Answer 4

Вот код C, который реализует вышеуказанный алгоритм, заданный Брайсом Седшлавом:

#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

Это заставит вас взбеситься - http://algods -cracker.blogspot.in / 2011/09 / design-data-structure-which-support.html