Holen Sie sich 100 höchste Zahlen aus einer unendlichen Liste

Einer meiner Freunde wurde diese Interviewfrage gestellt -

"Es gibt einen konstanten Zahlenfluss aus einer unendlichen Liste von Zahlen, aus der Sie eine Datenstruktur erstellen müssen, um die 100 höchsten Zahlen zu einem bestimmten Zeitpunkt zurückzugeben. Angenommen, alle Zahlen sind nur ganze Zahlen."

Dies ist ganz einfach. Sie müssen eine sortierte Liste in absteigender Reihenfolge und einen Titel mit der niedrigsten Nummer in dieser Liste führen. Wenn die neu erhaltene Nummer größer als die niedrigste ist, müssen Sie diese niedrigste Nummer entfernen und die neue Nummer nach Bedarf in die sortierte Liste einfügen.

Dann wurde die Frage erweitert -

"Können Sie sicherstellen, dass die Reihenfolge für die Einfügung O (1) sein sollte? Ist es möglich?"

Selbst wenn Sie eine neue Nummer hinzufügen, um sie aufzulisten und mit einem beliebigen Sortieralgorithmus erneut zu sortieren, ist dies meines Wissens nach am besten O (logn) für Quicksort (glaube ich). Also mein Freund sagte, es sei nicht möglich. Aber er war nicht überzeugt, er bat darum, eine andere Datenstruktur als eine Liste beizubehalten.

Ich dachte an einen ausgeglichenen Binärbaum, aber selbst dort werden Sie die Einfügung mit der Reihenfolge 1 nicht erhalten. Also die gleiche Frage habe ich jetzt auch. Wollte wissen, ob es eine solche Datenstruktur gibt, die das Einfügen in der Reihenfolge 1 für das obige Problem ausführen kann, oder ob dies überhaupt nicht möglich ist.

Angenommen, k ist die Anzahl der höchsten Zahlen, die Sie kennen möchten (100 in Ihrem Beispiel). Dann können Sie eine neue Nummer hinzufügen, in O(k)der auch steht O(1). Weil O(k*g) = O(g) if k is not zero and constant.

Halten Sie die Liste unsortiert. Das Herausfinden, ob eine neue Nummer eingefügt werden soll, dauert länger, aber das Einfügen ist O (1).

Das ist einfach. Die Größe der Liste der Konstanten, also die Sortierzeit der Liste, ist konstant. Eine Operation, die in konstanter Zeit ausgeführt wird, wird als O (1) bezeichnet. Daher ist das Sortieren der Liste für eine Liste mit fester Größe O (1).

Sobald Sie 100 Nummern übergeben haben, sind die maximalen Kosten für die nächste Nummer die Kosten für die Überprüfung, ob die Nummer unter den höchsten 100 Nummern liegt (nennen wir diese CheckTime ), zuzüglich der Kosten für die Eingabe in diesen Satz und das Auswerfen der niedrigste (nennen wir diese EnterTime ), die konstante Zeit ist (zumindest für begrenzte Zahlen), oder O (1) .

Worst = CheckTime + EnterTime

Wenn die Verteilung der Zahlen zufällig ist, sinken die durchschnittlichen Kosten, je mehr Zahlen Sie haben. Beispielsweise ist die Wahrscheinlichkeit, dass Sie die 101. Zahl in die maximale Menge eingeben müssen, 100/101, die Wahrscheinlichkeit für die 1000. Zahl wäre 1/10 und die Wahrscheinlichkeit für die n-te Zahl wäre 100 / n. Daher lautet unsere Gleichung für die durchschnittlichen Kosten:

Average = CheckTime + EnterTime / n

Daher ist, wenn n gegen unendlich geht, nur CheckTime wichtig:

Average = CheckTime

Wenn die Zahlen gebunden sind, ist CheckTime konstant und somit O (1) -Zeit .

Wenn die Zahlen nicht gebunden sind, wächst die Überprüfungszeit mit mehr Zahlen. Theoretisch liegt dies daran, dass Ihre Prüfzeit größer ist, wenn die kleinste Zahl in der maximalen Menge groß genug wird, da Sie mehr Bits berücksichtigen müssen. Das lässt es scheinen, als wäre es etwas höher als die konstante Zeit. Sie könnten jedoch auch argumentieren, dass die Wahrscheinlichkeit, dass sich die nächste Zahl in der höchsten Menge befindet, gegen Null geht, wenn sich n der Unendlichkeit nähert, und daher nähert sich die Wahrscheinlichkeit, dass Sie mehr Bits berücksichtigen müssen, ebenfalls gegen 0, was ein Argument für O (1) wäre. Zeit.

