Interviewfragen zu Algorithmen und Datenstrukturen (Senior) mit Antworten

75 Fragen fürs Vorstellungsgespräch zu Algorithmen und Datenstrukturen (Senior) mit richtigen Antworten, Erklärungen und Links zur Dokumentation.

Diesen Test machen
  1. 1.Warum liefert Dijkstras Algorithmus mit negativen Kantengewichten falsche Ergebnisse?
  2. 2.Welche zusätzliche Fähigkeit hat Bellman-Ford gegenüber Dijkstra?
  3. 3.Wie unterscheidet sich A* von Dijkstras Algorithmus?
  4. 4.Welche Komplexität hat Floyd-Warshall, und wann ist er eine vernünftige Wahl?
  5. 5.Wie unterscheiden sich die Algorithmen von Prim und Kruskal?
  6. 6.Was macht Union-Find-Operationen nahezu O(1)?
  7. 7.Welches Problem löst ein Fenwick-Baum (Binary Indexed Tree)?
  8. 8.Wann wählt man einen Segmentbaum statt eines Fenwick-Baums?
  9. 9.Was kann ein Bloom-Filter über einen Schlüssel sagen?
  10. 10.Warum kann man aus einem normalen Bloom-Filter kein Element löschen?
  11. 11.Was schätzt HyperLogLog, und warum ist es beliebt?
  12. 12.Welchen Vorteil bringt Consistent Hashing einem verteilten Cache?
  13. 13.Was ist eine Skip List?
  14. 14.Warum nutzen Datenbanken für Indizes B-Bäume statt binärer Suchbäume?
  15. 15.Welchen Kompromiss machen LSM-Bäume gegenüber B-Bäumen?
  16. 16.Welche durchschnittliche Komplexität hat Quickselect beim Finden des k-kleinsten Elements?
  17. 17.Wie zieht man aus einem Stream unbekannter Länge eine gleichverteilte Stichprobe von k Elementen?
  18. 18.Was ist falsch daran, ein Array per arr.sort(() => Math.random() - 0.5) zu mischen?
  19. 19.Wie sortiert man eine 200-GB-Datei auf einer Maschine mit 8 GB RAM?
  20. 20.Wie führt man k sortierte Listen mit insgesamt n Elementen effizient zusammen?
  21. 21.Was ist die Kernidee der String-Suche nach Rabin-Karp?
  22. 22.Wie erreicht KMP eine String-Suche in O(n + m)?
  23. 23.Welche Komplexität hat nach dem Master-Theorem T(n) = 2T(n/2) + O(n)?
  24. 24.Was bedeutet es, dass die DP für das 0/1-Rucksackproblem pseudopolynomiell ist?
  25. 25.Ein Interviewer beschreibt ein Problem, das sich auf das Problem des Handlungsreisenden zurückführen lässt. Was ist eine sinnvolle Reaktion?
  26. 26.Was nutzt Bitmasken-DP als Zustand?
  27. 27.Wie senkt man den Speicher einer DP für LCS oder Edit-Distanz von O(n × m) auf O(m)?
  28. 28.Was ist amortisierte Analyse mit der „Buchhaltungs“- oder „Potenzial“-Methode?
  29. 29.Was ist Hash Flooding?
  30. 30.Warum kann ein O(n log n)-Algorithmus auf echten Eingaben gegen einen O(n²)-Algorithmus verlieren?
  31. 31.Warum schneidet Timsort auf realen Daten so gut ab?
  32. 32.Was ist Introsort, und warum nutzt C++ std::sort es?
  33. 33.Welche Struktur findet alle Intervalle, die einen Punkt überlappen, in O(log n + k)?
  34. 34.Was berechnet der Algorithmus von Tarjan oder Kosaraju?
  35. 35.Warum läuft die Reconciliation von React in O(n), wenn ein allgemeiner Baum-Diff etwa O(n³) ist?
  36. 36.Welchen Algorithmus nutzen git diff und viele Diff-Werkzeuge standardmäßig?
  37. 37.Eine virtualisierte Liste rendert nur sichtbare Zeilen von 100.000 Elementen unterschiedlicher Höhe. Wie findet sie schnell die erste sichtbare Zeile?
  38. 38.Was bringt Structural Sharing in persistenten Datenstrukturen?
  39. 39.Wann schlägt LFU als Verdrängungsstrategie eines Caches LRU?
  40. 40.Wie funktioniert ein Rate Limiter nach dem Token-Bucket-Prinzip?
  41. 41.Welche Komplexität hat das Aufbauen eines binären Heaps aus n unsortierten Elementen per Sift-down (Heapify)?
  42. 42.Warum lässt sich binäre Suche auf einer verketteten Liste nicht effizient ausführen?
  43. 43.Welcher Ansatz beantwortet „steht dieses Wort im Wörterbuch?“ für Millionen Wörter mit dem wenigsten Speicher, wenn seltene falsch Positive in Ordnung sind?
  44. 44.Welche Zeitkomplexität hat der naive Aufbau eines Suffix-Arrays durch Sortieren aller Suffixe?
  45. 45.Warum ersetzt man Tries in Produktion oft durch Hash-Maps oder Radix-Bäume?
  46. 46.Welchen Algorithmus sollte man nutzen, um beim Build einen Zyklus in Modul-Imports zu erkennen?
  47. 47.Warum kann Union-Find keine Zyklen in einem gerichteten Graphen erkennen?
  48. 48.Welche Komplexität hat die Prüfung, ob eine Zahl eine Zweierpotenz ist, mit n > 0 && (n & (n - 1)) === 0?
  49. 49.Warum ist 0.1 + 0.2 !== 0.3 für Algorithmen wichtig?
  50. 50.Welche Aussage über Durchschnitt und schlimmsten Fall von Hashtabellen-Operationen stimmt?
  51. 51.Was ist cachefreundlich daran, ein 2D-Array in C-artigem Layout Zeile für Zeile zu durchlaufen?
  52. 52.Welcher Algorithmus findet den maximalen Fluss in einem Netzwerk?
  53. 53.Eine rekursive Lösung ist korrekt, läuft aber wegen wiederholter Teilprobleme mit drei Parametern in ein Timeout. Was ist die übliche erste Abhilfe?
  54. 54.Wie viele Vergleiche erwartet man bei erfolgreicher Suche in einer Hashtabelle mit Verkettung und Füllfaktor α?
  55. 55.Was bringt eine monotone Deque bei der Aufgabe „Maximum im Schiebefenster“?
  56. 56.Wie hält man den laufenden Median eines Streams effizient?
  57. 57.Was bedeutet es, dass ein Problem NP-vollständig ist?
  58. 58.Warum ist die Rekursionstiefe von Quicksort ein Problem, und wie begrenzt man sie?
  59. 59.Welche Struktur würdest du für eine Autovervollständigung nutzen, die Vorschläge nach Beliebtheit ordnet?
  60. 60.Welches Problem löst ein Ringpuffer mit Head- und Tail-Index für eine Queue mit hohem Durchsatz?
  61. 61.Was ist die untere Schranke für das Finden eines Elements in einem unsortierten Array, und warum?
  62. 62.Warum bevorzugt man bei manchen Rätseln DFS gegenüber BFS, obwohl BFS kürzeste Lösungen findet?
  63. 63.Welche Komplexität hat Array.prototype.sort in V8 bei einem bereits sortierten Array?
  64. 64.Wie findet man in einem Array mit Duplikaten alle Paare mit gegebener Summe, ohne doppelt zu zählen?
  65. 65.Welche Aussage über Rekursion und Call Stack in JavaScript stimmt?
  66. 66.Was ist der Hauptvorteil von Dijkstra mit Fibonacci-Heap gegenüber einem binären Heap?
  67. 67.Wie prüft man in O(n), ob zwei Wörter eine Bearbeitung auseinanderliegen?
  68. 68.Was bringt Randomisierung für Quicksort?
  69. 69.Welcher Ansatz zählt Inversionen (Paare i < j mit a[i] > a[j]) in O(n log n)?
  70. 70.Warum verarbeitet eine gute Hashfunktion für Strings jedes Zeichen?
  71. 71.Was beantwortet die Struktur „Sparse Table“ in O(1)?
  72. 72.Was ist der Hauptgrund, eine Adjazenzmatrix Adjazenzlisten vorzuziehen?
  73. 73.Ein Algorithmus läuft in O(n), legt aber in jeder Iteration einer heißen Schleife ein neues Array an. Was ist das wahrscheinliche Problem in der Praxis?
  74. 74.Was unterstützt der Trick mit „zwei Heaps“ gegenüber einem balancierten BST nicht effizient?
  75. 75.Warum ist Array.prototype.indexOf innerhalb von filter in Code-Reviews ein häufiges verstecktes O(n²)?