Die wichtigsten Datenstrukturen, die Sie über Ihr Programmierinterview wissen sollten

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

Nach mehr als 40 Jahren bleibt diese Identität gültig. Deshalb müssen Arbeitssuchende, die Programmierer werden wollen, nachweisen, dass sie die Datenstrukturen kennen und anwenden können.

Bei fast allen Aufgaben benötigt ein Kandidat ein tiefes Verständnis der Datenstrukturen. Gleichzeitig ist es nicht so wichtig, ob Sie ein Absolvent sind (Abschluss einer Universität oder eines Programmierkurses) oder über zehn Jahre Erfahrung verfügen.

Manchmal wird in Interviewfragen die eine oder andere Datenstruktur direkt erwähnt, zum Beispiel „ein binärer Baum gegeben“. In anderen Fällen ist die Aufgabe verschleierter formuliert, z. B. "Sie müssen nachverfolgen, wie viele Bücher wir von jedem Autor haben."

Das Studium von Datenstrukturen ist ein unverzichtbares Geschäft, auch wenn Sie nur versuchen, sich an Ihrem aktuellen Arbeitsplatz professionell zu verbessern. Beginnen wir mit den Grundlagen.

Übersetzt nach Alconost

Was ist eine Datenstruktur?

Kurz gesagt, eine Datenstruktur ist ein Container, in dem Informationen auf charakteristische Weise angeordnet sind. Dank dieses „Layouts“ ist die Datenstruktur bei einigen Vorgängen effektiv und bei anderen ineffizient. Unser Ziel ist es, die Datenstrukturen so zu verstehen, dass Sie aus ihnen die für die Lösung des spezifischen Problems am besten geeigneten auswählen können.

Warum brauchen wir Datenstrukturen?

Da Datenstrukturen zum ordnungsgemäßen Speichern von Informationen verwendet werden und Daten das wichtigste Phänomen in der Informatik sind, ist der wahre Wert von Datenstrukturen offensichtlich.

Es spielt keine Rolle, welche Art von Aufgabe Sie lösen, auf die eine oder andere Weise müssen Sie mit den Daten umgehen, ob es sich um das Gehalt eines Mitarbeiters, Börsenkurse, eine Liste von Produkten für den Laden oder ein reguläres Telefonverzeichnis handelt.

Je nach Szenario müssen die Daten in einem geeigneten Format gespeichert werden. Wir verfügen über eine Reihe von Datenstrukturen, die uns so unterschiedliche Formate bieten.

Gemeinsame Datenstrukturen

Lassen Sie uns zunächst die gängigsten Datenstrukturen auflisten und dann jede nacheinander analysieren:

1. Arrays
2. Stapel
3. Warteschlangen
4. Verknüpfte Listen
5. Bäume
6. Zählt
7. Bohrer (im Wesentlichen sind dies auch Bäume, aber sie sollten separat betrachtet werden).
8. Hash-Tabellen

Arrays

Ein Array ist die einfachste und häufigste Datenstruktur. Andere Datenstrukturen wie Stapel und Warteschlangen werden von Arrays abgeleitet.

Hier ist ein einfaches Array der Größe 4 dargestellt, 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. In den meisten Programmiersprachen sind die Elemente im Array von 0 nummeriert.

Es gibt zwei Arten von Arrays:

• Eindimensional (wie oben gezeigt)
• Mehrdimensional (Arrays, in die andere Arrays eingebettet sind)

Die einfachsten Array-Operationen

• Einfügen - Fügen Sie ein Element an einer Position mit einem bestimmten Index ein
• Get - Gibt ein Element zurück, das eine Position mit einem bestimmten Index einnimmt
• Löschen - Löscht das Element mit dem angegebenen Index
• Größe - Ermittelt die Gesamtzahl der Elemente im Array

Häufig gestellte Fragen zum Interview

• Suchen Sie das zweite minimale Array-Element
• Suchen Sie 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

Jeder kennt die berühmte Option „Abbrechen“, die in fast allen Anwendungen verfügbar ist. Haben Sie sich jemals gefragt, wie es funktioniert? Die Bedeutung ist folgende: Der vorherige Status Ihrer Arbeit wird im Programm gespeichert (die Anzahl der gespeicherten Zustände ist begrenzt) und sie befinden sich in dieser Reihenfolge im Speicher: Das zuletzt gespeicherte Element wird zuerst angezeigt. Arrays allein können dieses Problem nicht lösen. Hier bietet sich der Stapel an.

