Was sie bei einem Vorstellungsgespräch fragen könnten: Datenstrukturen in Java. Teil 1

Hallo! Unabhängig davon, wie Sie es betrachten, können Sie kein Entwickler werden, ohne ein technisches Aufnahmegespräch erfolgreich zu bestehen. Es gibt viele Technologien im Zusammenhang mit Java und es ist unmöglich, alles zu lernen. In Vorstellungsgesprächen wird in der Regel nur dann etwas Konkretes gefragt, wenn ein Entwickler mit guten Erfahrungen in einem für das Projekt wichtigen Rahmen gesucht wird. Wenn dem so ist, werden Sie mit voller Geschwindigkeit durch dieses Framework gejagt, daran haben Sie keinen Zweifel. Aber jetzt reden wir über die Basis, die jeder Java-Entwickler kennen sollte. Über das klassische Wissen, mit dem alles beginnt. Heute möchte ich auf eines der grundlegenden Themen jedes Interviews eingehen – Datenstrukturen in Java . Anstatt also um den heißen Brei herumzureden, fangen wir an. Hier finden Sie eine Liste mit Fragen, die Ihnen während eines Vorstellungsgesprächs zu diesem Thema gestellt werden könnten.

1. Erzählen Sie uns etwas über Datenstrukturen

Eine Datenstruktur ist ein Datenspeicher, der Informationen enthält, die auf eine bestimmte Weise strukturiert sind. Diese Strukturen sind für die effiziente Durchführung bestimmter Vorgänge konzipiert. Typische Beispiele für Datenstrukturen sind:

• Arrays,
• Stapel,
• Warteschlangen,
• Verwandte Listen,
• Grafiken,
• Bäume,
• Präfixbäume,
• Hash-tabelle.

Mehr darüber erfahren Sie hier und hier . Daten sind ein zentraler Bestandteil eines Programms und Strukturen ermöglichen es, diese Daten in einer bestimmten, klar strukturierten Form zu speichern. Was auch immer Ihre Anwendung tut, dieser Aspekt wird immer vorhanden sein: Wenn es sich um einen Webshop handelt, werden Informationen über Produkte gespeichert, wenn es sich um ein soziales Netzwerk handelt, Daten über Benutzer und Dateien und so weiter.

2. Was wissen Sie über Arrays?

Ein Array ist ein Container zum Speichern von Werten desselben Typs, dessen Anzahl im Voraus angegeben wurde. Ein Beispiel für die Erstellung eines Arrays mit String-Werten:

String[] strArray = {"Java","is","the","best","language"};

Beim Erstellen eines Arrays wird allen seinen Elementen Speicher zugewiesen: Je mehr Zellen für Elemente anfänglich angegeben werden, desto mehr Speicher wird zugewiesen. Wenn ein leeres Array mit einer bestimmten Anzahl von Zellen erstellt wird, werden allen Elementen des Arrays Standardwerte zugewiesen. Zum Beispiel:

int[] arr = new int[10];

Für ein Array mit Elementen vom Typ Boolean sind die Anfangswerte ( Standardwerte ) also false , für Arrays mit numerischen Werten - 0, mit Elementen vom Typ char - \u0000 . Für ein Array vom Klassentyp (Objekte) – null (keine leeren Zeichenfolgen – „“ , sondern speziell null ). Das heißt, im obigen Beispiel sind alle Werte des arr- Arrays 0, bis sie direkt angegeben werden. Im Gegensatz zu Sammlungen sind Arrays nicht dynamisch. Sobald ein Array mit einer bestimmten Größe deklariert ist, kann die Größe selbst nicht mehr geändert werden. Um einem Array ein neues Element hinzuzufügen, müssen Sie ein neues größeres Array erstellen und alle Elemente aus dem alten hinein kopieren (so funktioniert ArrayList). Es gibt einen Punkt, den nicht jeder kennt und an dem man sich ganz gut orientieren kann. In Java gibt es zwei Arten von Variablen: einfache Typen und Verweise auf vollwertige Objekte. Welche davon sind Arrays? Zum Beispiel hier:

