Dieses Problem wurde mir in einem Interview gegeben. Wie hätten Sie geantwortet?
Entwerfen Sie eine Datenstruktur, die die folgenden Operationen in O (1) -Zeit bietet:
- einfügen
- entfernen
- enthält
- zufälliges Element erhalten
data-structures
Gildenbesitzer
quelle
quelle
Antworten:
Stellen Sie sich eine Datenstruktur vor, die aus einer Hashtabelle H und einem Array A besteht. Die Hashtabellenschlüssel sind die Elemente in der Datenstruktur, und die Werte sind ihre Positionen im Array.
Da das Array automatisch vergrößert werden muss, wird O (1) amortisiert, um ein Element hinzuzufügen, aber ich denke, das ist in Ordnung.
quelle
O (1) Lookup impliziert eine Hash-Datenstruktur .
Im Vergleich:
quelle
hashtable.get((int)(Math.random()*hashtable.size()));
Das mag Ihnen vielleicht nicht gefallen, weil sie wahrscheinlich nach einer cleveren Lösung suchen, aber manchmal lohnt es sich, an Ihren Waffen festzuhalten ... Eine Hash-Tabelle erfüllt bereits die Anforderungen - wahrscheinlich insgesamt besser als alles andere (wenn auch offensichtlich in amortisierter Konstante) Zeit und mit unterschiedlichen Kompromissen zu anderen Lösungen).
Die Anforderung, die schwierig ist, ist die Auswahl des "zufälligen Elements": In einer Hash-Tabelle müssten Sie nach einem solchen Element suchen oder suchen.
Bei geschlossener Hashing- / offener Adressierung besteht die Wahrscheinlichkeit, dass ein bestimmter Bucket belegt wird
size() / capacity()
. Entscheidend ist jedoch , dass dies durch eine Hash-Tabellen-Implementierung in der Regel in einem konstanten multiplikativen Bereich gehalten wird (z. B. kann die Tabelle um das 1,2-fache größer als ihr aktueller Inhalt gehalten werden bis ~ 10x je nach Leistung / Speicheroptimierung). Dies bedeutet, dass wir im Durchschnitt mit der Suche nach 1,2 bis 10 Eimern rechnen können - völlig unabhängig von der Gesamtgröße des Containers. amortisiertes O (1).Ich kann mir zwei einfache Ansätze vorstellen (und viele weitere fummelige):
Suche linear aus einem zufälligen Eimer
Versuchen Sie es wiederholt mit zufälligen Eimern, bis Sie einen bestückten finden
Keine großartige Lösung, aber dennoch ein besserer Kompromiss als der Speicher- und Leistungsaufwand für die jederzeitige Aufrechterhaltung eines zweiten Indexarrays.
quelle
Die beste Lösung ist wahrscheinlich die Hash-Tabelle + Array, sie ist sehr schnell und deterministisch.
Aber die Antwort mit der niedrigsten Bewertung (verwenden Sie einfach eine Hash-Tabelle!) Ist auch großartig!
Die Leute mögen das vielleicht nicht wegen "möglicher Endlosschleifen", und ich habe gesehen, dass sehr kluge Leute diese Reaktion auch haben, aber es ist falsch! Unendlich unwahrscheinliche Ereignisse passieren einfach nicht .
Angenommen, das gute Verhalten Ihrer Pseudozufallsquelle - das für dieses spezielle Verhalten nicht schwer festzustellen ist - und die Hash-Tabellen sind immer zu mindestens 20% voll, ist dies leicht zu erkennen:
Es wird niemals passieren, dass getRandom () mehr als 1000 Mal versuchen muss. Nur nie . In der Tat beträgt die Wahrscheinlichkeit eines solchen Ereignisses 0,8 ^ 1000, was 10 ^ -97 entspricht. Wir müssten es also 10 ^ 88 Mal wiederholen, um eine Chance in einer Milliarde davon zu haben, die jemals einmal passiert. Selbst wenn dieses Programm auf allen Computern der Menschheit Vollzeit ausgeführt würde, bis die Sonne stirbt, wird dies niemals passieren.
quelle
Für diese Frage werde ich zwei Datenstrukturen verwenden
Schritte :-
Code: -
- Zeitkomplexität O (1). - Raumkomplexität O (N).
quelle
Hier ist eine C # -Lösung für dieses Problem, das ich vor einiger Zeit gefunden habe, als ich dieselbe Frage gestellt habe. Es implementiert Add, Remove, Contains und Random zusammen mit anderen Standard-.NET-Schnittstellen. Nicht, dass Sie es jemals während eines Interviews so detailliert implementieren müssten, aber es ist schön, eine konkrete Lösung zu haben, die Sie sich ansehen können ...
quelle
ArgumentException
mit der Meldung "Ein Element mit demselben Schlüssel wurde bereits hinzugefügt" hinzugefügt wird. wird ausgelöst (aus dem zugrunde liegenden Index-Wörterbuch).Wir können Hashing verwenden, um Operationen in Θ (1) Zeit zu unterstützen.
Einfügen (x) 1) Überprüfen Sie, ob x bereits vorhanden ist, indem Sie eine Hash-Map-Suche durchführen. 2) Wenn nicht vorhanden, fügen Sie es am Ende des Arrays ein. 3) Fügen Sie in der Hash-Tabelle auch x als Schlüssel und den letzten Array-Index als Index hinzu.
remove (x) 1) Überprüfen Sie, ob x vorhanden ist, indem Sie eine Hash-Map-Suche durchführen. 2) Wenn vorhanden, suchen Sie den Index und entfernen Sie ihn aus der Hash-Map. 3) Tauschen Sie das letzte Element mit diesem Element im Array aus und entfernen Sie das letzte Element. Der Austausch erfolgt, da das letzte Element in O (1) -Zeit entfernt werden kann. 4) Aktualisieren Sie den Index des letzten Elements in der Hash-Map.
getRandom () 1) Generiere eine Zufallszahl von 0 bis zum letzten Index. 2) Geben Sie das Array-Element am zufällig generierten Index zurück.
Suche (x) Suchen Sie in der Hash-Map nach x.
quelle
Das ist zwar viel alt, aber da es in C ++ keine Antwort gibt, sind hier meine zwei Cent.
Hier ist ein Teil des Client-Codes, um die Lösung zu testen.
quelle
In C # 3.0 + .NET Framework 4 ist ein Generikum
Dictionary<TKey,TValue>
sogar besser als eine Hashtable, da Sie dieSystem.Linq
Erweiterungsmethode verwenden können,ElementAt()
um in das zugrunde liegende dynamische Array zu indizieren, in dem dieKeyValuePair<TKey,TValue>
Elemente gespeichert sind:Soweit ich weiß, ist eine Hashtabelle (oder deren Dictionary-Nachkommen) jedoch keine echte Lösung für dieses Problem, da Put () nur mit O (1) amortisiert werden kann, nicht mit O (1), da es sich um O (N) handelt ) an der dynamischen Größenänderungsgrenze.
Gibt es eine echte Lösung für dieses Problem? Ich kann mir nur vorstellen, dass Sie O (1) -Operationen erhalten, wenn Sie eine Dictionary / Hashtable-Anfangskapazität angeben, die um eine Größenordnung über dem liegt, was Sie voraussichtlich jemals benötigen, da Sie die Größe nie ändern müssen.
quelle
Ich stimme Anon zu. Mit Ausnahme der letzten Anforderung, bei der ein zufälliges Element mit gleicher Fairness erforderlich ist, können alle anderen Anforderungen nur mit einem einzigen Hash-basierten DS erfüllt werden. Ich werde HashSet dafür in Java wählen. Das Modulo des Hash-Codes eines Elements gibt mir die Indexnummer des zugrunde liegenden Arrays in O (1) -Zeit. Ich kann das zum Hinzufügen, Entfernen und Enthalten von Operationen verwenden.
quelle
Können wir das nicht mit HashSet von Java machen? Es bietet standardmäßig das Einfügen, Löschen und Suchen in O (1). Für getRandom können wir den Iterator von Set verwenden, der sowieso zufälliges Verhalten liefert. Wir können einfach das erste Element aus der Menge iterieren, ohne uns um den Rest der Elemente kümmern zu müssen
quelle
quelle
Warum verwenden wir nicht epoch% arraysize, um zufällige Elemente zu finden? Das Finden der Arraygröße ist O (n), aber die amortisierte Komplexität ist O (1).
quelle
Ich denke, wir können eine doppelte Linkliste mit einer Hash-Tabelle verwenden. Der Schlüssel ist ein Element und der zugehörige Wert ist der Knoten in der doppelten Linkliste.
quelle