Interviewfragen zur topologischen Sortierung

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Was eine Frage zur topologischen Sortierung wirklich prüft

Das Wort „topologische Sortierung“ kommt in der Frage fast nie vor. Sie bekommen Kurse mit Voraussetzungen, Build-Ziele, Aufgabenlisten, ein Rezept oder ein Wörterbuch in einem fremden Alphabet, und das Interview achtet auf drei Dinge.

Sehen Sie den Graphen? Alles, was als „X muss vor Y kommen“ formuliert ist, ist eine gerichtete Kante, und die Antwort ist eine Ordnung der Knoten. Setzen Sie die Bögen richtig herum? Das ist der mit Abstand häufigste Fehler, und er erzeugt Code, der läuft, eine Ordnung liefert und verkehrt herum ist. Wissen Sie, dass Zykelprüfung und Sortierung dieselbe Berechnung sind? „Lässt sich das planen?“ und „gib mir einen Plan“ sind ein Algorithmus mit zwei verschiedenen return-Anweisungen.

Danach sind alle Varianten derselbe Durchlauf, der etwas zusätzlich mitführt: eine Ebenennummer, eine Dauer, einen Zähler, einen zweiten Graphen. Sitzt die Vorlage einmal, liegt der interessante Teil jedes dieser Probleme in der Modellierung, nicht im Code. Die Mechanik selbst behandelt der Leitfaden zur topologischen Sortierung; diese Seite handelt von den acht Fragen, die tatsächlich gestellt werden.

Jedes Rechenbeispiel unten wurde per Skript ausgeführt, bevor es aufgeschrieben wurde.

2. Die zwei Vorlagen, und wann welche gewinnt

Es gibt genau zwei Implementierungen, die man kennen sollte, und ein Interviewer akzeptiert beide. Schreiben Sie die, die Sie ohne Zögern hinbekommen, und sagen Sie, warum Sie vielleicht die andere wollen.

Kahns Algorithmus aus seiner Arbeit von 1962 ist die iterative Variante. Zählen Sie, wie viele Voraussetzungen jeder Knoten noch hat, halten Sie die mit null in einer Warteschlange und geben Sie sie aus.

from collections import deque

def kahn(n, edges):                  # edges enthält (u, v): u kommt vor v
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1                # Bögen IN v zählen
    q = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1            # u ist fertig, v braucht einen weniger
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []      # zu kurze Ausgabe bedeutet Zyklus

Die letzte Zeile trägt den ganzen Zyklustest. Erreichen manche Knoten nie Eingangsgrad null, warten sie aufeinander, und len(order) < n ist der Beweis. Beachten Sie, dass es nirgends eine visited-Menge gibt: Der Eingangsgradzähler garantiert bereits, dass jeder Knoten genau einmal ausgegeben wird.

Auf diesem Graphen beginnt die Warteschlange mit [1, 2], und die ausgegebene Ordnung ist 1, 2, 4, 0, 5, 3, 6, 7. Alle acht Knoten kommen heraus, also gibt es keinen Zyklus.

Die DFS-Version ist die andere Vorlage. Führen Sie eine Tiefensuche aus und legen Sie jeden Knoten auf eine Liste, wenn er abgeschlossen ist, und kehren Sie die Liste dann um. Die Feinheit, die Interviewer abfragen, ist die Färbung.

WHITE, GREY, BLACK = 0, 1, 2      # ungesehen, auf dem Stack, fertig

def dfs_topo(n, adj):
    colour = [WHITE] * n
    out = []
    def visit(u):
        colour[u] = GREY
        for v in adj[u]:
            if colour[v] == GREY:          # Rückwärtskante: Zyklus gefunden
                return False
            if colour[v] == WHITE and not visit(v):
                return False
        colour[u] = BLACK
        out.append(u)                      # beim VERLASSEN anhängen, nicht beim Betreten
        return True
    for v in range(n):
        if colour[v] == WHITE and not visit(v):
            return []
    return out[::-1]                       # umgekehrte Postorder