Ich bin nicht positiv, aber mein Bauch sagt, dass es O (log (log (n))) Zeit ist. Dies liegt daran, dass die Wahrscheinlichkeit, dass die niedrigste Zahl zunimmt, logarithmisch ist und die Wahrscheinlichkeit, dass die Anzahl der Bits, die Sie für jede Prüfung berücksichtigen müssen, ebenfalls logarithmisch ist. Ich interessiere mich für andere Völker, da ich nicht wirklich sicher bin ...

Dieser ist einfach, wenn Sie Binary Heap Trees kennen . Binäre Heaps unterstützen das Einfügen in der durchschnittlichen konstanten Zeit O (1). Und geben Ihnen einfachen Zugang zu den ersten x Elementen.

Wenn der Interviewer mit der Frage „Können wir sicherstellen, dass jede eingehende Nummer in konstanter Zeit verarbeitet wird“ wirklich sagen wollte, wie viele bereits darauf hingewiesen haben (siehe z. B. die Antwort von @ duedl0r), lautet die Lösung Ihres Freundes bereits O (1) und Es wäre sogar so, wenn er eine unsortierte Liste oder eine Blasensortierung oder was auch immer verwendet hätte. In diesem Fall ergibt die Frage keinen Sinn, es sei denn, es war eine knifflige Frage oder Sie erinnern sich, dass sie falsch ist.

Ich nehme an, die Frage des Interviewers war aussagekräftig, dass er nicht gefragt hat, wie man etwas zu O (1) macht, was ganz offensichtlich schon so ist.

Da die Komplexität des Fragealgorithmus nur dann sinnvoll ist, wenn die Größe der Eingabe auf unbestimmte Zeit wächst und die einzige Eingabe, die hier wachsen kann, 100 ist - die Listengröße. Ich gehe davon aus, dass die eigentliche Frage lautete: "Können wir sicherstellen, dass Top N O (1) Zeit pro Zahl ausgibt (nicht O (N) wie in der Lösung Ihres Freundes), ist das möglich?".

Das erste, was mir einfällt, ist das Zählen der Sorte, die die Komplexität von O (1) Zeit pro Zahl für das Top-N-Problem für den Preis der Verwendung des O (m) -Raums kauft, wobei m die Länge des Bereichs eingehender Zahlen ist . Also ja, das ist möglich.

Verwenden Sie eine Warteschlange mit minimaler Priorität, die mit einem Fibonacci-Heap implementiert wurde und eine konstante Einfügezeit aufweist:

1. Insert first 100 elements into PQ
2. loop forever
       n = getNextNumber();
       if n > PQ.findMin() then
           PQ.deleteMin()
           PQ.insert(n)

Die Aufgabe besteht eindeutig darin, einen Algorithmus zu finden, der O (1) in der Länge N der erforderlichen Liste von Zahlen ist. Es spielt also keine Rolle, ob Sie die Top-100-Nummer oder die 10000-Nummer benötigen, die Einfügezeit sollte O (1) sein.

Der Trick dabei ist, dass, obwohl diese O (1) -Anforderung für die Listeneinfügung erwähnt wird, die Frage nichts über die Reihenfolge der Suchzeit im gesamten Nummernraum aussagte, aber es stellt sich heraus, dass dies gemacht werden kann. O (1) auch. Die Lösung lautet dann wie folgt:

1. Ordnen Sie eine Hash-Tabelle mit Zahlen für Schlüssel und Paaren verknüpfter Listenzeiger für Werte an. Jedes Zeigerpaar ist der Anfang und das Ende einer verknüpften Listenfolge. Dies ist normalerweise nur ein Element, dann das nächste. Jedes Element in der verknüpften Liste wird neben dem Element mit der nächsthöheren Nummer angezeigt. Die verknüpfte Liste enthält daher die sortierte Folge der erforderlichen Nummern. Notieren Sie sich die niedrigste Nummer.

2. Nimm eine neue Zahl x aus dem Zufallsstrom.

