Coding-Fragenkatalog fürs Vorstellungsgespräch

Muster: Zwei Zeiger·Komplexität: Zeit O(n), Speicher O(1)

Setze je einen Zeiger an beide Enden des sortierten Arrays. Ist die Summe zu klein, rückt der linke Zeiger vor; ist sie zu groß, der rechte zurück. Die Sortierung garantiert, dass du nie ein gültiges Paar überspringst – genau diese Invariante sollst du laut aussprechen.

Muster: Hashmap / Zählen·Komplexität: Zeit O(n), Speicher O(1) bei festem Alphabet

Zähle die Zeichenhäufigkeiten des ersten Strings, verringere sie beim Durchlaufen des zweiten und prüfe, ob alle Zähler wieder bei null sind. Nenne die Folgefrage, bevor sie gestellt wird: Für vollständiges Unicode reicht ein festes Array mit 26 Plätzen nicht mehr – nimm eine Hashmap.

Muster: Langsamer und schneller Zeiger nach Floyd·Komplexität: Zeit O(n), Speicher O(1)

Bewege einen Zeiger um einen Knoten und einen anderen um zwei weiter; treffen sie sich irgendwann, gibt es einen Zyklus. Sei auf die klassische Folgefrage vorbereitet – den Eintrittspunkt des Zyklus finden: einen Zeiger auf den Kopf zurücksetzen und beide um je einen Schritt bewegen, bis sie sich wieder treffen.

Muster: Boyer–Moore-Voting·Komplexität: Zeit O(n), Speicher O(1)

Führe einen Kandidaten und einen Zähler: bei Übereinstimmung erhöhen, bei Abweichung verringern, den Kandidaten ersetzen, wenn der Zähler null erreicht. Weil das Mehrheitselement mehr als n/2-mal vorkommt, überlebt es immer. Zu erklären, WARUM es überlebt, ist das eigentliche Interview.

Muster: Ein Durchlauf, laufendes Minimum·Komplexität: Zeit O(n), Speicher O(1)

Merke dir den bisher niedrigsten Preis und den besten Gewinn, wenn du heute verkaufst. Ein Durchlauf, zwei Variablen. Es ist die kleinste Form der Idee „den besten Präfix-Zustand mitführen“, die später in Kadanes Algorithmus auftaucht – diesen Zusammenhang zu benennen bringt Punkte.

Muster: Sortieren + linearer Durchlauf·Komplexität: Zeit O(n log n), Speicher O(n)

Sortiere die Intervalle nach ihrem Start und geh sie dann durch: Beginnt das aktuelle Intervall nach dem Ende des zuletzt zusammengeführten, häng es an; sonst verlängere dessen Ende auf das Maximum beider. Das Sortieren leistet die eigentliche Arbeit – sag das, und behandle die Randfälle des Vergleichs (Intervalle, die sich berühren) korrekt.

Muster: Hash-Set + Sequenzanfänge·Komplexität: Zeit O(n), Speicher O(n)

Leg jede Zahl in ein Set; fang nur bei Zahlen an zu zählen, deren Vorgänger fehlt (Sequenzanfänge), und lauf dann vorwärts. Jedes Element wird höchstens zweimal besucht – so verteidigst du die O(n)-Behauptung gegen den Einwand „aber da ist doch eine verschachtelte Schleife“.

Muster: Präfix- und Suffixprodukte·Komplexität: Zeit O(n), zusätzlicher Speicher O(1) ohne die Ausgabe

Zwei Durchläufe ohne Division: Fülle zuerst jeden Platz mit dem Produkt aller Elemente links davon, dann geh von rechts durch und multipliziere das Produkt aller Elemente rechts davon hinein. Antworten mit Division scheitern an den Fällen mit Nullen – Interviewer verbieten sie meist ausdrücklich.

Muster: Invariante mit Hilfs-Stack·Komplexität: O(1) pro Operation, Speicher O(n)

Führe neben dem Werte-Stack einen Min-Stack, dessen oberstes Element immer das Minimum von allem darunter ist – lege min(neu, aktuelles oberstes) ab und entferne im Gleichschritt. Das ist eine Designfrage: Bewertet wird die Invariante, nicht die Menge an Code.

