Bellman-Ford Algorithm
Finds shortest paths from a source to all nodes, handling negative edge weights. Algorithm: initialize dist[source]=0, dist[all others]=inf. Repeat V-1 times: for each edge (u, v, w): if dist[u] + w < dist[v]: dist[v] = dist[u] + w (relax edge). After V-1 iterations, all shortest paths are found (longest shortest path uses at most V-1 edges). Negative cycle detection: run one more iteration. If any dist can still be reduced: a negative cycle exists (report it). Time: O(VE) — slower than Dijkstra's O((V+E) log V) but handles negative weights. Use Bellman-Ford for: graphs with negative edges, detecting negative cycles, as a subroutine in Johnson's algorithm (all-pairs shortest paths).
Floyd-Warshall Algorithm
Finds shortest paths between all pairs of nodes (all-pairs shortest paths, APSP). dp[i][j] = shortest distance from i to j. Initialize: dp[i][i]=0, dp[i][j]=edge weight if edge exists, else infinity. Triple nested loop: for k in 0..V: for i in 0..V: for j in 0..V: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]). Interpretation: after iteration k, dp[i][j] = shortest path from i to j using only intermediate nodes 0..k. Time: O(V^3). Space: O(V^2). Use for: dense graphs where you need all-pairs distances, small graphs (V <= 1000), detecting negative cycles (if dp[i][i] < 0 for any i after the algorithm, there is a negative cycle reachable from i).
Minimum Spanning Tree: Kruskal’s Algorithm
A Minimum Spanning Tree (MST) connects all V nodes with V-1 edges of minimum total weight. Kruskal’s: sort all edges by weight. Use Union-Find to track connected components. For each edge in sorted order: if the edge connects two different components (find(u) != find(v)): add to MST, union(u, v). Stop when MST has V-1 edges. Time: O(E log E) for sorting, O(E alpha(V)) for Union-Find operations. Prim’s algorithm alternative: starts from one node, greedily adds the cheapest edge connecting the MST to a new node. Uses a min-heap. Time: O((V+E) log V). Prefer Kruskal’s for sparse graphs (fewer edges to sort); Prim’s for dense graphs (more edges, heap is more efficient).
Tarjan’s Strongly Connected Components
A Strongly Connected Component (SCC) is a maximal set of nodes where every node is reachable from every other. Tarjan’s algorithm finds all SCCs in O(V+E) using DFS. Key concepts: discovery time (disc[v], DFS order), low value (low[v], the lowest disc reachable from v’s subtree via back edges), stack (tracks the current DFS path). DFS: when visiting v: set disc[v]=low[v]=timer++, push v onto stack. For each neighbor u: if unvisited: recurse, then low[v] = min(low[v], low[u]). If u is on the stack: low[v] = min(low[v], disc[u]) (back edge). SCC root: if low[v] == disc[v], v is the root of an SCC. Pop from stack until v is popped — all popped nodes form the SCC. Applications: finding circular dependencies, 2-SAT problem, condensation graph.
Eulerian Path and Circuit
An Eulerian path visits every edge exactly once. An Eulerian circuit visits every edge exactly once and returns to the start. Conditions for undirected graph: Eulerian circuit exists if all vertices have even degree and the graph is connected. Eulerian path (not circuit) exists if exactly 2 vertices have odd degree. Hierholzer’s algorithm finds the Eulerian circuit in O(E): start at any vertex (or one with odd degree for a path). DFS using a stack: while the current vertex has unvisited edges, traverse an edge, remove it (avoid re-traversal). When stuck (no unvisited edges): add to circuit. Backtrack. Common application: “Reconstruct Itinerary” (LeetCode 332) — an Eulerian path problem on a directed graph.
Interview Tips
- Bellman-Ford vs Dijkstra: the key differentiator is negative edges. If the graph has negative weights, Dijkstra is incorrect. Use Bellman-Ford or SPFA (Shortest Path Faster Algorithm, an optimization of Bellman-Ford).
- Floyd-Warshall for V=1000 requires 10^9 operations and 8MB for the distance matrix — feasible. For V=10000: 10^12 operations — not feasible.
- Tarjan’s SCC is subtle — the low-link value and stack membership together define an SCC root. Kosaraju’s algorithm (two-pass DFS) is an easier-to-code alternative with the same complexity.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use Bellman-Ford instead of Dijkstra?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use Bellman-Ford when: (1) The graph has negative edge weights. Dijkstra incorrectly handles negative weights because once a node is ‘settled’ (popped from the heap), it is never reconsidered. A negative-weight edge to a settled node could reduce its distance further. Bellman-Ford relaxes all edges V-1 times, catching updates propagated through negative edges. (2) You need to detect negative cycles. Bellman-Ford detects them with an additional iteration: if any distance can still be reduced after V-1 iterations, a negative cycle is reachable. (3) The graph is dense and V is small. Dijkstra is O((V+E) log V); Bellman-Ford is O(VE). For dense graphs (E u2248 V^2): Dijkstra is O(V^2 log V), Bellman-Ford is O(V^3) — similar but Bellman-Ford handles negative weights. In practice: always prefer Dijkstra for non-negative weights (faster). Use Bellman-Ford only when negative weights exist.”
}
},
{
“@type”: “Question”,
“name”: “How does Floyd-Warshall find all-pairs shortest paths?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Floyd-Warshall uses dynamic programming: dp[i][j][k] = shortest path from i to j using only intermediate nodes {0, 1, …, k}. Space-optimized (omit k dimension): update dp[i][j] in-place. The key update: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]). For each intermediate node k: can we improve the i-to-j path by going through k? Iteration order: outer loop on k (intermediates), inner loops on i and j (all source-destination pairs). Correctness: after processing intermediate node k, dp[i][j] contains the shortest path using any subset of {0..k} as intermediates. After k=V-1: all intermediate nodes considered, dp[i][j] is the true shortest path. Negative cycles: after the algorithm, if dp[i][i] < 0, node i is on a negative cycle. This invalidates shortest paths through that cycle."
}
},
{
"@type": "Question",
"name": "How does Kruskal's algorithm build a minimum spanning tree?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Kruskal's: sort all edges by weight ascending. Process edges in order: for each edge (u, v, w): if find(u) != find(v) (u and v are in different connected components): add edge to MST, union(u, v). Stop when MST has V-1 edges. This greedy choice is correct because: adding the cheapest edge that connects two components can never be suboptimal (cut property of MSTs). With Union-Find (path compression + union by rank): find and union are O(u03b1(V)) u2248 O(1). Total time: O(E log E) for sorting (dominates). Comparison with Prim's: Kruskal processes edges globally (good for sparse graphs). Prim's grows the MST from a starting node (better for dense graphs — uses a heap, O((V+E) log V)). Both produce a valid MST. Kruskal's is simpler to implement with Union-Find."
}
},
{
"@type": "Question",
"name": "What is a strongly connected component and how does Tarjan's algorithm find it?",
"acceptedAnswer": {
"@type": "Answer",
"text": "A Strongly Connected Component (SCC) is a maximal subset of vertices where every vertex can reach every other vertex. In a social network: an SCC is a group where everyone can message everyone else (following only directed edges). Tarjan's algorithm: DFS with two values per node: disc (discovery time, when DFS first visits) and low (lowest disc reachable from the subtree via back edges). A node v is an SCC root if low[v] == disc[v] (no back edge reaches an ancestor — the subtree rooted at v is isolated). When an SCC root is found: pop nodes from the DFS stack until v is popped; they form the SCC. O(V+E) time, O(V) space. Use case in interviews: finding circular dependencies in a build system (each SCC is a dependency cycle). Condensation graph (SCCs as nodes, edges between SCCs) is always a DAG."
}
},
{
"@type": "Question",
"name": "How do you find an Eulerian path in a directed graph?",
"acceptedAnswer": {
"@type": "Answer",
"text": "An Eulerian path in a directed graph: exists if (1) the graph is connected (ignoring edge directions) and (2) at most one vertex has (out_degree – in_degree = 1) (start node), at most one has (in_degree – out_degree = 1) (end node), and all others have equal in and out degree. Find it with Hierholzer's algorithm: start at the start vertex (or any vertex if all degrees are equal for Eulerian circuit). DFS: follow an unvisited edge from the current vertex. Push the vertex to a stack when no unvisited edges remain. Reverse the stack = Eulerian path. O(E) time. Interview application: 'Reconstruct Itinerary' (LeetCode 332) — each airport is a node, each ticket is a directed edge. Find the lexicographically smallest Eulerian path starting from JFK. Use a min-heap (sorted neighbors) + Hierholzer's."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Coinbase Interview Guide