Drei Farben, keine Besucht-Menge. Eine einfache visited-Menge kann einen Bogen zurück in den aktuellen Rekursionsstack, also einen Zyklus, nicht von einem Bogen in einen bereits abgeschlossenen Zweig unterscheiden, der keiner ist. Sagen Sie diesen Satz im Interview, und die Nachfrage zur Zykelerkennung ist schon beantwortet.

Welche verwenden? Kahn, wenn das Problem Ebenen, Zähler, lexikografische Ordnung oder irgendetwas verlangt, das von der Verarbeitung der Quellen in Wellen profitiert. DFS, wenn Sie ohnehin aus einem anderen Grund eine Tiefensuche schreiben oder die umgekehrte Postorder für einen Durchlauf zu starken Zusammenhangskomponenten wollen. Beide sind O(V + E). Der eine praktische Unterschied: Die rekursive DFS braucht eine Stacktiefe proportional zur längsten Kette, was bei einer bösartigen Eingabe mit hunderttausend verketteten Aufgaben Pythons Standard-Rekursionslimit sprengt; Kahn nicht.

3. Course Schedule: Lassen sich alle Kurse abschließen?

Die Frage. Es gibt n Kurse und eine Liste von Paaren [a, b] mit der Bedeutung „um Kurs a zu belegen, müssen Sie zuerst Kurs b belegen“. Können Sie alle abschließen?

Der Modellierungsschritt ist die ganze Frage, und hier verlieren die meisten Kandidaten. Das Paar [a, b] besagt b vor a, also verläuft der Bogen b → a, und es ist indeg[a], der steigt. Wer das umdreht, erhält trotzdem eine gültige topologische Sortierung eines anderen Graphen, nichts stürzt ab, und die Antwort ist bei jedem asymmetrischen Testfall stillschweigend falsch.

def can_finish(n, prerequisites):
    edges = [(b, a) for a, b in prerequisites]   # b vor a
    return len(kahn(n, edges)) == n

Das ist alles: Sortierung ausführen, Anzahl vergleichen. Sagen Sie laut, dass ein Plan genau dann existiert, wenn der Voraussetzungsgraph azyklisch ist, denn ein Zyklus ist eine Menge von Kursen, die jeweils auf einen anderen warten.

Fügen Sie dem laufenden Graphen den Bogen 7 → 2 hinzu, und die Warteschlange beginnt nur mit Knoten 1, gibt 1 und 4 aus und ist dann leer. Sechs Knoten bleiben stecken, und das sind genau der Zyklus 2 → 0 → 3 → 6 → 7 → 2 sowie Knoten 5, der hinter ihm liegt.

Die Nachfrage: Welche Kurse sind das Problem? Die übrig gebliebenen Knoten mit Eingangsgrad ungleich null sind die Knoten auf oder hinter einem Zyklus, und das ist meist die gewünschte Antwort. Bestehen sie auf dem Zyklus selbst statt auf allem, was er blockiert, brauchen Sie die DFS-Version: Wenn Sie auf einen grauen Knoten treffen, ist der aktuelle Rekursionsstack ab diesem Knoten der Zyklus.

Die Falle. Die Bögen umdrehen. Lesen Sie das Paar vor dem Tippen laut als „a hängt von b ab, also kommt b zuerst“ und bestätigen Sie die Richtung mit dem Interviewer an einem Beispiel mit zwei Elementen.

4. Course Schedule II: eine Reihenfolge zurückgeben

Die Frage. Dieselbe Eingabe, aber geben Sie eine gültige Reihenfolge zurück, oder eine leere Liste, wenn keine existiert.

Das ist kahn unverändert, weshalb die beiden Fragen meist direkt nacheinander gestellt werden. Die einzige neue Idee müssen Sie von selbst ansprechen: Die Ordnung ist nicht eindeutig, und die Bewertung akzeptiert jede gültige.

