Die wichtigsten Datenstrukturen, die Sie für Ihr nächstes Coding-Interview kennen sollten

Der Schweizer Informatiker Niklaus Wirth schrieb 1976 ein Buch mit dem Titel Algorithmen + Datenstrukturen = Programme.

Über 40 Jahre später gilt diese Gleichung immer noch. Aus diesem Grund müssen Kandidaten für Softwareentwicklung ihr Verständnis für Datenstrukturen zusammen mit ihren Anwendungen nachweisen.

Bei fast allen Problemen muss der Kandidat ein tiefes Verständnis der Datenstrukturen nachweisen. Es spielt keine Rolle, ob Sie gerade Ihren Abschluss gemacht haben (von einer Universität oder einem Coding Bootcamp) oder über jahrzehntelange Erfahrung verfügen.

In Interviewfragen wird manchmal explizit eine Datenstruktur erwähnt, z. B. „ein binärer Baum gegeben“. In anderen Fällen ist dies implizit, z. B. "Wir möchten die Anzahl der Bücher verfolgen, die jedem Autor zugeordnet sind."

Das Erlernen von Datenstrukturen ist wichtig, auch wenn Sie nur versuchen, Ihren aktuellen Job zu verbessern. Beginnen wir mit dem Verständnis der Grundlagen.

Was ist eine Datenstruktur?

Einfach ausgedrückt ist eine Datenstruktur ein Container, in dem Daten in einem bestimmten Layout gespeichert werden. Dieses „Layout“ ermöglicht es, dass eine Datenstruktur in einigen Vorgängen effizient und in anderen ineffizient ist. Ihr Ziel ist es, Datenstrukturen zu verstehen, damit Sie die Datenstruktur auswählen können, die für das jeweilige Problem am besten geeignet ist.

Warum brauchen wir Datenstrukturen?

Da Datenstrukturen zum Speichern von Daten in organisierter Form verwendet werden und Daten die wichtigste Einheit in der Informatik sind, ist der wahre Wert von Datenstrukturen klar.

Egal welches Problem Sie lösen, auf die eine oder andere Weise müssen Sie mit Daten umgehen - ob es sich um das Gehalt eines Mitarbeiters, Aktienkurse, eine Einkaufsliste oder sogar ein einfaches Telefonverzeichnis handelt.

Basierend auf verschiedenen Szenarien müssen Daten in einem bestimmten Format gespeichert werden. Wir haben eine Handvoll Datenstrukturen, die unseren Bedarf decken, Daten in verschiedenen Formaten zu speichern.

Häufig verwendete Datenstrukturen

Lassen Sie uns zuerst die am häufigsten verwendeten Datenstrukturen auflisten und sie dann einzeln behandeln:

  1. Arrays
  2. Stapel
  3. Warteschlangen
  4. Verknüpfte Listen
  5. Bäume
  6. Grafiken
  7. Versuche (sie sind effektiv Bäume, aber es ist immer noch gut, sie separat aufzurufen).
  8. Hash-Tabellen

Arrays

Ein Array ist die einfachste und am weitesten verbreitete Datenstruktur. Andere Datenstrukturen wie Stapel und Warteschlangen werden von Arrays abgeleitet.

Hier ist ein Bild eines einfachen Arrays der Größe 4, das Elemente (1, 2, 3 und 4) enthält.

Jedem Datenelement wird ein positiver numerischer Wert zugewiesen , der als Index bezeichnet wird und der Position dieses Elements im Array entspricht. Die meisten Sprachen definieren den Startindex des Arrays als 0.

Es gibt zwei Arten von Arrays:

  • Eindimensionale Arrays (wie oben gezeigt)
  • Mehrdimensionale Arrays (Arrays innerhalb von Arrays)

Grundlegende Operationen auf Arrays

  • Einfügen - Fügt ein Element an einem bestimmten Index ein
  • Get - Gibt das Element an einem bestimmten Index zurück
  • Löschen - Löscht ein Element an einem bestimmten Index
  • Größe - Ruft die Gesamtzahl der Elemente in einem Array ab

Häufig gestellte Fragen zu Array-Interviews

  • Suchen Sie das zweite minimale Element eines Arrays
  • Erste nicht wiederholte Ganzzahlen in einem Array
  • Führen Sie zwei sortierte Arrays zusammen
  • Ordnen Sie positive und negative Werte in einem Array neu an

Stapel

Wir alle kennen die berühmte Option " Rückgängig ", die in fast jeder Anwendung vorhanden ist. Haben Sie sich jemals gefragt, wie es funktioniert? Die Idee: Sie speichern die vorherigen Zustände Ihrer Arbeit (die auf eine bestimmte Anzahl beschränkt sind) in einer solchen Reihenfolge im Speicher, dass der letzte zuerst erscheint. Dies kann nicht nur mit Arrays erfolgen. Hier bietet sich der Stack an.

Ein reales Beispiel für Stack könnte ein Stapel Bücher sein, die in vertikaler Reihenfolge angeordnet sind. Um das Buch zu erhalten, das sich irgendwo in der Mitte befindet, müssen Sie alle darüber liegenden Bücher entfernen. So funktioniert die LIFO-Methode (Last In First Out).