3. Ist es höher als die zuletzt aufgezeichnete niedrigste Zahl? Ja => Schritt 4, Nein => Schritt 2

4. Schlagen Sie die Hash-Tabelle mit der gerade genommenen Nummer. Gibt es einen Eintrag? Ja => Schritt 5. Nein => Nimm eine neue Zahl x-1 und wiederhole diesen Schritt (dies ist eine einfache lineare Suche nach unten, trage mich hier ein, dies kann verbessert werden und ich werde erklären, wie)

5. Fügen Sie mit dem soeben aus der Hash-Tabelle erhaltenen Listenelement die neue Nummer direkt nach dem Element in die verknüpfte Liste ein (und aktualisieren Sie den Hash).

6. Nimm die niedrigste Nummer, die ich aufgezeichnet habe (und entferne sie aus dem Hash / der Liste).

7. Schlagen Sie die Hash-Tabelle mit der gerade genommenen Nummer. Gibt es einen Eintrag? Ja => Schritt 8. Nein => Nimm eine neue Zahl l + 1 und wiederhole diesen Schritt (dies ist eine einfache lineare Suche nach oben)

8. Bei einem positiven Treffer wird die Zahl zur neuen niedrigsten Zahl. Weiter zu Schritt 2

Um doppelte Werte zuzulassen, muss der Hash den Anfang und das Ende der verknüpften Listensequenz von Elementen, die doppelte Werte sind, beibehalten. Durch Hinzufügen oder Entfernen eines Elements zu einer bestimmten Taste wird der angezeigte Bereich vergrößert oder verkleinert.

Der Einsatz hier ist O (1). Die genannten Suchanfragen sind, denke ich, O (durchschnittlicher Unterschied zwischen Zahlen). Die durchschnittliche Differenz erhöht sich mit der Größe des Nummernraums, verringert sich jedoch mit der erforderlichen Länge der Nummernliste.

Die lineare Suchstrategie ist also ziemlich schlecht, wenn der Nummernraum groß ist (z. B. für einen 4-Byte-Int-Typ, 0 bis 2 ^ 32-1) und N = 100. Um dieses Leistungsproblem zu umgehen, können Sie parallele Sätze von Hashtabellen aufbewahren, bei denen die Zahlen auf höhere Beträge (z. B. 1s, 10s, 100s, 1000s) gerundet werden, um geeignete Schlüssel zu erstellen. Auf diese Weise können Sie einen höheren oder niedrigeren Gang einlegen, um die erforderlichen Suchvorgänge schneller durchzuführen. Die Leistung wird dann zu einem O (log numberrange), was meiner Meinung nach konstant ist, also auch zu O (1).

Stellen Sie sich zur Verdeutlichung vor, Sie hätten die Nummer 197 zur Hand. Wenn Sie den 10er-Hash-Tisch treffen, wird er mit '190' auf die nächste Zehn gerundet. Etwas? Nein. Also gehen Sie in 10s runter, bis Sie sagen 120 drücken. Dann können Sie bei 129 in der 1s-Hash-Tabelle beginnen und 128, 127 versuchen, bis Sie etwas treffen. Sie haben nun in der verknüpften Liste die Stelle gefunden, an der die Nummer 197 eingefügt werden soll. Während Sie sie eingeben, müssen Sie auch die 1s-Hashtabelle mit dem Eintrag 197, die 10s-Hashtabelle mit der Nummer 190, die 100s mit 100 usw. aktualisieren. Die meisten Schritte Sie müssen hier immer das 10-fache des Protokolls des Nummernkreises machen.

Ich könnte einige der Details falsch verstanden haben, aber da dies der Programmiereraustausch ist und der Kontext Interviews war, würde ich hoffen, dass die obige Antwort überzeugend genug für diese Situation ist.

BEARBEITEN Ich habe hier einige zusätzliche Details hinzugefügt, um das Schema der parallelen Hashtabelle zu erläutern und um zu erläutern, wie die von mir erwähnten schlechten linearen Suchen durch eine O (1) -Suche ersetzt werden können. Ich habe auch festgestellt, dass es nicht notwendig ist, nach der nächstniedrigeren Nummer zu suchen, da Sie direkt dorthin gelangen können, indem Sie in die Hash-Tabelle mit der niedrigsten Nummer schauen und zum nächsten Element übergehen.