Kahn liefert 1, 2, 4, 0, 5, 3, 6, 7 und die DFS 2, 5, 1, 4, 0, 3, 6, 7. Keine ist richtiger als die andere, und eine erschöpfende Zählung ergibt, dass dieser Graph 49 verschiedene gültige Ordnungen hat. Wird Ihre Lösung gegen eine einzige erwartete Antwort verglichen, ist der Test kaputt, nicht die Lösung.

Die Nachfrage: Geben Sie die lexikografisch kleinste Ordnung zurück. Ersetzen Sie die Warteschlange durch einen Min-Heap. In jedem Schritt entnehmen Sie den kleinsten verfügbaren Knoten statt des am frühesten eingereihten, was gierig an jeder Position den kleinstmöglichen Wert festlegt. Die Kosten steigen von O(V + E) auf O(V + E log V), und diesen Zielkonflikt benennen zu können, ist der Sinn der Nachfrage. Auf dem laufenden Graphen ist die kleinste Ordnung 1, 2, 0, 3, 4, 5, 6, 7.

Die Falle. Das Zurückgeben von order ohne die Längenprüfung. Bei einer zyklischen Eingabe geben Sie einen Teilplan zurück, der völlig plausibel aussieht, und jeder automatische Test mit Zyklus scheitert, während Ihr lokaler Lauf des Normalfalls besteht.

5. Alien Dictionary: ein Alphabet rekonstruieren

Die Frage. Sie erhalten Wörter, die nach einem unbekannten Alphabet sortiert sind. Rekonstruieren Sie eine Ordnung der Buchstaben, die mit dieser Sortierung übereinstimmt, oder melden Sie, dass keine existiert.

Nichts hier sieht nach einem Graphen aus, bis Sie bemerken, was „sortiert“ Ihnen verrät. Vergleichen Sie zwei benachbarte Wörter, finden Sie die erste Position, an der sie sich unterscheiden, und Sie haben genau eine Tatsache gelernt: Der Buchstabe des ersten Wortes kommt vor dem Buchstaben des zweiten. Alles nach dem ersten Unterschied sagt nichts aus. Dann sortieren Sie die Buchstaben topologisch.

def alien_order(words):
    adj = {c: set() for w in words for c in w}
    indeg = {c: 0 for c in adj}
    for w1, w2 in zip(words, words[1:]):
        if len(w1) > len(w2) and w1.startswith(w2):
            return ""                       # „abc“ vor „ab“ ist unmöglich
        for a, b in zip(w1, w2):
            if a != b:
                if b not in adj[a]:         # ein Duplikat nicht doppelt zählen
                    adj[a].add(b)
                    indeg[b] += 1
                break                       # nur der ERSTE Unterschied zählt
    ...                                     # dann Kahn über die Buchstaben

Drei Details in sechs Zeilen, und Interviewer prüfen alle drei. Nur benachbarte Paare. Jedes Wortpaar zu vergleichen, fügt Kanten hinzu, die die Eingabe nicht rechtfertigt. Nur die erste abweichende Position, dann break. Die Präfixregel: Ist ein Wort ein echtes Präfix des Wortes davor, widerspricht sich die Eingabe, und die Antwort ist der leere String, ganz ohne einen Graphen zu bauen.

Bei der klassischen Eingabe ["wrt", "wrf", "er", "ett", "rftt"] ergeben die Vergleiche t → f, w → e, r → t und e → r, und die Sortierung liefert "wertf". Bei ["abc", "ab"] greift die Präfixregel und liefert "". Bei ["z", "x", "z"] bilden die Kanten z → x und x → z einen Zyklus, also liefert die Längenprüfung ebenfalls "".

Die Nachfrage: Ist das zurückgegebene Alphabet das einzige? Das ist die Eindeutigkeitsfrage aus Abschnitt 7: Die Ordnung ist genau dann festgelegt, wenn die Warteschlange in jedem Schritt einen einzigen Buchstaben enthält. Jeder Buchstabe, der in keinem Vergleich vorkommt, schwebt frei, und seine Position ist beliebig.