Hier ist ein Bild des Stapels mit drei Datenelementen (1, 2 und 3), wobei 3 oben steht und zuerst entfernt wird:

Grundlegende Operationen des Stapels:

  • Push - Fügt oben ein Element ein
  • Pop - Gibt das oberste Element nach dem Entfernen vom Stapel zurück
  • isEmpty - Gibt true zurück, wenn der Stapel leer ist
  • Oben - Gibt das oberste Element zurück, ohne es vom Stapel zu entfernen

Häufig gestellte Fragen zum Stack-Interview

  • Bewerten Sie den Postfix-Ausdruck mithilfe eines Stapels
  • Werte in einem Stapel sortieren
  • Überprüfen Sie ausgeglichene Klammern in einem Ausdruck

Warteschlangen

Ähnlich wie Stack ist Queue eine weitere lineare Datenstruktur, in der das Element sequentiell gespeichert wird. Der einzige signifikante Unterschied zwischen Stapel und Warteschlange besteht darin, dass die Warteschlange anstelle der LIFO-Methode das FIFO implementiertMethode, die für First in First Out steht.

Ein perfektes Beispiel für Queue im wirklichen Leben: eine Reihe von Leuten, die an einem Ticketschalter warten. Wenn eine neue Person kommt, tritt sie von Anfang an und nicht von Anfang an in die Leitung ein - und die Person, die vorne steht, erhält als erste das Ticket und verlässt die Leitung.

Hier ist ein Bild der Warteschlange mit vier Datenelementen (1, 2, 3 und 4), wobei 1 oben steht und zuerst entfernt wird:

Grundlegende Operationen der Warteschlange

  • Enqueue () - Fügt ein Element am Ende der Warteschlange ein
  • Dequeue () - Entfernt ein Element vom Anfang der Warteschlange
  • isEmpty () - Gibt true zurück, wenn die Warteschlange leer ist
  • Top () - Gibt das erste Element der Warteschlange zurück

Häufig gestellte Fragen zum Warteschlangeninterview

  • Implementieren Sie den Stack mithilfe einer Warteschlange
  • Kehren Sie die ersten k Elemente einer Warteschlange um
  • Generieren Sie mithilfe einer Warteschlange Binärzahlen von 1 bis n

Verknüpfte Liste

Eine verknüpfte Liste ist eine weitere wichtige lineare Datenstruktur, die zunächst ähnlich wie Arrays aussehen kann, sich jedoch in der Speicherzuordnung, der internen Struktur und der Ausführung grundlegender Einfüge- und Löschvorgänge unterscheidet.

Eine verknüpfte Liste ist wie eine Knotenkette, in der jeder Knoten Informationen wie Daten und einen Zeiger auf den nachfolgenden Knoten in der Kette enthält. Es gibt einen Kopfzeiger, der auf das erste Element der verknüpften Liste zeigt. Wenn die Liste leer ist, zeigt sie einfach auf null oder nichts.

Verknüpfte Listen werden zum Implementieren von Dateisystemen, Hash-Tabellen und Adjazenzlisten verwendet.

Hier ist eine visuelle Darstellung der internen Struktur einer verknüpften Liste:

Es folgen die Arten von verknüpften Listen:

  • Einfach verknüpfte Liste (unidirektional)
  • Doppelt verknüpfte Liste (bidirektional)

Grundlegende Operationen der verknüpften Liste:

  • InsertAtEnd - Fügt ein bestimmtes Element am Ende der verknüpften Liste ein
  • InsertAtHead - Fügt ein bestimmtes Element am Anfang / Kopf der verknüpften Liste ein
  • Löschen - Löscht ein bestimmtes Element aus der verknüpften Liste
  • DeleteAtHead - Löscht das erste Element der verknüpften Liste
  • Suche - Gibt das angegebene Element aus einer verknüpften Liste zurück
  • isEmpty - Gibt true zurück, wenn die verknüpfte Liste leer ist

Häufig gestellte Fragen zum Interview mit Linked List

  • Eine verknüpfte Liste umkehren
  • Schleife in einer verknüpften Liste erkennen
  • Geben Sie den n-ten Knoten vom Ende in einer verknüpften Liste zurück
  • Entfernen Sie Duplikate aus einer verknüpften Liste

Grafiken

Ein Graph ist eine Reihe von Knoten, die in Form eines Netzwerks miteinander verbunden sind. Knoten werden auch als Eckpunkte bezeichnet. Ein Paar (x, y) wird als Kante bezeichnet , was anzeigt, dass der Scheitelpunkt x mit dem Scheitelpunkt y verbunden ist . Eine Kante kann Gewicht / Kosten enthalten und zeigt an, wie viel Kosten erforderlich sind, um vom Scheitelpunkt x nach y zu gelangen .

Arten von Grafiken:

  • Ungerichteter Graph
  • Gerichteter Graph

In einer Programmiersprache können Diagramme in zwei Formen dargestellt werden:

  • Adjazenzmatrix
  • Adjazenzliste

Gängige Graph-Traversing-Algorithmen:

  • Breite erste Suche
  • Tiefe Erste Suche

