Benutzerdefinierte Datenstruktur für push -, pop-und minimum zu finden

Ich wurde nur gebeten, ein interview-Frage mit der Firma A wie folgt:

Frage : Entwerfen Sie eine Datenstruktur, in der Sie 3 Operationen push, pop und finden Sie das minimum. Sie sollten alles tun, die 3 Operationen in konstanter Zeit.

Meine Antwort : würde ich eine verknüpfte Liste, in der ich tun kann, einfügen und entfernen in konstanter Zeit, und ich würde ein extra Speicher das minimum.

Er kam mit einer zweiten Frage sagen, dass, wenn Sie pop die minimale, wie finden Sie das zweite minimum? wieder, in konstanter Zeit.

Was würden Sie ihm sagen?

InformationsquelleAutor DarthVader | 2011-05-23
  1. 9

    Was ist, wenn Sie eine verkettete Liste, wie Sie sagte, sondern auch speichern Sie den aktuellen minimum-Wert. Beim hinzufügen einer neuen Nummer, sieht es bei den vorherigen min. - und änderungen der aktuellen min, um den aktuellen Wert, wenn der aktuelle Wert niedriger ist.

    E. g... Übernehmen Sie die Daten auch haben: 3, 6, 4, 2, 7, 1. Dann ist das, was die Liste würde wie folgt Aussehen

    Wert|min

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

    Dass merken die Minuten, wie Sie Elemente hinzufügen/entfernen.

    BEARBEITEN:
    Ich erwähnte Rückschritt, es wäre so etwas wie dieses:
    1/1 -> 7/2 -> 2/2 -> 4/3 -> 6/3 -> 3/3
    Dann sind Sie wouln ' T müssen den "footer".

    • Gewährt, müssen Sie ein root-Knoten und ein Knoten bezeichnet als "Fußzeile" und so können am Ende in O(1)
    • Oder Sie könnte rückwärts gehen mit es und fügen Sie die Dinge auf der Vorder-und ändern Sie das root-Knoten jeder einfügen... das würde auch funktionieren
    • aber wenn Sie entfernen 1 Sie müssen aktualisieren Sie alle Elemente in der Liste, so dass Ihre pop Betrieb ist nicht konstant
    • Aber man kann nicht einfach "update" 2... Sie können nur einfügen und pop. Es sei denn, ich bin es falsch verstehen
    • Siedschlaw hast du Recht, aber in diesem Fall, die Anzahl, die Sie speichern ist nicht das minimum nicht mehr richtig?
    • Sicher, es ist. Zumindest auf die aktuellen Knoten-position sowieso. Wie entfernen Sie den minimalen Knoten den nächsten Knoten wird das 2. niedrigste minimum, und so weiter.
    • Siedschlaw doh, ich vergaß, dass Sie nur push und pop
    • dies ist korrekt.

    InformationsquelleAutor Bryce Siedschlaw
  2. 10

    Minimale stack-Frage - http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Practice_Questions_Person_A.pdf

    Aus der PDF-Datei:

    Frage: Mindest-Stack

    Beschreiben eine stack-Datenstruktur, unterstützt "push" und "pop", und "minimum"
    Operationen. "Find minimum" gibt das kleinste element im stack.

    Gute Antwort: Speichern Sie zwei Stapel, von denen der eine enthält alle Elemente, die im stack
    und einer von denen ist ein Stapel von minima. Schieben Sie ein element, schieben Sie es auf den ersten
    stack. Prüfen Sie, ob es kleiner ist als das oberste Element auf dem zweiten Stapel; wenn dem so ist, drücken Sie
    auf dem zweiten Stapel. Pop ein Element, pop es aus dem ersten Stapel. Wenn es die top
    element des zweiten stack, pop es aus dem zweiten Stapel. Zu finden, die minimale
    element, schicken Sie einfach das element an der Oberseite des zweiten stack. Jeder Betrieb
    dauert O(1) Zeit.

    • Dies setzt Voraus, gibt es keine Duplikate, sondern Anpassung zu ermöglichen, Sie bedeutet nur den Austausch "kleiner" mit "kleiner oder gleich".
    • Mischel mit ein: Wenn das der Fall ist, dann müssen Sie nicht sorgen zu machen, weil Sie müssen entfernen Sie die beiden 4 und 3 vor, Sie können loszuwerden 1. Dies bedeutet, dass die minima-stack enthält den minimalen Wert in der Liste
    • haben Sie Lesen die Fragen in der pdf-Datei? es doenst sagen konstanter Zeit, Sie es tun können, mit linearer Zeit mit Hilfe einer Liste oder durch min-heap-u kann sogar mit in logn
    • Ja, habe ich. Die Frage fordert Sie auf, bauen eine Datenstruktur mit Operationen push, pop, und finden min. Ihre Lösung ist für alle drei Operationen in konstanter Zeit.
    InformationsquelleAutor Ryan Reeves
  3. 4

    Lassen, jeder Knoten halten ein Verweis auf die bisher kleinste Element. Also, wenn Sie aus dem pop-kleinste Element, das Sie wiederherstellen können, die bisher kleinste. Da kann man nur push-und pop-es wird der richtige Knoten.

    • Ich denke du und ich reden über die gleiche Sache, ja?
    • Ich denke so..
    InformationsquelleAutor Ishtar
  4. 3

    Hier ist der C-code die Implementierung des oben beschriebenen Algorithmus gegeben, von 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));
}
    InformationsquelleAutor praveenak
Schreibe einen Kommentar