Die Falle. Den Graphen aus den Buchstaben aufzubauen, die in Vergleichen vorkommen, statt aus jedem Buchstaben jedes Wortes. Buchstaben, die nie verglichen werden, müssen trotzdem in der Ausgabe erscheinen, und sie wegzulassen, ist der Fehler, den ein versteckter Test findet statt Ihr eigener.

6. Parallele Kurse: die minimale Anzahl von Semestern

Die Frage. Sie dürfen beliebig viele Kurse gleichzeitig belegen, solange jede Voraussetzung schon erledigt ist. Wie viele Semester braucht man mindestens?

Die Antwort ist die Anzahl der Ebenen im DAG, und die Ebene eines Knotens ist um eins größer als die größte Ebene unter seinen Vorgängern. Führen Sie diese Zahl im selben Durchlauf mit.

def min_semesters(n, edges):
    order = kahn(n, edges)
    if len(order) != n:
        return -1                          # ein Zyklus: endet nie
    level = [1] * n
    for u in order:                        # jeder Vorgänger von u steht fest
        for v in adj[u]:
            level[v] = max(level[v], level[u] + 1)
    return max(level)

Weil die Schleife in topologischer Ordnung läuft, hat jeder Vorgänger von u bereits beigetragen, bevor u gelesen wird, und genau diese Eigenschaft sorgt dafür, dass ein Durchlauf genügt. Auf dem laufenden Graphen sind die Ebenen {1, 2}, dann {0, 4, 5}, dann {3}, dann {6}, dann {7}, also ist die Antwort 5 Semester.

Die Nachfrage: Was, wenn Sie höchstens k Kurse pro Semester belegen dürfen? Die einfache Antwort bricht zusammen. Unbegrenzte Parallelität ist linear, weil es optimal ist, gierig alles Verfügbare zu nehmen; die Breite zu begrenzen, macht daraus Scheduling mit Vorrangbeschränkungen auf k Maschinen, was im Allgemeinen NP-schwer ist. Zwei identische Maschinen mit Einheitsaufgaben sind der klassische lösbare Fall, 1972 von Coffman und Graham gelöst. Zu erkennen, dass die Nachfrage die Komplexitätsklasse wechselt, statt an der Schleife herumzuflicken, ist das, worauf der Interviewer hört.

Die Falle. Eine Ebene zuzuweisen, wenn ein Knoten zum ersten Mal erreicht wird, als wäre das eine gewöhnliche BFS von den Quellen. Ein Knoten muss auf seinen langsamsten Vorgänger warten, also ist die Ebene ein Maximum und keine erste Ankunft. Die Variante als BFS in Wellen funktioniert nur, wenn Sie jeweils eine ganze Schicht entnehmen und einen Knoten nie ansehen, bevor sein Eingangsgrad null erreicht.

7. Ist die Ordnung eindeutig? Sequenzrekonstruktion

Die Frage. Entscheiden Sie für einen DAG, ob er genau eine gültige topologische Ordnung hat. Die übliche Verpackung ist die Sequenzrekonstruktion: Sie erhalten eine Folge und eine Menge von Teilfolgen und sollen entscheiden, ob die Folge die einzige ist, die mit ihnen übereinstimmt.

Der Test ist eine Zeile in Kahns Schleife.

    while q:
        if len(q) > 1:
            return False              # es gab eine Wahl, die Reihenfolge ist nicht erzwungen
        u = q.popleft()
        ...

Enthält die Warteschlange jemals zwei Knoten, sind beide verfügbar, und jeder kann als Nächstes kommen, also gibt es mindestens zwei gültige Ordnungen. Enthält sie in jedem Schritt genau einen, wurde nie eine Wahl getroffen, und die Ordnung ist festgelegt.