int[] arr = new int[10];

Es scheint, dass alles einfach ist – das sind 10 int- Elemente . Wir können also sagen, dass dies ein einfacher Typ ist? Egal wie es ist. In Java sind Arrays Objekte, werden dynamisch erstellt und können Variablen vom Typ Object zugewiesen werden. Alle Methoden der Object-Klasse können auf einem Array aufgerufen werden. Wir können also sogar schreiben:

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

Bei der Ausgabe an die Konsole erhalten Sie möglicherweise Folgendes: Lesen Sie mehr über die Funktionen von Arrays in Java in diesem Artikel über Java Array . Um Ihr Wissen zu festigen, können Sie mehrere Aufgaben aus dieser Sammlung lösen .

3. Erklären Sie die Hierarchie der Sammlungen

Sammlungen werden in Situationen verwendet, in denen Sie beim Arbeiten mit Daten Flexibilität benötigen. Sammlungen können ein Element hinzufügen, ein Element entfernen und viele andere Vorgänge ausführen. Es gibt viele verschiedene Implementierungen in Java und wir müssen nur die richtige Sammlung für die aktuelle Situation auswählen. Wenn Sie die Collection- Schnittstelle erwähnen, werden Sie normalerweise gebeten, einige ihrer Implementierungen und ihre Beziehung zu Map aufzulisten . Nun, lass es uns herausfinden. Sammlung und Karte sind also zwei verschiedene Hierarchien für Datenstrukturen. So sieht die Collection- Hierarchie aus : Die Collection- Schnittstelle ist der wichtigste obere Link mit einer Liste grundlegender Methoden, aus denen drei grundlegende Arten von Datenstrukturen stammen – Set , List , Queue . Set<T> ist eine Schnittstelle, die eine Sammlung von Objekten darstellt, in denen jedes Objekt eindeutig ist. List<T> ist eine Schnittstelle, die eine geordnete Folge von Objekten darstellt, die als Liste bezeichnet wird. Queue<T> ist eine Schnittstelle, die für Strukturen verantwortlich ist, die als Warteschlange organisiert sind (sequentielle Speicherung von Elementen). Wie bereits erwähnt, handelt es sich bei Map um eine separate Hierarchie: Map<K, V> ist eine Schnittstelle, die ein Wörterbuch darstellt, in dem Elemente als Schlüssel-Wert-Paare enthalten sind. Darüber hinaus sind alle Schlüssel (K) innerhalb des Map- Objekts eindeutig . Diese Art der Sammlung erleichtert das Auffinden eines Elements, wenn wir den Schlüssel kennen – die eindeutige Kennung des Objekts.

4. Was wissen Sie über Set?

Wie bereits erwähnt, weist diese Sammlung viele einzigartige Elemente auf. Mit anderen Worten: Dasselbe Objekt kann in einem Java- Set nicht mehr als einmal vorkommen. Ich möchte auch darauf hinweisen, dass wir ein Element nicht anhand der Zahl (Index) aus einer Menge extrahieren können, sondern nur mit roher Gewalt. Wichtig ist, dass verschiedene Set- Implementierungen unterschiedliche Arten der Datenstrukturierung haben. Wir werden spezifische Implementierungen weiter betrachten. Die Hauptimplementierungen von Set : HashSet ist ein Set, das auf einer Hash-Tabelle basiert, was wiederum bei der Suche hilft. Verwendet eine Hash-Funktion, die die Leistung beim Suchen und Einfügen verbessert. Unabhängig von der Anzahl der Elemente werden Einfügung und Suche (manchmal Löschung) im Allgemeinen in nahezu konstanter Zeit durchgeführt – O(1). Wir werden uns die Hash-Funktion etwas später genauer ansehen. Ich möchte auch darauf hinweisen, dass das HashSet eine HashMap enthält , in der die ganze Magie geschieht. Hier ist ein ausführlicher Artikel über HashSet in Java . LinkedHashSet – diese Klasse erweitert HashSet , ohne neue Methoden hinzuzufügen. Wie LinkedList verwaltet diese Klasse eine verknüpfte Liste der Elemente einer Menge in der Reihenfolge, in der sie eingefügt wurden. Auf diese Weise können Sie die erforderliche Reihenfolge in einer bestimmten Set- Implementierung organisieren . Die TreeSet- Klasse erstellt einen Satz, der auf einem Rot-Schwarz-Baum basiert, um die Struktur der Speicherelemente zu organisieren. Mit anderen Worten: In einer gegebenen Menge können wir die Elemente in aufsteigender Reihenfolge sortieren. Wenn wir einige Standardobjekte aus der „Box“ verwenden, zum Beispiel Integer , müssen wir nichts tun, um die Menge der Integers in aufsteigender Reihenfolge anzuordnen:

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

