Interviewfragen zu Algorithmen und Datenstrukturen mit Antworten

Beispielfragen

Ein paar Fragen aus jedem Level mit richtiger Antwort und Erklärung.

Algorithmen und Datenstrukturen · Junior

1. Was beschreibt die O-Notation?
   ▸Antwort zeigen

   Richtige Antwort: Wie Laufzeit oder Speicher mit der Größe der Eingabe wachsen

   Die O-Notation beschreibt die Wachstumsrate: wie sich die Kosten ändern, wenn n wächst, ohne Konstanten und Terme niedrigerer Ordnung. Über die absolute Zeit auf einer bestimmten Maschine sagt sie nichts: eine O(n)-Schleife kann bei kleinen Eingaben langsamer sein als eine O(n²)-Schleife.

2. Warum schreibt man O(2n + 10) einfach als O(n)?
   ▸Antwort zeigen

   Richtige Antwort: Weil Konstanten und Terme niedrigerer Ordnung die Wachstumsrate nicht ändern

   Die O-Notation beschreibt die Form des Wachstums für großes n. Mal 2 oder plus 10 ändert nichts daran, dass die Kosten linear wachsen, daher fallen beide weg. In der Praxis zählen Konstanten trotzdem, deshalb gibt es Benchmarks.

3. Welche Komplexität wächst mit steigendem n am langsamsten?
   ▸Antwort zeigen

   Richtige Antwort: O(log n)

   Logarithmisches Wachstum ist sehr langsam: eine Verdopplung von n fügt nur einen Schritt hinzu. Bei einer Million Elementen ist log₂ n etwa 20. O(n) und O(n log n) wachsen viel schneller.

4. Welche Komplexität hat das Lesen von arr[i] aus einem JavaScript-Array?
   ▸Antwort zeigen

   Richtige Antwort: O(1)

   Der Zugriff per Index braucht konstante Zeit: die Engine berechnet, wo das Element liegt, statt das Array zu durchlaufen. Das ist der Hauptvorteil von Arrays gegenüber verketteten Listen.

Algorithmen und Datenstrukturen · Middle

1. Wie funktioniert Merge Sort?
   ▸Antwort zeigen

   Richtige Antwort: Das Array halbieren, jede Hälfte sortieren und dann zusammenführen

   Merge Sort teilt, bis einzelne Elemente übrig sind, und führt dann sortierte Hälften mit zwei Zeigern zusammen. Es ist in jedem Fall O(n log n) und stabil, braucht aber O(n) zusätzlichen Speicher fürs Zusammenführen.

2. Was ist der Hauptnachteil von Merge Sort auf Arrays?
   ▸Antwort zeigen

   Richtige Antwort: Es braucht O(n) zusätzlichen Speicher fürs Zusammenführen

   Der Schritt des Zusammenführens schreibt in einen temporären Puffer. Die Zeit ist unabhängig von der Eingabe O(n log n), und die klassische Umsetzung ist stabil. Auf verketteten Listen geht Merge Sort ohne zusätzlichen Puffer.

3. Was ist der schlimmste Fall von Quicksort, und wann tritt er ein?
   ▸Antwort zeigen

   Richtige Antwort: O(n²), wenn Pivots das Array immer sehr ungleich teilen

   Ist das Pivot immer das kleinste oder größte Element (etwa das erste Element eines sortierten Arrays), entfernt jede Aufteilung nur ein Element. Zufällige Pivots oder Median-of-three machen das unwahrscheinlich; der Durchschnitt ist O(n log n).

4. Warum ist Quicksort in der Praxis oft schneller als Merge Sort, trotz gleichem Durchschnitt O(n log n)?
   ▸Antwort zeigen

   Richtige Antwort: Es sortiert an Ort und Stelle und greift sequenziell auf Speicher zu

   Das Aufteilen arbeitet im Array mit guter Cache-Lokalität und kleinen Konstanten. Sein schlimmster Fall ist sogar schlechter (O(n²)), und die übliche In-place-Version ist nicht stabil.

Algorithmen und Datenstrukturen · Senior

1. Warum liefert Dijkstras Algorithmus mit negativen Kantengewichten falsche Ergebnisse?
   ▸Antwort zeigen

   Richtige Antwort: Ein abgeschlossener Knoten könnte über eine negative Kante noch kürzer werden

   Dijkstra nimmt an, dass kein späterer Weg kürzer sein kann, sobald der nächste Knoten aus der Queue genommen ist. Eine negative Kante bricht diese Annahme. Bellman-Ford behandelt negative Gewichte in O(V × E) und erkennt auch negative Zyklen.

2. Welche zusätzliche Fähigkeit hat Bellman-Ford gegenüber Dijkstra?
   ▸Antwort zeigen

   Richtige Antwort: Er kann negative Gewichte und erkennt negative Zyklen

   Er relaxiert alle Kanten V - 1 Mal; verbessert ein V-ter Durchlauf noch eine Distanz, gibt es einen negativen Zyklus. Der Preis ist O(V × E), viel langsamer als Dijkstras O((V + E) log V).

3. Wie unterscheidet sich A* von Dijkstras Algorithmus?
   ▸Antwort zeigen

   Richtige Antwort: Er ergänzt eine Schätzung der verbleibenden Distanz

   A* ordnet Knoten nach g + h: den bekannten Kosten plus einer Schätzung bis zum Ziel, etwa die Luftlinie auf einer Karte. Überschätzt h nie (zulässig), bleibt der Weg optimal, und es werden viel weniger Knoten erkundet.

4. Welche Komplexität hat Floyd-Warshall, und wann ist er eine vernünftige Wahl?
   ▸Antwort zeigen

   Richtige Antwort: O(V³); für kürzeste Wege zwischen allen Paaren in kleinen, dichten Graphen

   Es sind drei verschachtelte Schleifen über Knoten, die dist[i][j] über jeden Zwischenknoten k aktualisieren. Einfach und mit negativen Kanten (ohne negative Zyklen) nutzbar, aber bei V = 10.000 sind es schon 10¹² Schritte.