Es gibt eine zweite, gleichwertige Formulierung, die Eindruck macht: Die Ordnung ist genau dann eindeutig, wenn aufeinanderfolgende Knoten darin durch einen Bogen verbunden sind, also wenn die topologische Ordnung ein Hamiltonpfad im DAG ist. Beide Formulierungen lassen sich in O(V + E) prüfen, und die Hamiltonpfad-Version zu nennen, zeigt, dass Sie verstehen, warum Eindeutigkeit eine strukturelle Eigenschaft ist und kein Zufall der Warteschlange.

Auf dem laufenden Graphen sind die Warteschlangengrößen bei den acht Entnahmen 2, 2, 3, 2, 2, 1, 1, 1. Schon der erste Schritt bietet die Wahl zwischen 1 und 2, also ist die Ordnung nicht eindeutig, was die 49 gültigen Ordnungen aus Abschnitt 4 bestätigen. Auf der Kette 0 → 1 → 2 → 3 sind die Größen 1, 1, 1, 1, und die Ordnung ist festgelegt.

Die Nachfrage: die Sequenzrekonstruktion selbst. Bauen Sie den Graphen aus aufeinanderfolgenden Paaren jeder Teilfolge, führen Sie dann die obige Prüfung aus und verifizieren Sie zusätzlich, dass die ausgegebene Ordnung gleich der gegebenen Folge ist. Beide Bedingungen sind nötig: Eine eindeutige Ordnung, die von der übergebenen Folge abweicht, ist trotzdem ein „Nein“.

Die Falle. Die Größe der Warteschlange nur einmal zu Beginn zu prüfen. Ein Graph kann mit einer einzigen Quelle beginnen und drei Schritte später verzweigen, also muss der Vergleich in jeder Iteration laufen. Gut zu wissen: „Jede Ebene enthält genau einen Knoten“ ist ein gleichwertiger Test, weil eine festgelegte Ordnung die Ebenen zu einer strikten Kette macht. In Ebenen zu denken, ist also nicht falsch, es kostet nur einen zweiten Durchlauf, um sie zu berechnen.

8. Der längste Pfad und der kritische Pfad

Die Frage. Jede Aufgabe dauert eine bekannte Anzahl von Tagen und kann erst beginnen, wenn ihre Voraussetzungen erledigt sind. Wann endet das Projekt, und welche Aufgaben entscheiden darüber?

Das ist das Problem des längsten Pfades, und auf einem allgemeinen Graphen ist es NP-schwer. Auf einem DAG ist es linear, und der Grund ist die topologische Ordnung: Jeder Vorgänger eines Knotens ist endgültig, bevor dieser Knoten gelesen wird, also erledigt ein einziger Vorwärtsdurchlauf die Sache.

def critical_path(n, edges, dur):
    order = kahn(n, edges)
    finish = list(dur)                     # frühestes Ende, wenn nichts blockiert
    prev = [-1] * n
    for u in order:
        for v in adj[u]:
            if finish[u] + dur[v] > finish[v]:
                finish[v] = finish[u] + dur[v]
                prev[v] = u                # merken, wer die Verzögerung erzwang
    end = max(range(n), key=lambda v: finish[v])
    path = []
    while end != -1:
        path.append(end); end = prev[end]
    return max(finish), path[::-1]

Geben Sie dem laufenden Graphen die Dauern 3, 2, 4, 5, 1, 2, 6, 3 für die Knoten 0 bis 7, und die frühesten Endzeiten ergeben sich als 7, 2, 4, 12, 3, 6, 18, 21. Das Projekt dauert 21 Tage, und der kritische Pfad ist 2 → 0 → 3 → 6 → 7, dessen Dauern sich zu genau 21 addieren. Diese Kette meint ein Manager mit „dem kritischen Pfad“: Verschiebt sich eine Aufgabe darauf um einen Tag, verschiebt sich das ganze Projekt um einen Tag, während Aufgabe 5 Puffer hat und tagelang treiben kann, bevor es jemand merkt. Das ist die Methode von Kelley und Walker aus dem Jahr 1959, und ihren Namen laut zu sagen, kostet nichts.