Muster: Hashmap + doppelt verkettete Liste·Komplexität: O(1) pro get/put, Speicher O(capacity)

Eine Hashmap liefert O(1)-Zugriff auf die Knoten einer doppelt verketteten Liste, die nach letzter Nutzung geordnet ist; bei einem Zugriff wandert ein Knoten an den Kopf, bei Überlauf wird am Ende entfernt. Sentinel-Knoten für Kopf und Ende beseitigen jeden Randfall mit Null-Prüfungen – erwähne sie, bevor du anfängst zu programmieren.

Muster: Flood Fill mit BFS/DFS im Raster·Komplexität: Zeit O(rows × cols)

Durchlaufe das Raster; jede unbesuchte Landzelle startet einen Flood Fill (DFS oder BFS), der die ganze Insel als besucht markiert, und du zählst die Starts. Nenne deine Strategie fürs Markieren (an Ort und Stelle „versenken“ oder separates Set) und das Risiko der Rekursionstiefe bei riesigen Rastern – das ist das Signal für Seniorität.

Muster: Topologische Sortierung / Zykluserkennung·Komplexität: Zeit O(V + E)

Modelliere die Voraussetzungen als gerichteten Graphen; die Frage „Kann man alle Kurse abschließen?“ ist genau die Frage „Ist der Graph azyklisch?“. Kahns Algorithmus (wiederholt Knoten mit Eingangsgrad null entfernen) oder DFS mit drei Farben funktionieren beide – wähle einen und erkläre, warum ein übrig gebliebener Knoten einen Zyklus bedeutet.

Muster: BFS mit Momentaufnahme pro Ebene·Komplexität: Zeit O(n), Speicher O(width)

BFS mit einer Queue, aber halte zu Beginn jeder Runde die Länge der Queue fest, damit du pro Ebene eine Liste ausgibst. Dieser Trick mit der festgehaltenen Länge ist der wiederverwendbare Kern – Zickzack-Durchlauf und Right Side View sind dieselbe Schleife mit einem anderen Sammelschritt.

Muster: Grenzen weitergeben / Inorder·Komplexität: Zeit O(n), Speicher O(height)

Rekursion mit einem erlaubten (min, max)-Fenster, das sich bei jedem Schritt verengt – oder ein Inorder-Durchlauf mit der Prüfung, dass die Folge streng steigt. Die klassische Falle ist, nur Kinder mit ihrem Elternknoten zu vergleichen; konstruiere das Gegenbeispiel selbst, bevor der Interviewer es tut.

Muster: Hash-Zuordnung in beide Richtungen (Bijektion)·Komplexität: Zeit O(n), Speicher O(n)

Ordne Musterzeichen Wörtern zu UND Wörter zurück den Zeichen – eine Richtung allein akzeptiert das Muster „ab“ für „dog dog“. Die Bijektion in beide Richtungen zu prüfen, ist der ganze Trick; sprich das Wort „Bijektion“ aus und behandle den Fall unterschiedlicher Längen, bevor du programmierst.

Muster: Zykluserkennung in einer versteckten Folge·Komplexität: O(log n) pro Schritt; Speicher O(1) mit Floyd

Ersetzt man eine Zahl immer wieder durch die Summe der Quadrate ihrer Ziffern, erreicht man entweder 1 oder gerät in eine Schleife – das ist also Linked List Cycle in Verkleidung. Erkenne die Schleife mit einem Set bereits gesehener Werte oder beeindrucke mit Floyds langsamem und schnellem Zeiger für O(1) Speicher. Die Rückführung auf Zykluserkennung zu benennen, ist der Zug, der Seniorität zeigt.

Muster: Greedy mit Beweispflicht·Komplexität: Zeit O(n), Speicher O(1)

Ist das gesamte Benzin ≥ den Gesamtkosten, gibt es eine Lösung, und sie ist eindeutig. Geh einmal durch und führe einen laufenden Tankstand; wird er negativ, kann keine Station im gescheiterten Abschnitt der Start sein – starte bei der nächsten Station neu. Das Interview ist die Begründung dieses Überspringens, nicht die Schleife selbst.

Muster: Greedy / implizite BFS-Ebenen·Komplexität: Zeit O(n), Speicher O(1)

