Bestehe dein Coding-Interview
Finden Sie bei einer Reihe von Aktivitäten zusammen mit der Start- und Endzeit jeder Aktivität die maximale Anzahl von Aktivitäten, die von einer einzelnen Person ausgeführt werden, unter der Annahme, dass eine Person nur an einer einzigen Aktivität gleichzeitig arbeiten kann.
Gegeben eine Menge von Scheitelpunkten V in einem gewichteten Graphen, wo seine Kanten gewichten w(u, v) negativ sein kann, finden Sie die kürzesten Pfadgewichte d(s, v) aus jeder Quelle s für alle Ecken v in der Grafik vorhanden. Wenn das Diagramm einen Zyklus mit negativem Gewicht enthält, melden Sie ihn.
Gegeben ein Quellscheitelpunkt s aus einer Menge von Ecken V in einem gewichteten Graphen, wo seine Kanten gewichten w(u, v) negativ sein kann, finden Sie die kürzesten Pfadgewichte d(s, v) aus Quelle s für alle Ecken v in der Grafik vorhanden. Wenn das Diagramm einen Zyklus mit negativem Gewicht enthält, melden Sie ihn.
Gegeben ein Quellscheitelpunkt s aus einer Menge von Ecken V in einem gewichteten Graphen, in dem alle seine Kanten gewichten w(u, v) nichtnegativ sind, finden Sie die kürzesten Pfadgewichte d(s, v) aus Quelle s für alle Ecken v in der Grafik vorhanden.
Konstruieren Sie aus einem gegebenen ungerichteten, zusammenhängenden und gewichteten Graphen einen minimalen Spannbaum unter Verwendung des Kruskal-Algorithmus.
Überprüfen Sie bei einem ungerichteten verbundenen Graphen, ob er einen Zyklus enthält oder nicht, indem Sie den union-find-Algorithmus verwenden.
Finden Sie auf einem Schachbrett die kürzeste Entfernung (Mindestschrittzahl), die ein Springer zurücklegt, um ein bestimmtes Ziel von einer bestimmten Quelle aus zu erreichen.
Dieser Beitrag erklärt die Funktionsweise der Datenstruktur mit disjunkten Mengen (auch Union-Find-Datenstruktur genannt). Eine disjunkte Menge ist eine Datenstruktur, die eine Menge von Elementen verfolgt, die in eine Anzahl disjunkter (nicht überlappender) Teilmengen unterteilt sind.
Überprüfen Sie bei einem gegebenen ungerichteten zusammenhängenden Graphen, ob der Graph zweikantenzusammenhängend ist oder nicht. Ein verbundener Graph ist zweikantenverbunden, wenn er verbunden bleibt, wenn Kanten entfernt werden.
Der transitive Abschluss für einen Digraphen G ist ein Digraph G’ mit Rand (i, j) entsprechend jedem gerichteten Pfad aus i zu j in G. Der resultierende Digraph G’ Die Darstellung in Form der Adjazenzmatrix wird Konnektivitätsmatrix genannt.
Geben Sie einen gegebenen gerichteten azyklischen Graphen (DAG) in topologischer Reihenfolge mit einem topologischen Sortieralgorithmus aus. Wenn der DAG über mehr als eine topologische Reihenfolge verfügt, geben Sie eine davon aus.
Finden Sie die Mindestanzahl an Würfen, die erforderlich ist, um ein bestimmtes Snake-and-Ladder-Spiel zu gewinnen. Zum Beispiel erfordert das folgende Spiel mindestens 7 Würfelwürfe, um zu gewinnen.