Skip to content
Tech Interview Prep
Technical interview guide

Advanced Graphs

Weighted shortest paths and connectivity beyond plain BFS/DFS: Dijkstra, Union-Find, and minimum spanning trees.

Read
46 min
Practice MCQs
25
Interview Q&A
25
Edition
v7
Editorial status
Reviewed

Scope: Language-neutral, with implementation notes referring to CPython 3.14 containers.

Curated: · Written: · Reviewed:

25 questions

MCQ-23A scheduler is given six tasks with these precedence constraints: A before B, A before C, B before D, C before D, D before E, and E before A. The team must decide whether any valid execution order exists. Which conclusion is correct?
MCQ-4A deploy tool prints release units for a call graph: two services land in the same unit exactly when each can reach the other over the call edges, and a unit is never split further. The recorded graph is A->B, B->C, C->A, C->D, D->E, E->D, F->D, G->F, where X->Y means X calls Y. How many units does the tool print, and which unit is the largest?
MCQ-5A monorepo build graph has 240,000 targets and 1.1M dependency edges. 3,400 targets sit in cycles, mutually recursive modules that form strongly connected components, and the rest form a DAG. The team needs each target's transitive dependency set and a build order. Their current DFS with a visited set sometimes emits a target before one of its dependencies. Which change fixes both outputs?
MCQ-6An undirected service graph has edges A-B, B-C, C-A, C-D. A DFS from A discovers A, B, C, D in that order. The low-link values are low[A]=1, low[B]=1, low[C]=1, low[D]=4. Which edge is a bridge, and which vertex is an articulation point?
MCQ-1A network team must connect five sites A–E with leased lines. Edge weights are monthly cost in thousands of dollars: A–B 1, B–C 1, A–C 1.5, C–D 2, D–E 2, B–D 4, C–E 5. They run Kruskal's algorithm to pick the minimum-cost set of lines that connects all five sites. Separately, they need the cheapest route from A to C for live traffic. Which statement is correct?
MCQ-2A network-design tool must compute a minimum spanning tree over a dense graph: V = 5,000 nodes and E = 12,000,000 edges, close to the V(V−1)/2 ≈ 12.5M maximum. The full adjacency matrix is already in memory. Which implementation is fastest here, and roughly how many operations does it take?
MCQ-3A connectivity index is built over n = 2^20 ≈ 1,048,576 nodes. The build runs 1,048,575 unions in an order that always hangs the larger tree's root under the smaller tree's root, leaving one chain of that length. find() applies path compression; union applies no rank or size rule. The service then runs 1,000,000 finds. Which statement about the find phase is correct?
MCQ-22A team builds offline dynamic connectivity with a segment tree over time and a DSU that uses union by rank (ties attach the second root under the first) plus path compression, pushing every union onto a rollback stack. Testing on vertices 0–3, they run union(0,1), union(2,3), union(0,2), call find(3), then roll back the last union. A connectivity query for 3 and 0 now returns true, although edge (0,2) has been removed. What explains the wrong result?
MCQ-19A nightly build pipeline is a DAG with six stages. Edge weights are stage durations in minutes: A→B 3, A→C 1, B→D 4, C→D 2, C→E 7, D→F 1, E→F 2. A is the source and F the sink. An engineer relaxes the edges in the order A, B, D, C, E, F, keeping one min-distance array initialised to ∞ except dist[A] = 0. What does the pass report for the shortest A→F distance, and why?
MCQ-9A* runs on this directed graph with f = g + h, ties broken by insertion order: S→A = 1, S→B = 10, A→B = 1, A→G = 100, B→G = 10 Heuristic: h(S) = 12, h(A) = 11, h(B) = 0, h(G) = 0 Which outcome does the search produce?
MCQ-20A directed graph has edges A→B (weight 1), B→D (1), A→C (5), C→D (5), and B→C (1). You need the second-shortest simple path from A to D. A teammate proposes running Dijkstra, deleting every edge on the shortest path, and rerunning Dijkstra. What does that procedure return, and what is the true second-shortest simple path?
MCQ-7A team implements Floyd-Warshall with the loops ordered for i, for j, for k (k innermost). The directed graph has edges 0→1 weight 10, 0→3 weight 1, 3→2 weight 1, 2→1 weight 1, and all other pairs ∞. What value does their d[0][1] end up as, and why?
MCQ-24A team implements Floyd–Warshall on a 4-node directed graph with a single `dist[][]` matrix, initialising `dist[i][i] = 0` and `dist[i][j]` to the edge weight or ∞. The edges are 0→1 (1), 1→3 (1), 3→2 (1), 0→2 (10), and 1→2 (20). The triple loop runs with the intermediate-vertex loop `k` as the innermost loop, updating `dist[i][j]` in place. What does the routine report for `dist[0][2]`, and why?
MCQ-10In a directed flow network with source $s$ and sink $t$, a feasible s-t flow $f$ has value $12$. For the cut $(S,T)$ with $s \in S$ and $t \in T$, the forward edges $(S \to T)$ have total capacity $20$, and the backward edges $(T \to S)$ carry a total of $3$ units of flow. Which statement is correct?
MCQ-11A max-flow service runs on a network with V = 2,000 nodes and E = 20,000 edges, where capacities are byte counts up to 10^9. Its implementation finds each augmenting path with DFS and pushes the bottleneck along it. On a test network with maximum flow 4×10^9 it performs roughly 4×10^9 augmentations and takes hours; dividing every capacity by 10^6 leaves the graph structure identical, drops the maximum flow to 4,000, and the same code finishes in under a second. Which conclusion does this measurement support?
MCQ-8A ride-hailing service matches 10,000 drivers to 10,000 trip requests. The bipartite graph has 1,000,000 edges and a maximum matching of 9,800. The team's first implementation runs the unit-capacity max-flow reduction with Ford-Fulkerson using DFS augmenting paths; each augmentation scans the residual graph in O(V+E) with V = 20,002 and E = 1,020,000. A colleague proposes replacing it with Hopcroft-Karp. Which outcome should the team expect?
MCQ-17An exam scheduler colours a conflict graph over four exams A, B, C, D whose conflicts are A-B, B-C and C-D. Greedy, run in the vertex order A, C, B, D, reports that 3 rooms are needed. What should the team do?
MCQ-14A courier must drive every street in a connected district exactly once, starting and ending at the depot. The intersection degrees are: depot 4, A 3, B 3, C 2, D 2, E 4. What follows?
MCQ-12Which statement correctly describes the Hamiltonian path decision problem on an arbitrary directed graph G = (V, E) and the verification of a candidate certificate?
MCQ-15In an interview, a candidate must justify that Hamiltonian Path is NP-complete by reduction. Which statement about the standard reduction is correct?
MCQ-13A team needs the minimum-weight Hamiltonian path that starts at a fixed vertex s and ends at a fixed vertex t in a directed graph with V vertices. They use bitmask DP. Which recurrence and complexity are correct?
MCQ-16A last-mile routing service must solve TSP exactly over n = 24 stops using the standard bitmask DP dp[mask][v], with each entry an 8-byte double, inside a 4 GB container. Which conclusion about the table size and transition count is correct?
MCQ-25A team's exact solver for a scheduling problem runs in O(2^n · n^2). On the target machine an n = 25 instance takes 4 seconds. The product must solve n = 50 instances inside a 5-minute batch window. The problem is NP-hard (reduction from 3-SAT). Which line belongs in the design review?
MCQ-18A courier firm has four depots with symmetric distances in km: d(P,Q)=2, d(Q,R)=3, d(R,S)=2, d(P,R)=5, d(Q,S)=5, d(P,S)=40. They build a minimum spanning tree (P-Q, Q-R, R-S; total 7), double its edges, and shortcut the Euler tour P-Q-R-S-R-Q-P into the Hamiltonian cycle P-Q-R-S-P, claiming the result is within twice the optimum. Which assessment is correct?
MCQ-21A team's single-machine BFS over a directed web graph (8 billion edges, 2 billion vertices, CSR with 4-byte ids: 32 GB edge array + 8 GB offsets) OOMs on a 64 GB box at the widest level. There the frontier holds 1.5 billion vertices, and the engine materializes one 16-byte message per out-edge of each frontier vertex; average out-degree is 4. Which change addresses the actual cause?