Betrachte die Indizes, die mit k Sprüngen erreichbar sind, als BFS-Ebene: Merke dir den rechten Rand der aktuellen Ebene und die größte bisher gesehene Reichweite; wenn du über den Rand hinausgehst, erhöhe die Sprünge und setze den Rand auf diese größte Reichweite. Es als BFS ohne Queue zu formulieren, erklärt, WARUM Greedy hier optimal ist.

Muster: Linearer Merge in drei Phasen·Komplexität: Zeit O(n), Speicher O(n)

Gib die Intervalle aus, die enden, bevor das neue beginnt, nimm dann jedes überlappende Intervall in das neue auf (kleinster Start, größtes Ende) und gib den Rest aus. Die sortierte Eingabe bedeutet einen Durchlauf ohne erneutes Sortieren – stell das Merge Intervals gegenüber, falls gefragt wird, warum es hier einfacher ist.

Muster: Matrixtransformation an Ort und Stelle·Komplexität: Zeit O(n²), Speicher O(1)

Um 90° im Uhrzeigersinn drehen = transponieren und dann jede Zeile umkehren. Zwei saubere Durchläufe mit O(1) zusätzlichem Speicher sind besser, als den Vierer-Ringtausch unter Druck von Hand herzuleiten – aber sei bereit, die Koordinatenabbildung (i,j) → (j, n−1−i) zu erklären, falls der Interviewer über den Trick hinaus nachbohrt.

Muster: Markieren an Ort und Stelle mit geliehenem Speicher·Komplexität: Zeit O(m×n), Speicher O(1)

Nutze die erste Zeile und die erste Spalte als Speicher für die Markierung, welche Zeilen und Spalten genullt werden müssen, und zwei Booleans, die sich deren eigenen Zustand merken. Geh die Speicherleiter laut durch – O(mn)-Kopie → O(m+n)-Sets → O(1) mit geliehenem Speicher –, denn genau diese Leiter wird geprüft.

Muster: Sortieren / Zähl-Buckets·Komplexität: O(n log n) sortiert, O(n) mit Buckets

Sortiere absteigend und finde das größte i mit citations[i] ≥ i+1 – oder verzichte aufs Sortieren und nutze Zähl-Buckets, gedeckelt bei n, für O(n). Formuliere die Definition präzise, bevor du programmierst; die meisten Fehler bei dieser Aufgabe entstehen durch falsches Lesen von „h Veröffentlichungen mit jeweils mindestens h Zitierungen“, nicht durch den Algorithmus.

Muster: Topologische Sortierung mit ausgegebener Reihenfolge·Komplexität: Zeit O(V + E)

Derselbe Graph wie bei Course Schedule, aber jetzt zahlt sich Kahns Algorithmus aus: Die Reihenfolge, in der Knoten mit Eingangsgrad null die Queue verlassen, IST eine gültige Kursreihenfolge. Ist die ausgegebene Reihenfolge kürzer als die Zahl der Kurse, gibt es einen Zyklus – gib eine leere Liste zurück. Nenne die umgekehrte DFS-Postorder als Alternative.

Muster: Sliding Window mit Zähler für erfüllte Bedingungen·Komplexität: Zeit O(n), Speicher O(alphabet)

Erweitere den rechten Rand, bis das Fenster jedes benötigte Zeichen abdeckt (führe einen Zähler „erfüllt gegen benötigt“ mit, statt in jedem Schritt eine ganze Map zu vergleichen), dann verkleinere den linken Rand bis zum Minimum, solange das Fenster gültig bleibt, und merke dir das beste. Die Optimierung mit dem Zähler hält es bei O(n) – erkläre sie ausdrücklich.

Muster: Zwei Zeiger über laufende Maxima·Komplexität: Zeit O(n), Speicher O(1)

Das Wasser über jedem Balken ist min(max-links, max-rechts) − Höhe. Zwei Zeiger, die sich von beiden Enden nach innen bewegen, lösen jeweils die Seite mit dem niedrigeren laufenden Maximum auf, weil deren Grenze bereits feststeht. Erkläre, warum diese Gewissheit gilt – darum dreht sich die ganze Frage.