Häufig gestellte Fragen zum Graph-Interview

  • Implementieren Sie die erste Suche für Breite und Tiefe
  • Überprüfen Sie, ob ein Diagramm ein Baum ist oder nicht
  • Zählen Sie die Anzahl der Kanten in einem Diagramm
  • Finden Sie den kürzesten Weg zwischen zwei Eckpunkten

Bäume

Ein Baum ist eine hierarchische Datenstruktur, die aus Eckpunkten (Knoten) und Kanten besteht, die sie verbinden. Bäume ähneln Diagrammen, aber der entscheidende Punkt, der einen Baum vom Diagramm unterscheidet, ist, dass in einem Baum kein Zyklus existieren kann.

Bäume werden häufig in der künstlichen Intelligenz und in komplexen Algorithmen verwendet, um einen effizienten Speichermechanismus für die Problemlösung bereitzustellen.

Hier ist ein Bild eines einfachen Baums und grundlegende Terminologien, die in der Baumdatenstruktur verwendet werden:

Die folgenden Baumarten sind:

  • N-ary Baum
  • Ausgeglichener Baum
  • Binärer Baum
  • Binärer Suchbaum
  • AVL-Baum
  • Roter schwarzer Baum
  • 2–3 Baum

Von den oben genannten sind Binary Tree und Binary Search Tree die am häufigsten verwendeten Bäume.

Häufig gestellte Fragen zum Tree-Interview

  • Finden Sie die Höhe eines Binärbaums
  • Finden Sie den k-ten Maximalwert in einem binären Suchbaum
  • Finden Sie Knoten in einem Abstand von „k“ von der Wurzel
  • Suchen Sie die Vorfahren eines bestimmten Knotens in einem Binärbaum

Trie

Trie, auch als "Präfixbäume" bekannt, ist eine baumartige Datenstruktur, die sich als sehr effizient zur Lösung von Problemen im Zusammenhang mit Zeichenfolgen erweist. Es bietet einen schnellen Abruf und wird hauptsächlich zum Suchen von Wörtern in einem Wörterbuch, zum Bereitstellen von automatischen Vorschlägen in einer Suchmaschine und sogar zum IP-Routing verwendet.

Hier ist eine Illustration, wie drei Wörter "top", "so" und "ihr" in Trie gespeichert sind:

Die Wörter werden von oben nach unten gespeichert, wobei die grün gefärbten Knoten "p", "s" und "r" das Ende von "oben", "also" bzw. "ihre" angeben.

Häufig gestellte Fragen zum Trie-Interview:

  • Zählen Sie die Gesamtzahl der Wörter in Trie
  • Drucken Sie alle in Trie gespeicherten Wörter
  • Sortieren Sie Elemente eines Arrays mit Trie
  • Bilden Sie mit Trie Wörter aus einem Wörterbuch
  • Erstellen Sie ein T9-Wörterbuch

Hash-tabelle

Hashing ist ein Prozess, mit dem Objekte eindeutig identifiziert und an einem vorberechneten eindeutigen Index gespeichert werden, der als "Schlüssel" bezeichnet wird. Das Objekt wird also in Form eines "Schlüssel-Wert" -Paares gespeichert, und die Sammlung solcher Elemente wird als "Wörterbuch" bezeichnet. Jedes Objekt kann mit diesem Schlüssel durchsucht werden. Es gibt verschiedene Datenstrukturen, die auf Hashing basieren, aber die am häufigsten verwendete Datenstruktur ist die Hash-Tabelle .

Hash-Tabellen werden im Allgemeinen mithilfe von Arrays implementiert.

Die Leistung der Hashing-Datenstruktur hängt von diesen drei Faktoren ab:

  • Hash-Funktion
  • Größe der Hash-Tabelle
  • Kollisionsbehandlungsmethode

Hier ist eine Illustration, wie der Hash in einem Array zugeordnet wird. Der Index dieses Arrays wird über eine Hash-Funktion berechnet.

Häufig gestellte Fragen zum Hashing-Interview

  • Finden Sie symmetrische Paare in einem Array
  • Verfolgen Sie den vollständigen Weg einer Reise
  • Suchen Sie, ob ein Array eine Teilmenge eines anderen Arrays ist
  • Überprüfen Sie, ob bestimmte Arrays nicht zusammenhängend sind

Dies sind die acht wichtigsten Datenstrukturen, die Sie unbedingt kennen sollten, bevor Sie ein Coding-Interview beginnen.

Wenn Sie nach Ressourcen zu Datenstrukturen zum Codieren von Interviews suchen, lesen Sie die interaktiven und herausfordernden Kurse: Datenstrukturen zum Codieren von Interviews (Python, Java oder JavaScript).

Weitere Informationen finden Sie unter Coderust 3.0: Schnellere Codierung von Interviewvorbereitungen mit interaktiven Herausforderungen und Visualisierungen.

Wenn Sie sich auf ein Software-Engineering-Interview vorbereiten, finden Sie hier eine umfassende Roadmap zur Vorbereitung des Codierens von Interviews.

Viel Glück und viel Spaß beim Lernen! :) :)