Der Stapel kann mit einem hohen Stapel Bücher verglichen werden. Wenn Sie ein Buch benötigen, das in der Nähe der Stapelmitte liegt, müssen Sie zuerst alle oben genannten Bücher entfernen. So funktioniert das LIFO-Prinzip (Last come, first go).

Es sieht aus wie ein Stapel mit drei Datenelementen (1, 2 und 3), wobei 3 oben liegt - daher wird er zuerst entfernt:

Einfachste Stapeloperationen:

• Push - Schiebt einen Gegenstand oben auf den Stapel
• Pop - Gibt das oberste Element zurück, nachdem es vom Stapel entfernt wurde
• 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 im Interview

• Berechnen Sie den Postfix-Ausdruck mit dem Stapel
• Werte auf Stapel sortieren
• Überprüfen Sie die ausgeglichenen Klammern im Ausdruck

Warteschlangen

Eine Warteschlange ist wie ein Stapel eine lineare Datenstruktur, in der Elemente in sequentieller Reihenfolge gespeichert werden. Der einzige signifikante Unterschied zwischen dem Stapel und der Warteschlange besteht darin, dass in der Warteschlange anstelle von LIFO das FIFO-Prinzip gilt (Wer zuerst kommt, mahlt zuerst).

Ein ideales realistisches Beispiel für eine Warteschlange - dies ist die Warteschlange der Kunden an der Kasse. Ein neuer Käufer steht ganz am Ende der Linie, nicht am Anfang. Derjenige, der zuerst in der Warteschlange steht, ist der erste, der ein Ticket kauft und es zuerst verlässt.

Hier ist ein Bild einer Warteschlange mit vier Datenelementen (1, 2, 3 und 4), wobei 1 zuerst geht und die Warteschlange zuerst verlässt:

Einfache Warteschlangenoperationen

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

Häufig gestellte Fragen zum Interview

• Implementieren Sie einen Stapel mithilfe einer Warteschlange
• Zahlen Sie die ersten k Artikel in der Warteschlange
• 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 auf den ersten Blick einem Array ähnelt. Eine verknüpfte Liste unterscheidet sich jedoch von einem Array in der Speicherzuordnung, der internen Struktur und der Art und Weise, wie grundlegende Einfüge- und Löschvorgänge darin ausgeführt werden.

Eine verknüpfte Liste ähnelt einer Knotenkette, von der jeder Informationen enthält: beispielsweise Daten und einen Zeiger auf den nächsten Knoten in der Kette. Es gibt einen Kopfzeiger, der dem ersten Element in einer verknüpften Liste entspricht. Wenn die Liste leer ist, wird sie einfach auf null (nichts) gerichtet.

Mithilfe verknüpfter Listen werden Dateisysteme, Hash-Tabellen und Adjazenzlisten implementiert.

So können Sie die interne Struktur einer verknüpften Liste visualisieren:


Es gibt Arten von verknüpften Listen:

• Single Link List (unidirektional)
• Doppelt verknüpfte Liste (bidirektional)

Die einfachsten Operationen mit verknüpften Listen sind:

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

Häufig gestellte Fragen zum Interview:

• Zahlen Sie eine verknüpfte Liste
• Suchen Sie die Schleife in der verknüpften Liste
• Geben Sie den N-ten Knoten vom Anfang der verknüpften Liste zurück
• Entfernen Sie doppelte Werte aus der verknüpften Liste

Zählt

Ein Graph ist eine Reihe von Knoten, die in Form eines Netzwerks miteinander verbunden sind. Knoten werden auch als Eckpunkte bezeichnet. Das Paar (x, y) wird als Kante bezeichnet, was bedeutet, dass der Scheitelpunkt x mit dem Scheitelpunkt y verbunden ist . Eine Kante kann Gewicht / Kosten haben - ein Indikator, der angibt, wie teuer der Übergang von Scheitelpunkt x zu Scheitelpunkt y ist.


Arten von Diagrammen:

• Ungerichtete Grafik
• Orientierter Graph

In einer Programmiersprache gibt es zwei Arten von Diagrammen:

• Adjazenzmatrix
• Adjazenzliste

Gängige Graph-Traversal-Algorithmen:

• Breite Suche
• Tiefensuche

Häufig gestellte Fragen zum Interview:

• Implementieren Sie Breitensuche
• Überprüfen Sie, ob das Diagramm ein Baum ist oder nicht
• Zählen Sie die Anzahl der Kanten in einem Diagramm
• Finden Sie den kürzesten Weg zwischen zwei Gipfeln

