20 articles
A complete tour of the seven advanced graph patterns FAANG interviewers test most: Kruskal and Prim MST, Tarjan SCC, bridges and articulation points, Floyd-Warshall all-pairs shortest path, Bellman-Ford with negative cycles, and A-star heuristic search. One pattern recognition guide that turns every advanced graph problem into a routine implementation.
LC 1584 Minimum Cost to Connect All Points and LC 1135 Connecting Cities are MST problems straight from the FAANG playbook. Master Kruskal: sort edges by weight, accept the cheapest edge that does not form a cycle using Union-Find, and prove correctness via the cut property in one sentence.
Master Prim's algorithm for Minimum Spanning Tree: grow a single tree from any starting vertex by repeatedly attaching the cheapest crossing edge using a min-heap. The dense-graph counterpart to Kruskal, asked at Google, Amazon, and Microsoft.
Master Tarjan's SCC algorithm: a single DFS pass with discovery times, low-link values, and an explicit stack to identify all strongly connected components in O(V + E). The interview gold standard for directed graph decomposition, asked at Google, Meta, and Uber.
Use Tarjan's low-link technique to find every bridge (critical edge) and articulation point (cut vertex) in an undirected graph in O(V + E). The interview pattern behind LeetCode 1192 Critical Connections, asked at Google, Meta, and Amazon.
Master the Floyd-Warshall algorithm: a triple-nested DP that computes shortest paths between every pair of vertices in O(V^3), supports negative edges, and detects negative cycles. The interview workhorse for dense graphs and small V, asked at Google, Amazon, and Microsoft.
Master Bellman-Ford: relax every edge V-1 times to compute single-source shortest paths even with negative edges, and detect negative cycles in one extra pass. The algorithm behind LeetCode 787 Cheapest Flights Within K Stops, asked at Google, Amazon, and Meta.
Master A* search: a heuristic-guided best-first search that finds optimal shortest paths far faster than Dijkstra by combining actual distance g(n) with an admissible estimate h(n). The interview pattern behind LeetCode 1091 Shortest Path in Binary Matrix and the algorithm powering Google Maps, game AI, and robotics navigation.
Master advanced topological sort: DFS post-order, Kahn's BFS algorithm, cycle detection, lexicographically smallest order, and parallel level scheduling. The pattern behind LeetCode 210 Course Schedule II, asked at Google, Amazon, and Meta.
Master advanced Dijkstra: state augmentation, K-stop limits, two-cost optimisation, k-th shortest paths, and modified relaxation. The interview pattern behind LeetCode 787, 1928, and 1976, asked at Google, Amazon, and Meta.
Master bipartite checking and graph coloring: a single BFS or DFS pass that 2-colors a graph and proves it is bipartite, or finds an odd cycle. The pattern behind LeetCode 785 Is Graph Bipartite and LeetCode 886 Possible Bipartition, asked at Google, Meta, and Amazon.
Master LeetCode 1584 Min Cost to Connect All Points: model the n^2 implicit edges as a complete graph, then run Prim's MST in O(n^2) without ever materialising the edge list. A FAANG-favourite interview question at Amazon, Google, and Meta that tests whether you can spot a Minimum Spanning Tree behind a geometry prompt.
Solve the bottleneck shortest path problem: find a route from source to destination that minimises the maximum edge weight on the path. Combines binary search on the answer with BFS connectivity checks in O((V+E) log W) — a FAANG interview pattern asked at Google and Amazon, and the foundation behind LeetCode 1102 Path With Maximum Minimum Value.
Master LeetCode 1976 Number of Ways to Arrive at Destination: extend Dijkstra to count the number of distinct shortest paths simultaneously, returning the count modulo 10^9+7. A FAANG-favourite shortest-path counting interview question asked at Google, Amazon, and Meta.
Master LeetCode 1192 Critical Connections in a Network: a textbook Tarjan bridge-finding algorithm using DFS with discovery times and low-link values to detect every edge whose removal disconnects the graph. A FAANG hard graph interview classic at Google, Amazon, and Meta.
Master LeetCode 332 Reconstruct Itinerary using Hierholzer's algorithm: a single DFS that traverses every edge exactly once and assembles an Eulerian path via post-order insertion. A FAANG hard interview classic asked at Google, Meta, and Amazon, and the foundational pattern for de Bruijn sequences and DNA fragment assembly.
Master LeetCode 778 Swim in Rising Water by reducing a grid puzzle to a minimax shortest-path problem. Solve it three ways — Dijkstra with max-relax, binary search plus BFS, and Kruskal-style union-find — and learn when each approach wins. A FAANG hard interview classic at Google, Amazon, and Meta.
Master longest path in a directed acyclic graph (DAG): a polynomial-time graph-DP that combines topological sort with memoised DFS. The same template solves LeetCode 329 Longest Increasing Path, course planning with prerequisites, and critical-path scheduling — a FAANG interview pattern at Google, Amazon, and Meta.
A complete walkthrough of network flow for FAANG interviews: the max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp BFS-augmenting paths, residual graphs, and practical applications including bipartite matching and project selection. Asked at Google, Amazon, and Meta as a senior-level systems-design-meets-algorithms screen.
Eighteen advanced graph problems collapsed into one decision tree. Match the problem cue to the algorithm in seconds: MST, SCC, bridges, Floyd-Warshall, Bellman-Ford, A-star, topological sort, Eulerian paths, and max flow with complexity bounds you can quote on demand.