| Adjacency list space | O(V+E) — preferred for sparse graphs |
| Adjacency matrix space | O(V²) — fast O(1) edge lookup, wasteful for sparse graphs |
| BFS / DFS traversal | O(V+E) time, O(V) space |
| Dijkstra (binary heap) | O((V+E) log V) — no negative weights |
| Bellman-Ford | O(V×E) — handles negative weights, detects negative cycles |
| Floyd-Warshall | O(V³) time, O(V²) space — all-pairs shortest paths |
| Kruskal's MST | O(E log E) — sort edges + union-find |
| Union-Find (path compression + union by rank) | O(1) amortized per operation |
Graph Algorithms Coding Interview Questions & Answers
Q1. What is a graph, and what are its two basic components?
A: A graph is a data structure consisting of a set of vertices (nodes) and a set of edges connecting pairs of vertices. Vertices represent entities (cities, users, web pages) and edges represent relationships or connections between them (roads, friendships, hyperlinks). Unlike trees, graphs allow cycles and multiple paths between the same two nodes, making them the most general way to model pairwise relationships.
Q2. What is the difference between a directed graph and an undirected graph?
A: In an undirected graph, an edge between u and v implies you can traverse in both directions — the edge (u, v) is identical to (v, u). In a directed graph (digraph), edges have a direction, so an edge from u to v does not imply an edge from v to u; think of one-way streets versus two-way streets. This distinction changes how adjacency is stored and how algorithms like cycle detection and topological sort must be implemented.
Q3. What is a weighted graph versus an unweighted graph?
A: In a weighted graph, every edge carries a numeric cost (distance, time, price), and shortest-path algorithms must account for that cost rather than just the number of hops. An unweighted graph treats every edge as having an implicit weight of 1, so the "shortest path" is simply the path with the fewest edges, which is exactly what BFS computes directly.
Q4. How is a graph represented using an adjacency matrix, and what is its space cost?
A: An adjacency matrix is a V×V 2D array where matrix[i][j] is 1 (or the weight) if an edge exists from i to j, and 0/infinity otherwise. It uses O(V²) space regardless of how many edges actually exist, and offers O(1) edge-existence checks, but it wastes memory on sparse graphs where E is much smaller than V².
int[][] adjMatrix = new int[V][V];
adjMatrix[u][v] = 1; // directed edge u -> v
adjMatrix[v][u] = 1; // add this line too if undirected
boolean hasEdge = adjMatrix[u][v] == 1; // O(1) lookupQ5. How is a graph represented using an adjacency list, and why is it usually preferred?
A: An adjacency list stores, for each vertex, a list of the vertices it is directly connected to — typically an array or map of List<Integer> (or a list of edge objects for weighted graphs). It uses only O(V+E) space, which scales with the actual number of edges rather than V², making it the default choice for most interview problems since real-world graphs are usually sparse.
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
adj.get(u).add(v); // directed edge u -> v
adj.get(v).add(u); // add this line too if undirectedQ6. When would you choose an adjacency matrix over an adjacency list?
A: Prefer a matrix when the graph is dense (E close to V²), when you need O(1) "does an edge exist between u and v" queries very frequently, or when the vertex count is small and fixed (like a Floyd-Warshall all-pairs computation, which inherently needs a V×V structure). Prefer a list whenever the graph is sparse or V is large, since the matrix's O(V²) memory becomes prohibitive.
Q7. How would you model a weighted graph in Java using an adjacency list?
A: Instead of storing plain neighbor integers, store small edge objects (or int arrays) that pair a neighbor with its weight, one list per source vertex. This keeps the O(V+E) space advantage of an adjacency list while still supporting weighted algorithms like Dijkstra and Bellman-Ford that need per-edge cost during traversal.
class Edge {
int to, weight;
Edge(int to, int weight) { this.to = to; this.weight = weight; }
}
List<List<Edge>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
adj.get(u).add(new Edge(v, weight));Q8. What is an edge list representation and when is it useful?
A: An edge list simply stores every edge as a triple (or pair) — source, destination, and optionally weight — in one flat list, without any per-vertex grouping. It is the most compact and simplest representation to build, and it is exactly the form Kruskal's MST algorithm wants, since Kruskal only needs to sort all edges globally by weight rather than traverse neighbor-by-neighbor.
Q9. What is the degree of a vertex, and how does it differ for directed graphs?
A: In an undirected graph, the degree of a vertex is the number of edges incident to it. In a directed graph, this splits into in-degree (number of incoming edges) and out-degree (number of outgoing edges); a vertex with in-degree 0 is a natural starting point (a "source"), which is exactly what Kahn's topological sort algorithm looks for first.
int[] outDegree = new int[V];
int[] inDegree = new int[V];
for (int u = 0; u < V; u++)
for (int v : adj.get(u)) { outDegree[u]++; inDegree[v]++; }Q10. What is a self-loop and a multigraph?
A: A self-loop is an edge that connects a vertex to itself (u to u). A multigraph allows more than one edge between the same pair of vertices (e.g., two different flights between the same two cities with different costs). Most interview graph problems assume a simple graph — no self-loops, no parallel edges — unless the problem statement says otherwise.
Q11. How is a tree a special case of a graph?
A: A tree is a connected, undirected, acyclic graph with exactly V-1 edges for V vertices — one unique path between any two nodes and no cycles. This means every tree algorithm (traversal, recursion, LCA) is really a graph algorithm restricted to this acyclic, singly-connected structure, and general graph algorithms like BFS/DFS work on trees unchanged, just without needing a "visited" check to avoid infinite loops (though it's still safe to keep one).
Q12. What is a DAG (Directed Acyclic Graph), and why does it matter?
A: A DAG is a directed graph containing no directed cycles — you can never return to a vertex by following edge directions. DAGs are the precondition for topological sorting (task scheduling, build dependency graphs, course prerequisites) and are also the structure behind dynamic programming problems reformulated as shortest/longest path problems, since a DAG guarantees a valid processing order exists.
Q13. What is BFS (Breadth-First Search) and how does it explore a graph?
A: BFS explores a graph level by level outward from a starting vertex, visiting all neighbors at distance 1 before any at distance 2, and so on. It uses a queue (FIFO) to enforce this order: dequeue a vertex, enqueue all its unvisited neighbors, mark them visited immediately (to avoid enqueuing duplicates), and repeat until the queue is empty.
Q14. How do you implement BFS iteratively in Java?
A: Use an explicit Queue, a boolean[] (or set) of visited vertices, mark and enqueue the start node first, then repeatedly dequeue a vertex, process it, and enqueue any unvisited neighbors while marking them visited. Marking a neighbor visited at enqueue time (not at dequeue time) is essential to prevent the same vertex from being added to the queue multiple times.
void bfs(List<List<Integer>> adj, int start, int V) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}Q15. What is the time and space complexity of BFS?
A: BFS is O(V+E) time because every vertex is dequeued once and every edge is examined once (twice for undirected graphs, once per direction, which is still a constant factor). Space is O(V) for the visited array plus the queue, which in the worst case (a star graph) can hold almost all vertices at once.
Q16. Why does BFS guarantee the shortest path in an unweighted graph, but not necessarily in a weighted one?
A: BFS discovers vertices in strictly increasing order of distance (number of edges) from the source because it fully processes each level before moving to the next, so the first time a vertex is reached is guaranteed to be via the fewest possible edges. This guarantee breaks for weighted graphs because a path with more edges can still have a smaller total weight than a path with fewer edges — that's precisely why Dijkstra's algorithm (priority queue by cumulative weight) is needed instead.
Q17. How do you compute the shortest distance (in edges) from a source to every other vertex using BFS?
A: Initialize a distance[] array to -1 (unvisited) except the source, which is 0. Whenever a neighbor is discovered for the first time during BFS, set its distance to distance[current] + 1 before enqueuing it. Because BFS visits vertices in non-decreasing distance order, each distance is finalized correctly the first (and only) time it is set.
int[] bfsDistances(List<List<Integer>> adj, int start, int V) {
int[] dist = new int[V];
Arrays.fill(dist, -1);
dist[start] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int nbr : adj.get(node)) {
if (dist[nbr] == -1) {
dist[nbr] = dist[node] + 1;
queue.offer(nbr);
}
}
}
return dist;
}Q18. What is multi-source BFS, and when would you use it?
A: Multi-source BFS starts with several source vertices already enqueued (all at distance 0) instead of just one, so the traversal spreads outward from all of them simultaneously. It is the standard technique for problems like "rotting oranges" (multiple rotten oranges spread infection simultaneously) or "distance to nearest 0" in a grid, where computing each source's BFS separately would be far more expensive than expanding all fronts together in one pass.
Queue<int[]> queue = new LinkedList<>();
for (int[] source : sources) queue.offer(source); // seed all sources at once
boolean[] visited = new boolean[V];
for (int[] s : sources) visited[s[0]] = true;
// then run the normal BFS loop from hereQ19. Why can't you simply swap BFS's queue for a stack and still call it BFS?
A: A queue (FIFO) preserves discovery order, so vertices are processed in the exact order they were found, guaranteeing level-by-level expansion. A stack (LIFO) would process the most recently discovered vertex next, which plunges deeper into the graph instead of spreading outward — that behavior is DFS, not BFS, and it destroys the shortest-path-by-edge-count guarantee.
Q20. How do you model a 2D grid as a graph for BFS (e.g., shortest path in a maze)?
A: Each cell (row, col) is an implicit vertex, and its neighbors are the up to four adjacent cells (up, down, left, right) that are within bounds and not blocked/visited — there is no need to materialize an explicit adjacency list. BFS then runs exactly as on any graph, using a queue of coordinate pairs and a 2D visited array, giving the shortest path in number of moves.
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{startRow, startCol, 0});
visited[startRow][startCol] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
if (cur[0] == targetRow && cur[1] == targetCol) return cur[2];
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc] && grid[nr][nc] != 1) {
visited[nr][nc] = true;
q.offer(new int[]{nr, nc, cur[2] + 1});
}
}
}Q21. How is BFS used to find the length of the shortest path between two specific nodes?
A: Run standard BFS from the source, but stop as soon as the target node is dequeued (or its distance is set), returning its recorded distance. There is no need to complete the BFS over the whole graph once the target is found, because BFS guarantees the first time a node is reached is via its shortest path in an unweighted graph.
Q22. How does BFS on a general graph differ from level-order traversal of a binary tree?
A: They use the identical queue-based mechanism, but a tree traversal never needs a visited set because a tree has no cycles and each node has exactly one parent, whereas general-graph BFS must explicitly track visited vertices to avoid infinite loops or reprocessing a vertex reachable via multiple paths. Level-order traversal is essentially BFS specialized to the acyclic, single-parent structure of a tree.
Q23. What is DFS (Depth-First Search) and how does it explore a graph?
A: DFS explores as far as possible along each branch before backtracking — from the current vertex, it moves to an unvisited neighbor, recursing (or pushing to a stack) before considering the next neighbor, only backing up once a vertex has no unvisited neighbors left. It can be implemented with either recursion (the call stack acts as the stack) or an explicit stack data structure.
Q24. How do you implement DFS recursively in Java?
A: Mark the current vertex visited, process it, and then recursively call DFS on every unvisited neighbor. The recursion naturally backtracks once a vertex's neighbor list is exhausted, which is what gives DFS its depth-first character — each recursive call goes one level deeper before returning control to its caller.
void dfs(List<List<Integer>> adj, int node, boolean[] visited) {
visited[node] = true;
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfs(adj, neighbor, visited);
}
}
}Q25. How do you implement DFS iteratively using an explicit stack?
A: Push the start vertex onto a stack; while the stack isn't empty, pop a vertex, and if it hasn't been visited, mark it visited, process it, and push all of its neighbors (visited or not — the check happens on pop, not on push, since a vertex may be pushed multiple times before being popped). This avoids Java's call-stack depth limit on very deep or highly recursive graphs.
void dfsIterative(List<List<Integer>> adj, int start, int V) {
boolean[] visited = new boolean[V];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited[node]) continue;
visited[node] = true;
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) stack.push(neighbor);
}
}
}Q26. What is the time and space complexity of DFS?
A: DFS is O(V+E) time for the same reason as BFS — every vertex is visited once and every edge is examined at most twice (once per direction on undirected graphs). Space is O(V) for the visited array plus the recursion call stack (or explicit stack), which in the worst case (a long path graph) can hold all V vertices at once.
Q27. What are entry time and exit time in a DFS traversal, and why do they matter?
A: Entry time (discovery time) records when a vertex is first visited; exit time (finish time) records when DFS has fully explored all of its descendants and is about to backtrack past it. These timestamps let you classify edges (back, forward, cross) and are the foundation of algorithms like Tarjan's SCC and the DFS-based topological sort, where finish-time order directly gives a valid topological ordering when reversed.
Q28. What are back edges, forward edges, and cross edges in a DFS tree?
A: A tree edge is one actually traversed by DFS to discover a new vertex. A back edge points from a vertex to one of its ancestors in the DFS tree (still being processed, i.e., on the current recursion stack) — the presence of a back edge in a directed graph is exactly what signals a cycle. A forward edge points to a descendant already fully finished, and a cross edge connects two vertices with no ancestor-descendant relationship; the latter two can only occur in directed graphs.
Q29. How does DFS help find articulation points and bridges in an undirected graph?
A: Tarjan's low-link technique runs DFS while tracking each vertex's discovery time and its "low" value — the lowest discovery time reachable via a back edge from its subtree. A vertex u (non-root) is an articulation point if some child c has low[c] >= discovery[u], meaning c's subtree cannot reach back above u, so removing u disconnects the graph; an edge (u, c) is a bridge under the stricter condition low[c] > discovery[u].
Q30. How does DFS detect cycles conceptually, before looking at directed vs. undirected specifics?
A: A cycle exists if, during DFS, you encounter an edge leading to a vertex that is already "in progress" (currently on the active recursion path) rather than fully finished or never visited. The precise check differs between undirected graphs (any revisit of a non-parent visited vertex signals a cycle) and directed graphs (only a revisit of a vertex still on the current recursion stack counts, since directed graphs can revisit fully-finished vertices safely via cross edges).
Q31. What are the trade-offs between recursive and iterative DFS?
A: Recursive DFS is shorter and more natural to write, but each recursive call consumes stack frame memory, so a very deep or skewed graph (e.g., a 100,000-node path) can trigger a StackOverflowError in Java, whose default thread stack size is limited. Iterative DFS with an explicit Deque avoids that limit entirely (bounded only by heap memory) at the cost of slightly more verbose bookkeeping code.
Q32. How do you find all paths between two nodes in a graph using DFS backtracking?
A: Perform DFS from the source, maintaining a mutable path list; add the current vertex to the path, and if it equals the target, record a copy of the path. Otherwise recurse into each unvisited neighbor, then remove the vertex from the path before returning (the backtrack step) so sibling branches start from a clean path. This naturally enumerates every simple path, which can be exponential in the worst case.
void findPaths(List<List<Integer>> adj, int node, int target,
boolean[] visited, List<Integer> path, List<List<Integer>> result) {
visited[node] = true;
path.add(node);
if (node == target) {
result.add(new ArrayList<>(path));
} else {
for (int nbr : adj.get(node)) {
if (!visited[nbr]) findPaths(adj, nbr, target, visited, path, result);
}
}
path.remove(path.size() - 1); // backtrack
visited[node] = false;
}Q33. What is a connected component in an undirected graph?
A: A connected component is a maximal set of vertices such that every pair of vertices in the set has a path between them, and no vertex outside the set connects to any vertex inside it. A graph with a single connected component is fully connected; otherwise it is a disjoint union of several separate "islands" of connectivity.
Q34. How do you count the number of connected components in an undirected graph?
A: Iterate over all vertices; whenever you find one that hasn't been visited yet, increment a counter and run a full BFS or DFS from it to mark every vertex reachable from it as visited. Each such run discovers exactly one connected component, so the counter's final value is the answer, in O(V+E) total time.
int countComponents(List<List<Integer>> adj, int V) {
boolean[] visited = new boolean[V];
int count = 0;
for (int i = 0; i < V; i++) {
if (!visited[i]) {
count++;
dfs(adj, i, visited);
}
}
return count;
}Q35. What is a strongly connected component (SCC) in a directed graph?
A: An SCC is a maximal set of vertices where every vertex can reach every other vertex in the set by following directed edges (a path exists in both directions between any pair). Unlike undirected connectivity, directed reachability isn't automatically symmetric, so SCCs partition a directed graph into groups of mutually reachable vertices, with no such guarantee between different SCCs.
Q36. How does Kosaraju's algorithm find all strongly connected components?
A: Kosaraju's algorithm runs in three steps: (1) do a DFS on the original graph and record vertices by finish time onto a stack, (2) reverse every edge in the graph, and (3) process vertices in the order popped from the stack, running DFS on the reversed graph from each unvisited one — each such DFS run discovers exactly one SCC. It runs in O(V+E) time since it performs a constant number of full graph traversals.
Q37. How does Tarjan's algorithm find SCCs in a single DFS pass?
A: Tarjan's algorithm tracks a discovery index and a low-link value per vertex while maintaining an explicit stack of vertices currently "on the path." When a vertex's low-link equals its own discovery index (meaning it cannot reach any ancestor further back), it is the root of an SCC, and every vertex still on the stack above it is popped off as belonging to that same SCC. It achieves O(V+E) time with just one DFS traversal, versus Kosaraju's two full passes.
void tarjan(int u) {
disc[u] = low[u] = ++timer;
stack.push(u);
onStack[u] = true;
for (int v : adj.get(u)) {
if (disc[v] == -1) {
tarjan(v);
low[u] = Math.min(low[u], low[v]);
} else if (onStack[v]) {
low[u] = Math.min(low[u], disc[v]);
}
}
if (low[u] == disc[u]) { // u is an SCC root
while (stack.peek() != u) { onStack[stack.pop()] = false; }
onStack[stack.pop()] = false;
}
}Q38. What is the condensation graph of a directed graph's SCCs?
A: The condensation graph collapses each strongly connected component into a single super-vertex, keeping an edge between two super-vertices if any edge existed between their original members. The resulting graph is always a DAG (no cycles can remain, otherwise the collapsed components would have been merged into one larger SCC), which makes it eligible for topological sorting and DAG-based dynamic programming.
Q39. How do you detect a cycle in an undirected graph using DFS?
A: During DFS, track each vertex's immediate parent in the traversal. If you visit a neighbor that is already visited and that neighbor is not the current vertex's direct parent, a cycle exists — you've reached an ancestor through a different path. Simply revisiting the parent is expected in undirected graphs (since the edge is bidirectional) and must not be flagged as a cycle.
Q40. How do you implement cycle detection in an undirected graph in Java?
A: The DFS carries the parent vertex alongside the current one; any visited neighbor other than the parent indicates a cycle. This is O(V+E) time, the same as a plain DFS traversal, since no extra passes are needed.
boolean hasCycleUndirected(List<List<Integer>> adj, int node, int parent, boolean[] visited) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
if (hasCycleUndirected(adj, neighbor, node, visited)) return true;
} else if (neighbor != parent) {
return true; // revisited a non-parent -> cycle
}
}
return false;
}Q41. How do you detect a cycle in a directed graph using DFS?
A: Track three states per vertex: unvisited (white), currently in the recursion stack / being explored (gray), and fully finished (black). A cycle exists if DFS ever encounters an edge to a gray vertex — that means the current path has looped back onto itself. Encountering an edge to a black vertex is safe (it's a cross or forward edge, not a cycle), which is the key difference from the undirected case.
Q42. How do you implement directed-cycle detection with a recursion stack in Java?
A: Maintain two boolean arrays: visited for "ever discovered" and onStack for "currently on the active recursion path." Mark both true on entry, recurse into unvisited neighbors, and immediately return true if a neighbor is onStack (a back edge to an in-progress ancestor); before returning from the call, clear onStack for the current vertex since it's no longer part of the active path.
boolean hasCycleDirected(List<List<Integer>> adj, int node, boolean[] visited, boolean[] onStack) {
visited[node] = true;
onStack[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
if (hasCycleDirected(adj, neighbor, visited, onStack)) return true;
} else if (onStack[neighbor]) {
return true; // back edge to a vertex on the current path
}
}
onStack[node] = false; // done exploring this vertex's branch
return false;
}Q43. How does Kahn's algorithm detect a cycle in a directed graph as a side effect of topological sort?
A: Kahn's algorithm repeatedly removes vertices with in-degree 0, decrementing the in-degree of their neighbors. If the graph is a DAG, exactly V vertices will be processed this way; if fewer than V vertices are processed (the queue empties early), the remaining, unprocessed vertices must all be part of one or more cycles, since every vertex in a cycle always has at least one incoming edge and never reaches in-degree 0.
Q44. How do you detect a cycle in an undirected graph using Union-Find instead of DFS?
A: Process each edge (u, v) one at a time: if u and v are already in the same disjoint set (same root), adding this edge would create a cycle, so report a cycle immediately. Otherwise, union their sets and continue. This is O(E) union-find operations (near O(1) each with path compression and union by rank), and it's exactly how Kruskal's algorithm avoids creating cycles while building an MST.
Q45. Why doesn't a simple "visited" boolean array alone suffice for directed-cycle detection the way it does for undirected graphs?
A: In a directed graph, reaching an already-visited vertex is not automatically a cycle — it could be a perfectly valid cross edge or forward edge to a branch that has already been fully explored and has no path back to the current vertex. Only revisiting a vertex that is still actively on the current DFS path (tracked via the separate onStack/gray state) indicates an actual cycle, which is why directed-cycle detection needs that extra state beyond plain visited/unvisited.
Q46. What is topological sorting, and what precondition must the graph satisfy?
A: A topological sort is a linear ordering of a directed graph's vertices such that for every directed edge u → v, u appears before v in the ordering. It only exists for a DAG — any directed cycle makes a valid ordering impossible, since the vertices in the cycle would each need to come before each other.
Q47. How does the DFS-based algorithm for topological sort work?
A: Run DFS from every unvisited vertex; each time a vertex finishes exploring all of its neighbors (i.e., it's about to be popped off the recursion), push it onto a stack. Once DFS is complete, popping the stack from top to bottom gives a valid topological order — a vertex is only pushed after everything reachable from it has already finished, so it necessarily ends up before its dependents when the stack is reversed.
Q48. How do you implement DFS-based topological sort in Java?
A: Use a standard recursive DFS, but instead of printing on entry, push the vertex onto a stack right after the for-loop over its neighbors completes. After running DFS from every unvisited vertex, pop the entire stack to get the topological order.
void topoDfs(List<List<Integer>> adj, int node, boolean[] visited, Deque<Integer> stack) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) topoDfs(adj, neighbor, visited, stack);
}
stack.push(node); // push only after all descendants are done
}
List<Integer> topologicalSort(List<List<Integer>> adj, int V) {
boolean[] visited = new boolean[V];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < V; i++) if (!visited[i]) topoDfs(adj, i, visited, stack);
List<Integer> order = new ArrayList<>();
while (!stack.isEmpty()) order.add(stack.pop());
return order;
}Q49. How does Kahn's algorithm (BFS-based) perform topological sort?
A: Compute in-degree for every vertex, then enqueue all vertices with in-degree 0 (they have no prerequisites). Repeatedly dequeue a vertex, append it to the result, and decrement the in-degree of each of its neighbors — enqueuing any neighbor whose in-degree drops to 0. This mirrors "process a task once all its prerequisites are done," which is intuitive for build systems and course scheduling.
Q50. How do you implement Kahn's algorithm in Java?
A: First compute every vertex's in-degree by scanning all adjacency lists. Seed a queue with every vertex whose in-degree is 0, then repeatedly poll a vertex, add it to the result, and decrement its neighbors' in-degrees, enqueuing any that reach 0. If the resulting order has fewer than V vertices, the graph contains a cycle and no valid topological order exists.
List<Integer> kahnTopoSort(List<List<Integer>> adj, int V) {
int[] inDegree = new int[V];
for (int u = 0; u < V; u++) for (int v : adj.get(u)) inDegree[v]++;
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++) if (inDegree[i] == 0) queue.offer(i);
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int neighbor : adj.get(node)) {
if (--inDegree[neighbor] == 0) queue.offer(neighbor);
}
}
if (order.size() != V) throw new IllegalStateException("Graph has a cycle");
return order;
}Q51. What are some real-world use cases of topological sorting?
A: Build systems (Maven/Gradle) use it to determine the order to compile modules given their dependencies; course scheduling uses it to order courses given prerequisites; task schedulers use it to run jobs in dependency order; and spreadsheet applications use it to evaluate formula cells in the correct order when one cell's value depends on another's.
Q52. What problem does Dijkstra's algorithm solve, and what is its core idea?
A: Dijkstra's algorithm finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edge weights. It greedily picks the unvisited vertex with the smallest known tentative distance (using a min-priority-queue), finalizes that distance, and relaxes (potentially improves) the distances of its neighbors — repeating until every reachable vertex has been finalized.
Q53. Why doesn't Dijkstra's algorithm work correctly with negative edge weights?
A: Dijkstra finalizes a vertex's distance as soon as it's popped from the priority queue, assuming no future edge could possibly produce a shorter path to it — but a negative-weight edge discovered later could indeed reduce that "finalized" distance further, and Dijkstra would never revisit it. This greedy assumption only holds when all weights are non-negative, which is why Bellman-Ford (which keeps relaxing without assuming any vertex is "done") is required when negative weights are possible.
Q54. How do you implement Dijkstra's algorithm in Java using a PriorityQueue?
A: Store {distance, vertex} pairs in a min-heap ordered by distance, seeded with the source at distance 0. Repeatedly poll the smallest-distance entry; if it's stale (a better distance was already finalized for that vertex), skip it; otherwise relax each neighbor and push improved distances onto the heap. This achieves O((V+E) log V) time with a binary heap.
int[] dijkstra(List<List<Edge>> adj, int src, int V) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, src});
while (!pq.isEmpty()) {
int[] top = pq.poll();
int d = top[0], u = top[1];
if (d > dist[u]) continue; // stale entry
for (Edge e : adj.get(u)) {
int newDist = d + e.weight;
if (newDist < dist[e.to]) {
dist[e.to] = newDist;
pq.offer(new int[]{newDist, e.to});
}
}
}
return dist;
}Q55. What is the time complexity of Dijkstra's algorithm with different underlying data structures?
A: With a plain array scan to find the minimum each iteration, it's O(V²), which can beat a heap on dense graphs. With a binary heap priority queue, it's O((V+E) log V), the standard interview answer. With a Fibonacci heap, decrease-key becomes O(1) amortized, bringing total time down to O(E + V log V) — a theoretical improvement rarely implemented in practice due to complexity.
Q56. What is "edge relaxation" in the context of shortest-path algorithms?
A: Relaxing an edge (u, v) with weight w means checking whether going through u gives a shorter path to v than v's currently known best distance — i.e., whether dist[u] + w < dist[v] — and updating dist[v] if so. Every shortest-path algorithm (Dijkstra, Bellman-Ford, Floyd-Warshall) is fundamentally just repeated edge relaxation applied in a different order or a different number of times.
Q57. How do you reconstruct the actual shortest path (not just its length) after running Dijkstra's?
A: Maintain a parent[] array alongside dist[]; whenever an edge relaxation improves dist[v], set parent[v] = u. After the algorithm finishes, walk backward from the target through parent pointers until reaching the source (or -1), then reverse that list to get the path from source to target.
Q58. How does Dijkstra's algorithm relate to and differ from plain BFS?
A: Both are greedy frontier-expansion algorithms that finalize vertices in order of distance from the source. BFS is essentially Dijkstra's specialized to unweighted graphs, where a simple FIFO queue suffices because every edge has weight 1 (so the "priority" is naturally just discovery order); Dijkstra generalizes this using a priority queue so that vertices are finalized in order of actual cumulative weight, not hop count.
Q59. What problem does Bellman-Ford solve that Dijkstra's algorithm cannot?
A: Bellman-Ford correctly computes single-source shortest paths even when the graph has negative edge weights, and it can additionally detect the presence of a negative-weight cycle (a cycle whose total weight is negative, which would make "shortest path" undefined since you could loop forever to decrease cost). Dijkstra assumes non-negative weights and simply produces incorrect results if that assumption is violated.
Q60. How does Bellman-Ford's algorithm work?
A: It relaxes every edge in the graph, V-1 times in total (where V is the vertex count). Since the shortest path between any two vertices in a graph with no negative cycles uses at most V-1 edges, V-1 full rounds of relaxing all edges guarantees every shortest path has been fully propagated, regardless of edge order.
Q61. How do you implement Bellman-Ford in Java?
A: Initialize distances to infinity except the source (0), then loop V-1 times, relaxing every edge in the edge list each time. An extra, (V)-th pass that still finds an improvable edge indicates a negative-weight cycle exists somewhere reachable from the source.
int[] bellmanFord(int[][] edges, int V, int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 0; i < V - 1; i++) {
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
for (int[] edge : edges) { // Vth pass: check for negative cycle
int u = edge[0], v = edge[1], w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
throw new IllegalStateException("Negative weight cycle detected");
}
}
return dist;
}Q62. How does Bellman-Ford detect a negative weight cycle?
A: After the standard V-1 relaxation rounds (which are guaranteed sufficient in a cycle-free graph), run one more pass over all edges. If any edge can still be relaxed (still finds a shorter distance), that improvement could only come from a negative cycle continuing to reduce distances indefinitely, since a normal graph's shortest paths would have already stabilized.
Q63. What is the time complexity of Bellman-Ford, and when should you prefer it over Dijkstra?
A: Bellman-Ford is O(V×E) because it performs V-1 rounds, each relaxing all E edges — significantly slower than Dijkstra's O((V+E) log V) on graphs with non-negative weights. Prefer Bellman-Ford specifically when negative edge weights are possible (e.g., currency arbitrage graphs, graphs with penalty/refund edges) or when you need to explicitly detect negative cycles.
Q64. What problem does the Floyd-Warshall algorithm solve?
A: Floyd-Warshall computes the shortest path between every pair of vertices in a weighted graph (all-pairs shortest paths) in a single algorithm, rather than running a single-source algorithm V times. It handles negative edge weights (as long as there's no negative cycle) and is especially convenient when the graph is small and dense, or when you genuinely need every pairwise distance, not just from one source.
Q65. What is the core idea behind Floyd-Warshall's dynamic programming approach?
A: For every intermediate vertex k (processed in order from 1 to V), and for every pair (i, j), check whether routing through k gives a shorter path than the current best: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After considering all vertices as potential intermediates, dist[i][j] holds the true shortest path allowing any subset of vertices as intermediate stops.
Q66. How do you implement Floyd-Warshall in Java?
A: Initialize a V×V distance matrix directly from the adjacency matrix (0 on the diagonal, edge weights where they exist, infinity elsewhere), then run three nested loops over k, i, j in that specific order (k must be the outermost loop), relaxing dist[i][j] through k each time.
void floydWarshall(int[][] dist, int V) {
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE
&& dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}Q67. What is the time and space complexity of Floyd-Warshall?
A: It is O(V³) time due to the three nested loops over all vertices, and O(V²) space for the distance matrix (which can be updated in place, reusing the input adjacency matrix). This makes it practical only for graphs with roughly a few thousand vertices or fewer; for larger sparse graphs, running Dijkstra from every vertex (O(V×(E log V))) is usually faster.
Q68. How do you detect a negative cycle using Floyd-Warshall?
A: After running the full algorithm, check the diagonal of the distance matrix: if any dist[i][i] is negative, then vertex i lies on a cycle whose total weight is negative (since the shortest "path" from i back to itself should always be 0 in a cycle-free-negative graph). This is a simple O(V) post-processing check on top of the O(V³) main computation.
Q69. What is a Minimum Spanning Tree (MST)?
A: A spanning tree of a connected, undirected graph is a subgraph that connects all V vertices using exactly V-1 edges with no cycles. A Minimum Spanning Tree is the spanning tree whose sum of edge weights is the smallest possible among all spanning trees of that graph — the cheapest way to keep every vertex connected.
Q70. How does Kruskal's algorithm build an MST?
A: Sort all edges by weight in ascending order, then process them one at a time, adding an edge to the MST only if its two endpoints are currently in different components (checked and merged via union-find) — skipping it if they're already connected, since that edge would create a cycle. The algorithm stops once V-1 edges have been added.
Q71. How do you implement Kruskal's algorithm in Java?
A: Represent each edge as a small object or array of {weight, u, v}, sort the edge array by weight, then iterate through it using a union-find structure to decide whether to accept each edge into the growing MST.
int kruskalMST(int[][] edges, int V) { // edges[i] = {u, v, weight}
Arrays.sort(edges, (a, b) -> a[2] - b[2]);
UnionFind uf = new UnionFind(V);
int totalWeight = 0, edgesUsed = 0;
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (uf.union(u, v)) { // true only if u and v were in different sets
totalWeight += w;
edgesUsed++;
if (edgesUsed == V - 1) break;
}
}
return totalWeight;
}Q72. Why does Kruskal's algorithm use Union-Find rather than DFS/BFS to detect cycles?
A: Kruskal considers edges in arbitrary weight order, not in a connected traversal order, so a DFS/BFS-based "is there already a path between u and v" check would need to search the partially-built MST from scratch for every edge, costing O(V+E) per check. Union-Find answers "are u and v already connected" in near O(1) amortized time (with path compression and union by rank), which is what keeps Kruskal's overall complexity down to O(E log E), dominated by the sort.
Q73. What is the time complexity of Kruskal's algorithm?
A: Sorting the E edges costs O(E log E), and then processing them with near-O(1) union-find operations costs approximately O(E). Since O(E log E) dominates, the overall time complexity is O(E log E).
Q74. When can a graph have more than one valid Minimum Spanning Tree?
A: Whenever there are duplicate edge weights that create a tie in Kruskal's (or Prim's) selection process, different tie-breaking choices can produce different spanning trees that all have the identical total weight. All such trees are equally valid MSTs — the MST's total weight is always unique, but the specific set of edges achieving it may not be.
Q75. How does Prim's algorithm build an MST?
A: Prim's grows a single tree starting from an arbitrary vertex: at each step, it adds the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree, using a priority queue of candidate edges keyed by weight. This continues until all V vertices are included, always keeping the growing structure connected (unlike Kruskal, which can add disconnected pieces that only merge later).
Q76. How do you implement Prim's algorithm in Java using a PriorityQueue?
A: Start by pushing the source vertex's edges into a min-heap keyed by weight; repeatedly pop the cheapest edge, and if its destination hasn't already been added to the MST, add it, accumulate its weight, and push all of its outgoing edges into the heap. Skip any popped edge whose destination is already in the MST, since that would create a cycle.
int primMST(List<List<Edge>> adj, int V, int start) {
boolean[] inMST = new boolean[V];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, start}); // {weight, vertex}
int totalWeight = 0;
while (!pq.isEmpty()) {
int[] top = pq.poll();
int w = top[0], u = top[1];
if (inMST[u]) continue;
inMST[u] = true;
totalWeight += w;
for (Edge e : adj.get(u)) {
if (!inMST[e.to]) pq.offer(new int[]{e.weight, e.to});
}
}
return totalWeight;
}Q77. What is the time complexity of Prim's algorithm with different data structures?
A: With an adjacency matrix and a simple array-based minimum search, it's O(V²), efficient for dense graphs. With an adjacency list and a binary heap priority queue, it's O(E log V), better for sparse graphs — the same asymptotic complexity as Dijkstra's heap-based implementation, since both algorithms share the same "greedily extend via a priority queue" structure.
Q78. When would you prefer Kruskal's algorithm over Prim's, or vice versa?
A: Prefer Kruskal's when the graph is sparse and edges are easy to sort globally, or when the edge list representation is already available (e.g., streaming edges). Prefer Prim's when the graph is dense (adjacency matrix representation) or when you want to grow the MST incrementally from a specific starting vertex, which Kruskal's global edge-sorting approach doesn't naturally support.
Q79. Does the standard MST algorithm (Kruskal's/Prim's) work on directed graphs?
A: No — MST is defined for undirected graphs; the analogous problem on a directed graph is called a Minimum Arborescence (or Minimum Spanning Arborescence), solved by a different algorithm (the Chu-Liu/Edmonds' algorithm), because direction fundamentally changes which vertex can serve as the "root" and which edges can be legally combined without violating directionality.
Q80. What is a disjoint set (union-find) data structure used for?
A: A disjoint set / union-find data structure efficiently tracks a partition of elements into non-overlapping groups, supporting two operations: find(x) (which group does x belong to) and union(x, y) (merge x's and y's groups). It's the backbone of Kruskal's MST, cycle detection in undirected graphs, and network connectivity queries where you repeatedly ask "are these two nodes connected."
Q81. How do you implement Union-Find with path compression and union by rank in Java?
A: Store a parent[] array (each element initially its own parent) and a rank[] array (initially 0). find() recursively follows parent pointers to the root while flattening the path (path compression) by pointing every visited node directly at the root. union() attaches the root with the smaller rank under the root with the larger rank, incrementing rank only when both ranks were equal — keeping the resulting tree shallow.
class UnionFind {
int[] parent, rank;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // path compression
return parent[x];
}
boolean union(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX == rootY) return false; // already connected -> would form a cycle
if (rank[rootX] < rank[rootY]) { int t = rootX; rootX = rootY; rootY = t; }
parent[rootY] = rootX;
if (rank[rootX] == rank[rootY]) rank[rootX]++;
return true;
}
}Q82. What is path compression, and how does it improve union-find performance?
A: Path compression makes every node visited during a find() call point directly at the discovered root, instead of leaving the original chain of intermediate parent pointers in place. This flattens the tree structure over time, so future find() calls on those same nodes (or their descendants) resolve in far fewer hops, contributing to the near-constant amortized time complexity.
Q83. What is union by rank (or union by size), and why does it matter?
A: Union by rank always attaches the root of the shorter (lower-rank) tree underneath the root of the taller tree, rather than picking arbitrarily. This prevents the combined tree from growing needlessly tall/skewed, keeping the maximum tree height logarithmic in the number of elements even without path compression, which bounds the worst case for `find()`.
Q84. What is the overall time complexity of union-find with both path compression and union by rank?
A: Combined, both optimizations give an amortized time complexity of O(α(n)) per operation, where α is the inverse Ackermann function — a value that grows so slowly it is effectively a small constant (never exceeding about 4 or 5) for any n that could realistically be represented in memory. In practice, interview answers commonly simplify this to "O(1) amortized" or "nearly O(1)."
Q85. How is union-find used to detect a cycle while building a graph edge by edge?
A: Before adding each edge (u, v), call find(u) and find(v); if they return the same root, u and v are already connected through some other path, so this new edge would close a cycle — reject or flag it. Otherwise call union(u, v) to merge their components and proceed. This same check-then-merge pattern is exactly what Kruskal's algorithm relies on internally.
boolean hasCycleUnionFind(int[][] edges, int V) {
UnionFind uf = new UnionFind(V);
for (int[] edge : edges) {
if (!uf.union(edge[0], edge[1])) return true; // union failed -> cycle
}
return false;
}Q86. How exactly does Kruskal's algorithm rely on union-find internally?
A: After sorting edges by weight, Kruskal's calls find() on each edge's two endpoints to check if they're in the same set; if not, it adds the edge to the MST and calls union() to merge the sets, gradually merging separate components into one as cheaper edges get consumed first. This guarantees the final result is both cycle-free and minimal in total weight, since greedily picking the cheapest "safe" edge at every step is provably optimal for MST construction (the cut property).
Q87. What is the difference between calling find() with and without path compression?
A: Without path compression, find() just walks up parent pointers to the root and returns it, leaving the tree structure unchanged — repeated calls on a deep chain repeat the same full-length walk every time, potentially degrading to O(n) per call in the worst case. With path compression, every node visited along the way gets its parent pointer redirected straight to the root during the walk, so subsequent lookups on those same nodes become O(1), amortizing the cost across many operations.
Q88. What is a bipartite graph?
A: A bipartite graph is one whose vertices can be split into exactly two disjoint sets such that every edge connects a vertex in one set to a vertex in the other — no edge ever connects two vertices within the same set. Equivalently, a graph is bipartite if and only if it contains no odd-length cycle.
Q89. How do you check if a graph is bipartite using BFS 2-coloring?
A: Assign the starting vertex color 0, then BFS outward, coloring every newly discovered neighbor the opposite color of its parent. If you ever encounter an already-colored neighbor whose color matches the current vertex's color, the graph is not bipartite (an odd cycle exists); if BFS completes without any such conflict, it is bipartite. This must be repeated per connected component if the graph is disconnected.
boolean isBipartite(List<List<Integer>> adj, int V) {
int[] color = new int[V];
Arrays.fill(color, -1);
for (int start = 0; start < V; start++) {
if (color[start] != -1) continue;
color[start] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int nbr : adj.get(node)) {
if (color[nbr] == -1) {
color[nbr] = 1 - color[node];
queue.offer(nbr);
} else if (color[nbr] == color[node]) {
return false; // same-color neighbors -> not bipartite
}
}
}
}
return true;
}Q90. How do you check bipartiteness using DFS instead of BFS?
A: The logic is identical — assign colors and check for conflicts — but implemented via recursion: color the current vertex, then recurse into each uncolored neighbor with the opposite color, returning false immediately if a same-colored neighbor is ever found. Both approaches are O(V+E) time; the choice between BFS and DFS here is purely a matter of implementation style.
Q91. What real-world problems map to checking bipartiteness?
A: Bipartite checks come up in job-matching (workers vs. jobs, forming a bipartite graph for the assignment problem / Hungarian algorithm), scheduling conflicts (can tasks be split into two non-conflicting shifts), and social network analysis (detecting two-community structures with no intra-community edges, like a graph of "must alternate" constraints).
Q92. What is the graph coloring problem?
A: Graph coloring assigns a color (label) to every vertex such that no two adjacent vertices share the same color, typically while trying to minimize the number of distinct colors used. It models resource-conflict problems directly — e.g., assigning exam time slots so no student has two exams simultaneously, or register allocation in compilers where colors represent physical registers.
Q93. What is a simple greedy approach to graph coloring, and what is its limitation?
A: Process vertices in some order, assigning each the smallest color not already used by any of its already-colored neighbors. This is fast (O(V+E)) but does not guarantee the minimum possible number of colors — the result depends heavily on vertex ordering, and a poor ordering can use far more colors than the true chromatic number requires.
Q94. What is the chromatic number of a graph?
A: The chromatic number is the minimum number of colors needed to color a graph such that no two adjacent vertices share a color. Determining the exact chromatic number is NP-hard in general, though special cases have known answers — a bipartite graph's chromatic number is always exactly 2 (as long as it has at least one edge), and a graph containing a triangle needs at least 3.
Q95. How does a backtracking approach solve the m-coloring problem (can the graph be colored with exactly m colors)?
A: Try assigning each vertex, in order, one of the m available colors that doesn't conflict with already-colored neighbors; recurse to the next vertex, and backtrack (try a different color, or fail) if no color works or a later vertex gets stuck. This explores the coloring space exhaustively and is exponential in the worst case, but with pruning it is the standard way to answer "is m colors enough" exactly, since the greedy approach can't guarantee optimality.
boolean canColor(boolean[][] graph, int m, int[] colors, int vertex, int V) {
if (vertex == V) return true;
for (int c = 1; c <= m; c++) {
boolean safe = true;
for (int i = 0; i < V; i++) {
if (graph[vertex][i] && colors[i] == c) { safe = false; break; }
}
if (safe) {
colors[vertex] = c;
if (canColor(graph, m, colors, vertex + 1, V)) return true;
colors[vertex] = 0; // backtrack
}
}
return false;
}Q96. How do you clone a graph (deep copy) that may contain cycles?
A: Traverse the original graph (BFS or DFS) while maintaining a map from original node references to their newly created clone. When visiting a node for the first time, create its clone and store it in the map before recursing/enqueuing into its neighbors, so that if a cycle brings you back to an already-cloned node, you reuse the existing clone instead of creating a duplicate or looping forever.
Q97. How do you implement clone graph using BFS and a HashMap in Java?
A: Create a clone of the start node and put the mapping in a HashMap first. Then BFS: for each original node dequeued, iterate its neighbors — if a neighbor hasn't been cloned yet, clone it, map it, and enqueue it; either way, add the (already-existing-or-just-created) clone to the current node's clone's neighbor list.
Node cloneGraph(Node start) {
if (start == null) return null;
Map<Node, Node> map = new HashMap<>();
map.put(start, new Node(start.val));
Queue<Node> queue = new LinkedList<>();
queue.offer(start);
while (!queue.isEmpty()) {
Node cur = queue.poll();
for (Node neighbor : cur.neighbors) {
if (!map.containsKey(neighbor)) {
map.put(neighbor, new Node(neighbor.val));
queue.offer(neighbor);
}
map.get(cur).neighbors.add(map.get(neighbor));
}
}
return map.get(start);
}Q98. Why is the original-to-clone HashMap essential for correctly cloning a cyclic graph?
A: Without it, revisiting a node already reached by a different path (guaranteed in any graph with a cycle) would either create a second, redundant clone of that node — breaking the structural equivalence with the original — or cause infinite recursion/looping if there's no way to recognize "I've already handled this node." The map lets the traversal recognize already-cloned nodes in O(1) and immediately reuse their clone reference instead of reprocessing them.
Q99. What is the "number of islands" problem, and how is it a graph problem in disguise?
A: Given a 2D grid of land (1) and water (0) cells, count the number of islands, where an island is a maximal group of land cells connected horizontally or vertically. It's exactly the "count connected components" problem, except the graph is implicit — grid cells are vertices, and adjacency is defined by grid position rather than an explicit edge list.
Q100. How do you implement "number of islands" using DFS flood fill in Java?
A: Scan every cell; whenever an unvisited land cell is found, increment the island count and run a DFS (or BFS) that marks every reachable land cell from it as visited ("sinks" the island), so it's never counted again. This is O(rows × cols) time since every cell is visited a constant number of times.
int numIslands(char[][] grid) {
int count = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == '1') {
count++;
sink(grid, r, c);
}
}
}
return count;
}
void sink(char[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != '1') return;
grid[r][c] = '0'; // mark visited by sinking it
sink(grid, r + 1, c); sink(grid, r - 1, c);
sink(grid, r, c + 1); sink(grid, r, c - 1);
}Q101. How would you solve "number of islands" using Union-Find instead of DFS?
A: Treat every land cell as its own set initially, then for each land cell, union it with any adjacent land cell (right and down are enough if you scan left-to-right, top-to-bottom, since earlier neighbors were already handled). The final answer is the number of distinct roots among land cells. This approach is especially handy for a streaming variant of the problem (e.g., "add land at (r, c) and report island count after each addition"), where DFS would require re-scanning from scratch each time.
Q102. How do you count islands using BFS instead of DFS, and does the result differ?
A: The result is identical — only the traversal mechanics change. Instead of recursively sinking neighbors, enqueue the starting land cell, and repeatedly dequeue a cell, mark it visited, and enqueue any of its unvisited land neighbors, exactly like grid BFS. BFS is often preferred here to avoid recursion-depth issues on very large, densely-connected islands.
void bfsSink(char[][] grid, int sr, int sc) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{sr, sc});
grid[sr][sc] = '0';
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == '1') {
grid[nr][nc] = '0';
q.offer(new int[]{nr, nc});
}
}
}
}Q103. What is the "word ladder" problem, and why is BFS the right tool for it?
A: Given a start word and end word, and a dictionary of valid words, word ladder asks for the shortest sequence of single-letter transformations from start to end, where every intermediate word must also be in the dictionary. Each word is effectively a vertex, and an edge connects two words that differ by exactly one letter; since every edge has an implicit weight of 1 (one transformation step), BFS is exactly the right tool to find the shortest transformation sequence.
Q104. What is a Java approach outline for solving word ladder's shortest transformation length?
A: Put all dictionary words in a HashSet for O(1) lookup, then BFS from the start word: for each word dequeued, generate every possible one-letter variation (26 possibilities per position), and if a variation is in the dictionary and unvisited, mark it visited and enqueue it with distance+1. Return the distance the moment the end word is dequeued.
int ladderLength(String start, String end, Set<String> dict) {
Queue<String> queue = new LinkedList<>();
queue.offer(start);
int steps = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String word = queue.poll();
if (word.equals(end)) return steps;
char[] chars = word.toCharArray();
for (int pos = 0; pos < chars.length; pos++) {
char original = chars[pos];
for (char c = 'a'; c <= 'z'; c++) {
chars[pos] = c;
String candidate = new String(chars);
if (dict.remove(candidate)) queue.offer(candidate);
}
chars[pos] = original;
}
}
steps++;
}
return 0;
}Q105. How do you build the implicit graph for word ladder without enumerating every pair of words?
A: Rather than precomputing an O(n²) adjacency list by comparing every pair of dictionary words for a one-letter difference, generate a word's neighbors on the fly during BFS: for each of its positions, substitute all 26 letters and check dictionary membership directly (O(word length × 26) per word). This avoids the quadratic pairwise comparison entirely and scales much better for large dictionaries.
Q106. What is bidirectional BFS, and how does it speed up shortest-path problems like word ladder?
A: Bidirectional BFS runs two simultaneous BFS frontiers — one expanding forward from the source, one expanding backward from the target — alternating which one advances a level, and stops as soon as the two frontiers meet. Since BFS's frontier size grows roughly exponentially with distance, meeting in the middle at half the distance from each side reduces the explored search space from roughly b^d to about 2×b^(d/2), a dramatic practical speedup for large branching factors like word ladder's 26-letters-per-position.
Q107. What is the difference between a spanning tree and a minimum spanning tree?
A: Any spanning tree connects all V vertices using exactly V-1 edges with no cycles — a graph can have many different spanning trees. A minimum spanning tree is specifically the one (or one of the ones, if there are ties) among all possible spanning trees whose total edge weight is the smallest; on an unweighted graph, every spanning tree is trivially an MST since all edge weights are equal.
Q108. What is an Euler path/circuit, and what is Euler's theorem for its existence?
A: An Euler path traverses every edge of a graph exactly once (not necessarily returning to the start); an Euler circuit does the same but also returns to the starting vertex. Euler's theorem states an undirected connected graph has an Euler circuit if and only if every vertex has even degree, and has an Euler path (but not a circuit) if and only if exactly two vertices have odd degree.
Q109. What is a Hamiltonian path, and why is finding one NP-hard in general?
A: A Hamiltonian path visits every vertex in the graph exactly once (a Hamiltonian circuit additionally returns to the start). Unlike Euler paths, there is no known simple degree-based characterization for when one exists, and determining whether a Hamiltonian path exists is NP-complete — the best known general algorithms are exponential (backtracking or DP over subsets), making it intractable for large graphs.
Q110. How do you verify that a given connected graph is actually a tree?
A: A connected undirected graph with V vertices is a tree if and only if it has exactly V-1 edges and contains no cycle — checking the edge count is O(1) if known upfront, and a single DFS/BFS (or union-find over all edges) confirms both connectivity and the absence of a cycle in O(V+E) time. If the edge count doesn't equal V-1 exactly, it cannot possibly be a tree regardless of any other check.
boolean isTree(List<List<Integer>> adj, int V, int E) {
if (E != V - 1) return false; // wrong edge count -> cannot be a tree
boolean[] visited = new boolean[V];
dfs(adj, 0, visited);
for (boolean v : visited) if (!v) return false; // not connected
return true;
}Q111. What is the difference between A* search and Dijkstra's algorithm?
A: Dijkstra's expands vertices purely by their known cumulative distance from the source. A* adds a heuristic estimate of the remaining distance to a specific target (e.g., straight-line distance on a map) to that priority, so it explores far fewer vertices by preferring ones that seem "closer to the goal" — as long as the heuristic never overestimates the true remaining distance (admissibility), A* still guarantees the optimal shortest path, just typically much faster in practice for single-target queries.
Q112. How would you serialize and deserialize a graph for storage or network transmission?
A: A common approach serializes the graph as an edge list (and vertex count/labels), since that format is compact and representation-agnostic — writing each edge as "u,v[,weight]" per line or as a JSON array of triples. Deserialization then just rebuilds whichever in-memory representation (adjacency list or matrix) the consuming algorithm needs, reconstructing the vertex set from either an explicit count or by scanning all edge endpoints.
String serialize(int[][] edges) {
StringBuilder sb = new StringBuilder();
for (int[] e : edges) sb.append(e[0]).append(",").append(e[1]).append(",").append(e[2]).append(";");
return sb.toString();
}
List<List<Edge>> deserialize(String data, int V) {
List<List<Edge>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
for (String token : data.split(";")) {
if (token.isEmpty()) continue;
String[] parts = token.split(",");
adj.get(Integer.parseInt(parts[0])).add(new Edge(Integer.parseInt(parts[1]), Integer.parseInt(parts[2])));
}
return adj;
}
Post a Comment
Add