Die Nachfrage: stattdessen der kürzeste Pfad. Ändern Sie den Vergleich zu <, und Sie haben kürzeste Wege von einer Quelle auf einem DAG, in O(V + E), und es funktioniert mit negativen Gewichten, was Dijkstra nicht kann. Wann immer ein Interviewer negative Kanten auf einem azyklischen Graphen erwähnt, ist das die Antwort, nicht Bellman-Ford. Vergleichen Sie mit dem allgemeinen Fall unter Kürzeste-Wege-Algorithmen.

Die Falle. In der falschen Reihenfolge zu relaxieren. Über die Knoten 0 bis n-1 statt über die topologische Ordnung zu iterieren, ergibt einen Wert, der von der Nummerierung abhängt: Auf diesem Graphen meldet es stillschweigend 17 statt 21, weil Knoten 0 gelesen wird, bevor Knoten 2 zu ihm beigetragen hat. Der ganze Sinn der topologischen Ordnung ist, dass sie einen Durchlauf ausreichen lässt.

9. Eventual Safe States: den umgekehrten Graphen sortieren

Die Frage. Ein Knoten ist sicher, wenn jeder von ihm ausgehende Pfad einen Endknoten erreicht, man also nie in einem Zyklus stecken bleiben kann. Geben Sie alle sicheren Knoten aufsteigend zurück.

Vorwärts formuliert ist das umständlich. Kehren Sie jeden Bogen um, und es wird zu einer topologischen Sortierung: Schälen Sie die Knoten mit Ausgangsgrad null ab, also die Endknoten, und jedes Mal, wenn der verbleibende Ausgangsgrad eines Knotens null erreicht, waren alle seine Nachfolger sicher, also ist er es auch.

def safe_nodes(graph):
    n = len(graph)
    rev = [[] for _ in range(n)]
    outdeg = [len(graph[u]) for u in range(n)]
    for u in range(n):
        for v in graph[u]:
            rev[v].append(u)
    q = deque(v for v in range(n) if outdeg[v] == 0)   # Endknoten
    safe = []
    while q:
        u = q.popleft()
        safe.append(u)
        for p in rev[u]:
            outdeg[p] -= 1
            if outdeg[p] == 0:
                q.append(p)
    return sorted(safe)

Es ist Kahns Algorithmus mit Ausgangsgrad statt Eingangsgrad und umgekehrten Bögen, und das sollte man ausdrücklich sagen, weil es zeigt, dass Sie die Vorlage unter einer Verkleidung erkennen. Im Standardbeispiel [[1,2], [2,3], [5], [0,5], [5], [], []] ist die Antwort [2, 4, 5, 6]: Die Knoten 5 und 6 sind Endknoten, 2 und 4 führen nur in sie hinein, und 0, 1 und 3 liegen auf dem Zyklus 0 → 1 → 3 → 0.

Die Nachfrage: Machen Sie es stattdessen mit DFS. Wieder drei Farben. Ein Knoten ist sicher, wenn kein Bogen von ihm einen grauen Knoten erreicht, und Sie können das Ergebnis pro Knoten memoisieren, sodass das Ganze linear bleibt. Interviewer wollen oft beides hören, weil Kandidaten die Version mit dem umgekehrten Graphen selten selbst finden.

Die Falle. Zu antworten „die Knoten, die auf keinem Zyklus liegen“. Knoten 3 liegt nach dieser Lesart auf keinem eigenen Zyklus, hat aber einen Bogen in den Zyklus über 0 und ist daher unsicher. Sicherheit betrifft jeden Pfad vom Knoten aus, nicht den Knoten selbst.

10. Elemente nach Gruppen sortieren: zwei Ebenen zugleich

Die Frage. Elemente gehören zu Gruppen, manche Elemente müssen vor anderen kommen, und Elemente derselben Gruppe müssen in der Ausgabe zusammenhängend stehen. Geben Sie eine gültige Ordnung oder eine leere Liste zurück.