Und in der Konsole erhalten wir die Ausgabe: Das heißt, in diesem Satz werden die Zahlen sortiert gespeichert. Wenn wir String- Elemente in einem TreeSet verwenden , werden diese alphabetisch sortiert. Was wäre, wenn wir eine Standardklasse (benutzerdefinierte Klasse) hätten? Wie werden Objekte dieser Klasse das TreeSet strukturieren ? Wenn wir versuchen, dieser Menge ein beliebiges Objekt zuzuordnen :

TreeSet set = new TreeSet<>();
set.add(new Cat(4, „Mürzik“));
set.add(new Cat(2, „Barsik“));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

Wir erhalten eine ClassCastException, da das TreeSet nicht weiß, wie Objekte dieses Typs sortiert werden sollen. In diesem Fall benötigen wir unser benutzerdefiniertes Objekt, um die Comparable- Schnittstelle und ihre CompareTo- Methode zu implementieren :

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

Wie Sie bemerkt haben, gibt die Methode „compareTo“ ein int zurück :

• 1, wenn das aktuelle (dieses) Objekt als groß angesehen wird;
• -1, wenn das aktuelle Objekt als kleiner betrachtet wird als das, das als Argument kam;
• 0, wenn die Objekte gleich sind (wir verwenden dies in diesem Fall nicht).

In diesem Fall funktioniert unser TreeSet ordnungsgemäß und zeigt das Ergebnis an: Eine andere Möglichkeit besteht darin , eine separate Sortierklasse zu erstellen, die die Komparatorschnittstelle und ihre Vergleichsmethode implementiert :

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

In diesem Fall müssen wir zur Verwendung ein Objekt dieser Klasse auf den TreeSet- Konstruktor setzen :

TreeSet set = new TreeSet<>(new CatComparator());

Danach werden alle Objekte der Cat- Klasse, die im TreeSet enthalten sind, mithilfe der Cat Comparator- Klasse sortiert . In diesem Artikel erfahren Sie mehr über Comparator und Comparable in Java .

5. Erzählen Sie uns etwas über die Warteschlange

Queue ist eine Schnittstelle, die für Strukturen verantwortlich ist, die als Warteschlange organisiert sind – eine Datenstruktur, die Elemente nacheinander speichert. Beispielsweise wird in einer Warteschlange diejenige Person als erste eintreten, die früher als die anderen eingetroffen ist, und die letzte Person, die später als alle anderen eingetroffen ist. Diese Methode heißt FIFO , also First in First Out . Einzigartige Queue -Methoden konzentrieren sich auf die Arbeit mit dem ersten oder letzten Element, zum Beispiel:

• hinzufügen und anbieten – fügt ein Element am Ende der Warteschlange ein,
• Remove – ruft den Header dieser Warteschlange ab und entfernt ihn.
• peek – Ruft den Warteschlangenheader ab, entfernt ihn jedoch nicht.

TEIL 2