Interviewfragen zu Algorithmen und Datenstrukturen (Middle) mit Antworten

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

Diesen Test machen
  1. 1.Wie funktioniert Merge Sort?
  2. 2.Was ist der Hauptnachteil von Merge Sort auf Arrays?
  3. 3.Was ist der schlimmste Fall von Quicksort, und wann tritt er ein?
  4. 4.Warum ist Quicksort in der Praxis oft schneller als Merge Sort, trotz gleichem Durchschnitt O(n log n)?
  5. 5.Was macht das Aufteilen (Partitioning) in Quicksort?
  6. 6.Welchen Sortieralgorithmus nutzt V8 für Array.prototype.sort?
  7. 7.Warum kann kein vergleichsbasiertes Sortierverfahren im schlimmsten Fall O(n log n) schlagen?
  8. 8.Wann kann Counting Sort O(n log n) schlagen?
  9. 9.Was ist ein binärer Heap (Min-Heap)?
  10. 10.Was kosten die Hauptoperationen eines binären Heaps?
  11. 11.Wie findet man effizient die k größten Elemente eines großen Arrays?
  12. 12.Hat JavaScript eine eingebaute Priority Queue?
  13. 13.Was liefert diese binäre Suche, wenn target nicht im Array steht?
  14. 14.Warum empfiehlt man in vielen Sprachen mid = lo + Math.floor((hi - lo) / 2) statt (lo + hi) / 2?
  15. 15.Was bedeutet „binäre Suche über die Antwort“?
  16. 16.Wie findet man in O(log n) einen Wert in einem rotierten sortierten Array wie [4, 5, 6, 1, 2, 3]?
  17. 17.Was ist die Sliding-Window-Technik?
  18. 18.Längster Teilstring ohne wiederholte Zeichen: was ist die O(n)-Idee?
  19. 19.Two Sum auf einem sortierten Array: was ist der O(n)-Ansatz ohne zusätzlichen Speicher?
  20. 20.Wie führt man überlappende Intervalle wie [[1,3],[2,6],[8,10]] zusammen?
  21. 21.Wofür nutzt man einen monotonen Stack?
  22. 22.Wie setzt man eine Queue mit zwei Stacks so um, dass jede Operation amortisiert O(1) ist?
  23. 23.Welche Struktur bietet Einfügen und Entfernen in O(1) an beiden Enden?
  24. 24.Wie erkennt man mit O(1) zusätzlichem Speicher einen Zyklus in einer verketteten Liste?
  25. 25.Wie findet man die Mitte einer verketteten Liste in einem Durchlauf?
  26. 26.Wie dreht man eine einfach verkettete Liste iterativ um?
  27. 27.Wie baut man meist einen LRU-Cache mit get und put in O(1)?
  28. 28.Warum findet BFS in einem ungewichteten Graphen den kürzesten Weg?
  29. 29.Warum halten Graph-Traversierungen eine Menge visited?
  30. 30.Wie zählt man Inseln (zusammenhängende Gruppen aus 1en) in einem Gitter aus 0en und 1en?
  31. 31.Was ist eine topologische Sortierung?
  32. 32.Wie berechnet Kahns Algorithmus eine topologische Reihenfolge?
  33. 33.Wie erkennt man mit DFS einen Zyklus in einem gerichteten Graphen?
  34. 34.Was unterstützt eine Union-Find-Struktur (Disjoint Set)?
  35. 35.Wofür eignet sich ein Trie?
  36. 36.Welche Baumtraversierung besucht die Werte eines BST in sortierter Reihenfolge?
  37. 37.Wie durchläuft man einen Binärbaum Ebene für Ebene?
  38. 38.Wie berechnet man rekursiv die maximale Tiefe eines Binärbaums?
  39. 39.Welches Problem lösen selbstbalancierende Bäume (AVL, Rot-Schwarz)?
  40. 40.Welche zwei Eigenschaften machen ein Problem geeignet für dynamische Programmierung?
  41. 41.Was ist der Unterschied zwischen Memoisierung und Tabulation?
  42. 42.Treppensteigen: man kann 1 oder 2 Stufen auf einmal nehmen. Wie viele Wege gibt es, n Stufen zu steigen?
  43. 43.Warum kann ein Greedy-Algorithmus beim Wechselgeld mit Münzen [1, 3, 4] und Betrag 6 scheitern?
  44. 44.Welche Komplexität hat die DP für Wechselgeld bei Betrag A und k Münzarten?
  45. 45.Was ist die längste gemeinsame Teilfolge (LCS) zweier Strings?
  46. 46.Was misst die Levenshtein-(Edit-)Distanz?
  47. 47.Was ist die Idee von Kadanes Algorithmus für die maximale Teilarray-Summe?
  48. 48.Wie viele Teilmengen hat eine Menge mit n Elementen, und warum ist das wichtig?
  49. 49.Was ist Backtracking?
  50. 50.Wie viele Permutationen hat ein Array aus n verschiedenen Elementen?
  51. 51.Wie vermeidet man in JavaScript einen Stack Overflow bei tiefer Rekursion?
  52. 52.Welche Platzkomplexität hat eine rekursive DFS auf einem Baum der Höhe h?
  53. 53.Was passiert mit einer Hashtabelle, wenn ihr Füllfaktor zu hoch wird?
  54. 54.Was macht eine gute Hashfunktion für eine Hashtabelle aus?
  55. 55.Was nutzt die Aufgabe „Anagramme gruppieren“ meist als Map-Schlüssel?
  56. 56.Wie beantwortet man auf einem statischen Array viele Male „Summe der Elemente von i bis j“?
  57. 57.Teilarray-Summe gleich k: warum speichert man Zählungen der Präfixsummen in einer Hash-Map?
  58. 58.Was berechnet Dijkstras Algorithmus?
  59. 59.Welche Datenstruktur macht Dijkstras Algorithmus effizient?
  60. 60.Welche Komplexität hat BFS oder DFS auf einem Graphen als Adjazenzlisten?
  61. 61.Wie prüft man, ob sich ein Graph mit zwei Farben so färben lässt, dass keine Kante gleiche Farben verbindet?
  62. 62.Was macht x & (x - 1) bei einer positiven ganzen Zahl x?
  63. 63.Jede Zahl in einem Array kommt zweimal vor, außer einer. Wie findet man sie in O(n) Zeit und O(1) Speicher?
  64. 64.Welche Komplexität hat diese Funktion?
  65. 65.Welcher Algorithmus findet einen minimalen Spannbaum, indem er die günstigsten Kanten hinzufügt, die keinen Zyklus bilden?
  66. 66.Warum entspricht die Reihenfolge der Schlüssel eines JavaScript-Objekts nicht immer der Einfügereihenfolge?
  67. 67.Welche Komplexität hat die Prüfung, ob zwei Strings der Länge n gleich sind?
  68. 68.Welches Problem löst man, indem man die k neuesten Werte in einem Ringpuffer fester Größe hält?
  69. 69.Was ist die Idee „Meet in the Middle“ bei der zweiseitigen BFS?
  70. 70.Warum lassen sich Arrays meist schneller durchlaufen als verkettete Listen, obwohl beides O(n) ist?
  71. 71.Welche Zeitkomplexität hat str.split("").sort().join("") für einen String der Länge n?
  72. 72.Was macht diese Funktion, und welche Komplexität hat sie?
  73. 73.Was kostet es, einen Wert in ein sortiertes Array einzufügen und es sortiert zu halten?
  74. 74.Wie rotiert man ein Array an Ort und Stelle um k Positionen nach rechts, mit O(1) zusätzlichem Speicher?
  75. 75.Subset Sum: können einige der Zahlen target ergeben? Was ist die klassische DP-Lösung?