Angesichts einer Situation, wie man sich für eine Datenstruktur entscheidet?

Question

Ich bereite mich auf technische Interviews vor und habe mich meist mit Fragen konfrontiert, die situationsbezogen sind. Oft ist die Situation ein großer Datensatz und ich werde gefragt, welche die optimale Datenstruktur ist.

Ich kenne die meisten Datenstrukturen, deren Implementierung und Leistung. Aber ich bin in gegebenen Situationen in ein Dilemma geraten und bauentscheidend.

Suchen nach Schritten/Algorithmus in einer bestimmten Situation zu folgen, die mir helfen können, die optimale Datenstruktur innerhalb des Zeitraums des Interviews zu erreichen.

Answer 1

• Beginnen Sie mit gemeinsamen Datenstrukturen. Kann das Problem effizient mit Arrays, Hashtables, Listen oder Bäumen gelöst werden (oder einer einfachen Kombination von ihnen, beispielsweise einem Array von Arbeitstischen oder Ähnlichem)?

• Wenn mehrere Optionen vorhanden sind, wiederholen Sie einfach die Laufzeiten für allgemeine Operationen. Typischerweise ist eine Datenstruktur ein eindeutiger Gewinner in dem für das Interview eingerichteten Szenario. Wenn nicht, teilen Sie dem Interviewer Ihre Ergebnisse mit, z. "A braucht O (n^2), um zu bauen, aber dann können Abfragen in O (1) behandelt werden, während für B Build- und Abfragezeit beide O (n) sind. Für die einmalige Verwendung würde ich B verwenden. sonst A ". Der Platzverbrauch könnte in einigen Fällen ebenfalls relevant sein.

• Hochspezialisierte Datenstrukturen (z. B. Präfixbäume, auch bekannt als "Trie") sind oft: hochspezialisiert für einen speziellen Fall. Der Interviewer sollte in der Regel mehr daran interessiert sein, nützliche Dinge aus einer bestehenden allgemeinen Bibliothek zu erstellen - im Gegensatz dazu, alle Arten von exotischen Datenstrukturen zu kennen, die möglicherweise nicht viel realen Gebrauch machen. Das heißt, zusätzliches Wissen tut nie weh, sei einfach darauf vorbereitet, Vor- und Nachteile von dem zu besprechen, was du erwähnst (der Interviewer kann prüfen, ob du nur "Namen fallen lässt").

Answer 2

Es hängt davon ab, welche Operationen Sie effizient unterstützen müssen.

Beginnen wir mit dem einfachsten Beispiel - Sie haben eine große Liste von Elementen und Sie müssen das gegebene Element finden. Lässt verschiedene Kandidaten in Betracht ziehen

Sie können sortierten Array verwenden, um ein Element in O (log N) -Zeit mit binärer Suche zu finden. Was, wenn Sie das Einfügen und Löschen gleichzeitig unterstützen möchten? Das Einfügen eines Elements in ein sortiertes Array dauert im schlimmsten Fall O (n) Zeit. (Denken Sie daran, am Anfang ein Element hinzuzufügen. Sie müssen alle Elemente um eine Stelle nach rechts verschieben). Jetzt kommt hier binäre Suchbäume (BST). Sie können Einfügen, Löschen und Suchen nach einem Element in O (log N) -Zeit unterstützen.

Jetzt müssen Sie zwei Operationen unterstützen, nämlich Minimum und Maximum zu finden. Im ersten Fall gibt es nur das erste und das letzte Element zurück und daher ist die Komplexität O (1). Angenommen, der BST ist ein ausgewogener wie Rot-Schwarz-Baum oder AVL-Baum, das Finden von Min und Max benötigt O (log N) Zeit. Betrachten Sie eine andere Situation, in der Sie die Statistik der k-ten Reihenfolge zurückgeben müssen. Auch hier gewinnt das sortierte Array. Wie Sie sehen können, gibt es einen Kompromiss und es hängt wirklich von dem Problem ab, das Sie erhalten.

Nehmen wir ein anderes Beispiel. Sie erhalten ein Diagramm mit V-Ecken und E-Kanten, und Sie müssen die Anzahl der verbundenen Komponenten in der Grafik finden. Es kann in O (V + E) -Zeit unter Verwendung der ersten Tiefensuche (unter Annahme einer Adjazenzliste-Darstellung) durchgeführt werden. Betrachten Sie eine andere Situation, in der Kanten inkrementell hinzugefügt werden und die Anzahl der verbundenen Komponenten zu jedem Zeitpunkt des Prozesses abgefragt werden kann.In dieser Situation kann Disjoint Set Union Datenstruktur mit Rang- und Pfadkompressionsheuristiken verwendet werden, und es ist extrem schnell für diese Situation.

Ein weiteres Beispiel - Sie brauchen Bereich Updates zu unterstützen, effizient Summe einer Sub-Array zu finden und keine neuen Elemente in die Array einfügen. Wenn Sie ein Array von N Elementen und Q-Abfragen haben, gibt es zwei Möglichkeiten. Wenn Bereichssummenabfragen nur nach "allen" Aktualisierungsoperationen kommen, die Q 'in der Nummer sind. Dann können Sie das Array in O (N + Q ') Zeit vorverarbeiten und jede Abfrage in O (1) Zeit beantworten (Speichere Präfix Summen). Was passiert, wenn eine solche Order nicht durchgesetzt wird? Sie können dafür den Segmentbaum mit Lazy-Propagation verwenden. Es kann in O (N log N) -Zeit eingebaut werden und jede Abfrage kann in O (log N) -Zeit durchgeführt werden. Sie benötigen also insgesamt O ((N + Q) log N) Zeit. Auch wenn das Einfügen und Löschen zusammen mit all diesen Operationen unterstützt wird? Sie können eine Datenstruktur mit der Bezeichnung Treap verwenden, die eine probabilistische Datenstruktur darstellt, und alle diese Operationen können in O (log N) -Zeit ausgeführt werden. (Mit implizitem Treap).

Hinweis:Die Konstante weggelassen wird, während Notation Big Oh. Einige von ihnen haben große Konstante in ihrer Komplexität versteckt.