Bäume

Ein Baum ist eine hierarchische Datenstruktur, die aus Eckpunkten (Knoten) und Kanten besteht, die sie verbinden. Bäume ähneln Diagrammen. Der Hauptunterschied zwischen einem Baum und einem Diagramm besteht jedoch darin, dass in einem Baum keine Zyklen vorhanden sind.

Bäume werden häufig auf dem Gebiet der künstlichen Intelligenz und in komplexen Algorithmen verwendet und dienen als effektive Informationsquelle für die Lösung von Problemen.

Hier ist ein einfaches Baumdiagramm und eine grundlegende Terminologie für diese Datenstruktur:


Es gibt folgende Baumarten:

• N-Baum
• Ausgeglichener Baum
• Binärer Baum
• Binärer Suchbaum
• AVL-Baum
• Rotes Ebenholz
• 2-3 Baum

Von den oben genannten Bäumen werden am häufigsten der Binärbaum und der Binärsuchbaum verwendet.

Häufig gestellte Interviewfragen zu Bäumen:

Finden Sie die Höhe eines Binärbaums
Suchen Sie den k-ten Maximalwert im binären Suchbaum
Suchen Sie Knoten, die sich "k" von der Wurzel entfernt befinden
Suchen Sie die Vorfahren eines bestimmten Knotens in einem Binärbaum

Bor

Bor, auch als "Präfixbaum" bezeichnet, ist eine baumartige Datenstruktur, die besonders effektiv bei der Lösung von Zeichenfolgenproblemen ist. Es bietet einen schnellen Datenabruf und wird am häufigsten zum Suchen nach Wörtern in einem Wörterbuch, zum automatischen Vervollständigen in einer Suchmaschine und sogar zum IP-Routing verwendet.

So werden die drei Wörter „oben“ (oben), „also“ (daher) und „ihre“ (sie) im Wald gespeichert:


Die Wörter sind von oben nach unten angeordnet, und die grünen Knoten "p", "s" und "r" vervollständigen jeweils die Wörter "oben", "also" und "ihre".

Häufig gestellte Interviewfragen zu Bohrern:

• Zählen Sie die Gesamtzahl der im Kiefernwald gespeicherten Wörter
  
• Alle im Wald gespeicherten Wörter anzeigen.
  
• Sortieren Sie Array-Elemente mit Bor
  
• Bauen Sie Vokabeln mit Bor auf
  
• Erstellen Sie ein T9-Wörterbuch
  

Hash-Tabelle

Hashing ist ein Prozess, mit dem Objekte eindeutig identifiziert und jedes Objekt anhand eines vorberechneten Index gespeichert wird, der als „Schlüssel“ bezeichnet wird. Somit wird das Objekt als Schlüsselwert gespeichert, und eine Sammlung solcher Objekte wird als Wörterbuch bezeichnet. Jedes Objekt kann mit seinem Schlüssel durchsucht werden. Es gibt verschiedene Datenstrukturen, die auf dem Prinzip des Hashings basieren, aber meistens wird eine Hash-Tabelle aus solchen Strukturen verwendet.

Hash-Tabellen werden in der Regel mit Arrays implementiert.

Die Leistung einer Hash-Datenstruktur hängt von den folgenden drei Faktoren ab:

• Hash-Funktion
• Hash-Tabellengröße
• Kollisionsverarbeitungsmethode

Das Folgende zeigt, wie ein Hash einem Array zugeordnet wird. Der Index dieses Arrays wird mithilfe einer Hash-Funktion berechnet.

Häufig gestellte Hash-Fragen im Interview:

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

Das Obige beschreibt die acht wichtigsten Datenstrukturen, die Sie unbedingt kennen müssen, bevor Sie zu einem Programmierinterview gehen.

Viel Glück und interessantes Lernen! :) :)

Über den Übersetzer

Der Artikel wurde von Alconost übersetzt.

Alconost lokalisiert Spiele , Anwendungen und Websites in 68 Sprachen. Muttersprachliche Übersetzer, Sprachtests, Cloud-Plattform mit API, kontinuierliche Lokalisierung, Projektmanager rund um die Uhr, jedes Format von Zeichenfolgenressourcen.

Wir machen auch Werbe- und Schulungsvideos - für Websites, die verkaufen, Image, Werbung, Schulung, Teaser, Expliner, Trailer für Google Play und den App Store.

Weitere Details