Das ist die schwere Variante, und die Einsicht ist klein: Führen Sie zwei topologische Sortierungen aus. Eine über die Gruppen, mit einem Bogen zwischen Gruppen, wann immer ein Element der einen vor einem Element der anderen kommen muss, und eine über die Elemente innerhalb jeder Gruppe. Verketten Sie dann die Gruppen in Gruppenordnung, jede gefüllt mit ihren eigenen sortierten Elementen.

Der einzige knifflige Teil sind die Elemente ohne Gruppe. Ein Element mit Gruppe -1 ist durch keine Gruppierung eingeschränkt, also geben Sie jedem eine neue, eigene Gruppe. Sie stattdessen alle in eine einzige Gruppe zu legen, ist die klassische falsche Antwort: Das zwingt unabhängige Elemente zusammen und kann eine lösbare Instanz unlösbar machen.

Scheitert eine der beiden Sortierungen, scheitert die ganze Instanz, also läuft die Längenprüfung zweimal. Die Komplexität bleibt O(V + E) über beide Durchläufe, da jedes Element und jede Abhängigkeit nur eine konstante Anzahl von Malen berührt wird.

Die Nachfrage: Ist ein Kurs Voraussetzung eines anderen? Das ist Course Schedule IV, und hier ist Erreichbarkeit statt einer Ordnung gefragt. Verarbeiten Sie die Knoten in topologischer Ordnung und vereinigen Sie die Erreichbarkeitsmenge jedes Knotens in seine Nachfolger, mit Bitsets: O(V × E / 64) in der Praxis, und die topologische Ordnung garantiert, dass eine Menge vollständig ist, bevor sie weitergegeben wird.

Die Falle. Die Gruppen zu sortieren und zu vergessen, dass eine Gruppe über zwei Elemente in verschiedenen Gruppen auch einen Zyklus mit sich selbst bilden kann. Bauen Sie den Gruppengraphen aus Elementabhängigkeiten nur dann, wenn sich die beiden Gruppen unterscheiden, sonst erzeugen Sie Schleifen, die die Sortierung grundlos scheitern lassen.

11. Die Komplexitätsantworten

Halten Sie diese bereit, denn sie werden wörtlich gefragt, und die Antwort ist kurz.

Zwei Dinge sollten Sie ungefragt ergänzen. Erstens wird Ihnen der Graph meist nicht als Adjazenzliste gegeben: Er kommt als Liste von Paaren, und die Liste aufzubauen kostet ebenfalls O(V + E), also ist eine Schranke, die den Aufbau ignoriert, falsch. Zweitens ist eine topologische Sortierung keine Vergleichssortierung und nicht an O(n log n) gebunden: Sie ist linear, gerade weil die Eingabe die Ordnungsbedingungen schon liefert, statt dass Sie sie entdecken müssen.

Die rekursive DFS-Version braucht im schlimmsten Fall außerdem O(V) Stacktiefe, und das ist eine echte Grenze, keine theoretische. Eine Kette von 100.000 Aufgaben erschöpft Pythons Standard-Rekursionslimit von 1.000 lange bevor sie den Speicher erschöpft.

12. Fehler, an denen das Interview scheitert

Sortiert nach Häufigkeit; die ersten zwei erklären die meisten abgelehnten Lösungen.