Können wir annehmen, dass die Zahlen einen festen Datentyp haben, wie z. B. Integer? Wenn ja, führen Sie eine Liste aller hinzugefügten Zahlen. Dies ist eine O (1) -Operation.

1. Deklarieren Sie ein Array mit so vielen Elementen wie möglich:
2. Lesen Sie jede Nummer, während sie gestreamt wird.
3. Zählen Sie die Nummer. Ignorieren Sie es, wenn diese Zahl bereits 100-mal vergeben wurde, da Sie sie nie brauchen werden. Dies verhindert, dass Überläufe es unendlich oft zählen.
4. Wiederholen Sie ab Schritt 2.

VB.Net Code:

Const Capacity As Integer = 100

Dim Tally(Integer.MaxValue) As Integer ' Assume all elements = 0
Do
    Value = ReadValue()
    If Tally(Value) < Capacity Then Tally(Value) += 1
Loop

Wenn Sie die Liste zurückschicken, können Sie so lange dauern, wie Sie möchten. Gehen Sie einfach vom Ende der Liste aus und erstellen Sie eine neue Liste mit den höchsten 100 aufgezeichneten Werten. Dies ist eine O (n) -Operation, die jedoch keine Rolle spielt.

Dim List(Capacity) As Integer
Dim ListCount As Integer = 0
Dim Value As Integer = Tally.Length - 1
Dim ValueCount As Integer = 0
Do Until ListCount = List.Length OrElse Value < 0
    If Tally(Value) > ValueCount Then
        List(ListCount) = Value
        ValueCount += 1
        ListCount += 1
    Else
        Value -= 1
        ValueCount = 0
    End If
Loop
Return List

Bearbeiten: In der Tat ist es egal, ob es ein fester Datentyp ist. Da der Speicherverbrauch (oder der Festplattenverbrauch) nicht begrenzt ist, können Sie diese Funktion für eine Reihe positiver Ganzzahlen verwenden.

Einhundert Zahlen lassen sich leicht in einem Array der Größe 100 speichern. Jeder Baum, jede Liste oder jede Menge ist angesichts der anstehenden Aufgabe überfordert.

Wenn die eingehende Nummer höher als die niedrigste (= letzte) im Array ist, führen Sie alle Einträge durch. Wenn Sie die erste gefunden haben, die kleiner ist als Ihre neue Nummer (Sie können dazu ausgefallene Suchanfragen verwenden), durchlaufen Sie den Rest des Arrays und drücken Sie jeden Eintrag "nach unten".

Da Sie die Liste von Anfang an sortiert halten, müssen Sie überhaupt keinen Sortieralgorithmus ausführen. Das ist O (1).

Sie könnten einen binären Max-Heap verwenden. Sie müssten einen Zeiger auf den minimalen Knoten verfolgen (der unbekannt / null sein könnte).

Sie beginnen, indem Sie die ersten 100 Zahlen in den Heap einfügen. Das Maximum wird oben sein. Nachdem dies erledigt ist, werden Sie immer 100 Nummern darin behalten.

Wenn Sie dann eine neue Nummer erhalten:

if(minimumNode == null)
{
    minimumNode = findMinimumNode();
}
if(newNumber > minimumNode.Value)
{
    heap.Remove(minimumNode);
    minimumNode = null;
    heap.Insert(newNumber);
}

Leider findMinimumNodeist O (n) und es fallen einmalig Kosten pro Insert an (aber nicht während des Inserts :). Das Entfernen des Mindestknotens und das Einfügen des neuen Knotens haben im Durchschnitt den Wert O (1), da sie zum unteren Rand des Heaps tendieren.

Wenn Sie einen binären Min-Heap verwenden, befindet sich der Min-Heap ganz oben, was sich hervorragend dazu eignet, den Min-Heap zum Vergleich zu ermitteln. Dies ist jedoch kein Erfolg, wenn Sie den Minimum-Heap durch eine neue Zahl ersetzen müssen, die> min ist. Das liegt daran, dass Sie den min-Knoten (immer O (logN)) entfernen und dann den neuen Knoten einfügen müssen (durchschnittliches O (1)). Sie haben also immer noch O (logN), was besser ist als Max-Heap, aber nicht O (1).

Wenn N konstant ist, haben Sie natürlich immer O (1). :)