• Die Bögen verkehrt herum bauen. Das Paar [a, b] in Course Schedule bedeutet b vor a. Umgedreht liefert der Code trotzdem eine Ordnung, nur eben eine für das gespiegelte Problem. Lesen Sie das Paar vor dem Tippen laut vor.
• Die Prüfung len(order) == V weglassen. Ohne sie liefert eine zyklische Eingabe einen Teilplan, der gut aussieht. Die Anzahl ist der Zyklustest, die Ordnung das Nebenprodukt.
• In der DFS-Version eine Besucht-Menge verwenden. Zwei Zustände können eine Rückwärtskante nicht von einem Bogen in einen abgeschlossenen Zweig unterscheiden, also übersehen Sie Zyklen oder erfinden welche. Drei Farben, jedes Mal.
• Knoten ohne Kanten verlieren. Den Graphen nur aus der Paarliste zu bauen, verwirft stillschweigend jeden Kurs ohne Voraussetzungen und ohne abhängige Kurse. Gehen Sie von der Knotenzahl aus, die Sie erhalten haben.
• Ebenen bei der ersten Ankunft zuweisen. Ein Knoten wartet auf seinen langsamsten Vorgänger, also ist seine Ebene ein Maximum über die Vorgänger, nicht der erste Wert, der ihn erreicht.
• Außerhalb der topologischen Ordnung relaxieren. Die Durchläufe für längsten und kürzesten Pfad sind nur korrekt, weil jeder Vorgänger endgültig ist, wenn ein Knoten gelesen wird. Stattdessen über die Knotenindizes zu iterieren, liefert stillschweigend eine kleinere Zahl.
• Doppelte Abhängigkeiten doppelt zählen. Kann die Eingabe ein Paar wiederholen, deduplizieren Sie entweder vor dem Zählen der Eingangsgrade oder dekrementieren Sie einmal pro gespeichertem Bogen. Ein Duplikat an einer Stelle zu zählen und an der anderen nicht, lässt einen Knoten dauerhaft bei Eingangsgrad eins hängen.
• Behaupten, die Ordnung sei eindeutig. Das ist sie selten, und es zu behaupten, lädt zu der Nachfrage ein, auf die Sie nicht vorbereitet sind. Sagen Sie „eine gültige Ordnung“ und bieten Sie den Eindeutigkeitstest an, falls er gewünscht ist.
• Nicht nach der Eingabe fragen. Können sich Abhängigkeiten wiederholen? Kann ein Kurs von sich selbst abhängen? Sind die Knoten-IDs dichte ganze Zahlen oder beliebige Strings? Jede Antwort ändert die ersten zehn Zeilen, die Sie schreiben.

Die Gewohnheit, die die meisten davon verhindert: Sagen Sie, bevor Sie etwas schreiben, in welche Richtung die Bögen zeigen und was die Antwort ist, wenn die Sortierung zu kurz ausfällt. Können Sie beides nicht in einem Satz sagen, sind Sie noch nicht bereit zu tippen.

14. Literatur

Die Arbeiten, die diese Techniken eingeführt haben, und die Lehrbücher, die sie analysieren, in chronologischer Reihenfolge.

1. Kelley, J. E. und Walker, M. R. (1959). “Critical-path planning and scheduling.” Proceedings of the Eastern Joint Computer Conference, 160–173.
2. Kahn, A. B. (1962). “Topological sorting of large networks.” Communications of the ACM, 5(11), 558–562.
3. Knuth, D. E. (1968). The Art of Computer Programming, Volume 1: Fundamental Algorithms, Abschnitt 2.2.3. Addison-Wesley.
4. Coffman, E. G. und Graham, R. L. (1972). “Optimal scheduling for two-processor systems.” Acta Informatica, 1(3), 200–213.
5. Tarjan, R. E. (1972). “Depth-first search and linear graph algorithms.” SIAM Journal on Computing, 1(2), 146–160.
6. Tarjan, R. E. (1976). “Edge-disjoint spanning trees and depth-first search.” Acta Informatica, 6(2), 171–185.
7. Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms, 3. Auflage, Abschnitt 22.4. MIT Press.
8. Sedgewick, R. und Wayne, K. (2011). Algorithms, 4. Auflage, Abschnitt 4.2. Addison-Wesley.
9. McDowell, G. L. (2015). Cracking the Coding Interview, 6. Auflage. CareerCup.
10. Skiena, S. S. (2020). The Algorithm Design Manual, 3. Auflage, Abschnitt 5.10. Springer.