Skip to content
Tech Interview Prep
Technical interview guide

Graphs

Nodes and edges generalizing trees to arbitrary connections: cycles, multiple parents, and disconnected components all allowed.

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

Scope: Language-neutral, with container costs cited from CPython 3.14.

Curated: · Written: · Reviewed:

25 questions

MCQ-10A dependency graph is used to schedule tasks, where edges represent precedence constraints (Task A must finish before Task B). For the scheduling algorithm to successfully produce a complete linear ordering of all tasks, which structural property must the graph satisfy?
MCQ-2An interviewer asks you to compare adjacency list and adjacency matrix on space and on the two operations that matter: testing whether edge (u,v) exists and iterating u's neighbours. Which answer is correct?
MCQ-12A nightly pipeline labels connected components in an undirected interaction graph. A snapshot is stored as CSR-style adjacency lists: a vertex table with one row per registered account, dormant accounts included, and a neighbour array in which every undirected edge appears twice, once in each endpoint's list. One iterative DFS pass steps over the vertex table from the first row to the last, skips any row whose mark is already set in the shared marks array, and starts a traversal at each row it finds unmarked, marking each row as it is dequeued. For a snapshot with V rows and E edges, what is the tightest worst-case time bound on the pass?
MCQ-3A team profiles BFS on two unweighted graphs. Graph A has V = 500,000 vertices and E = 1,500,000 edges. Graph B has V = 5,000 vertices and E = 12,000,000 edges. They expect Graph B to be much faster because it has 100× fewer vertices. Which outcome should they expect?
MCQ-1A robot moves one cell at a time on a 100×100 grid, orthogonally. Three distinct keys sit in fixed cells, and the exit door opens only when all three are held. BFS over cells alone returns a 140-step path that ends at the door, but the robot is refused entry. Which change makes the search return a correct shortest path?
MCQ-21A BFS over a 5×5 grid (25 cells) must collect three keys before it can pass the matching doors. The first implementation keys its visited set on the cell alone and reports the goal unreachable, though a path exists. What vertex identity and vertex count does the fix need?
MCQ-5A build graph has a root target `R` that depends on 10,000 leaf targets `L1`…`L10000`; every leaf depends on the single shared target `core`, and `core` has no dependencies of its own. A breadth-first search from `R` computes distances, and the implementation adds a target to the visited set when it is dequeued rather than when it is enqueued. How many times is `core` pushed onto the queue?
MCQ-4A routing service models its network as a directed graph and runs breadth-first search from source S to find the cheapest route to T. The edges and their latencies are S→A 1 ms, A→T 10 ms, S→B 1 ms, B→C 1 ms, C→T 1 ms. What does BFS return, and is it the minimum-cost route?
MCQ-24A BFS runs over
MCQ-20A warehouse robot plans paths on a 5,000 × 5,000 occupancy grid (25,000,000 cells, 4-directional moves, 2% of cells blocked) stored as one byte per cell. Before each BFS the service precomputes an explicit adjacency list: one entry per free cell listing its free neighbours. The container's 512 MB heap is exhausted during that precomputation. Which change lets the BFS run inside 512 MB?
MCQ-18A routing job fills a 1,000,000-cell grid with each cell's step distance to the nearest of 500 source cells. Today it runs BFS from every source and keeps the per-cell minimum, visiting about 500,000,000 cells in 40 minutes. Which replacement visits about 1,000,000 cells and still stores the true nearest-source distance?
MCQ-23A conflict graph has vertices 0–5 and undirected edges 0–1, 1–2, 2–3, 3–4, 4–5, 5–0, and 0–2. A two-colouring BFS starts at vertex 0, gives it colour 0, and processes each vertex's neighbours in increasing index order, colouring an unvisited neighbour opposite to the vertex it was reached from. What does the traversal return?
MCQ-6A build system has five targets A–E. Edges mean 'must finish before': A→B, A→C, B→D, C→D, D→E, E→C. You run depth-first search from A, visiting each adjacency list in alphabetical order and marking vertices gray on entry, black on exit. What does the traversal report about this graph?
MCQ-8A recursive depth-first search starts at A on the directed graph with edges A→B, A→C, B→D, C→D, D→B, C→E, E→B, E→D, expanding each node's neighbours in alphabetical order. Which traversal confirms that the graph contains a directed cycle?
MCQ-9A mesh health checker looks for cycles in an undirected graph of pod links. It runs DFS from pod 0, marks a pod visited the first time it reaches it, and flags a cycle whenever it sees an edge to an already-visited pod. The links, with each pod's neighbours listed in the order the checker visits them, are: 0: [1]; 1: [0, 2, 3]; 2: [1]; 3: [1]. The checker reports a cycle. Which edge does it flag, and is the report correct?
MCQ-7A build tool loads a dependency graph of 120,000 packages. On production inputs the graph is a near-chain: each package depends on the next, with a few extra edges. The tool runs recursive depth-first search from the root in CPython 3.12, whose default recursion limit is 1000. It passes on the 500-package test fixture and raises RecursionError on production graphs. The fix must not change the order in which packages are visited and must not risk crashing the interpreter. Which change meets both constraints?
MCQ-11A build scheduler computes a topological order for six tasks with dependencies A->B, A->C, B->D, C->D, C->E, D->F, E->F. A test asserts the exact sequence [A, B, C, D, E, F]. After a refactor replaces the FIFO queue with a LIFO stack, the scheduler returns [A, C, E, B, D, F] and the test fails. Which change to the test is correct?
MCQ-13A DSU over the elements 0, 1, …, 10^6 uses path compression on every find but no union by rank or size. Its union(a, b) attaches the root of b's tree directly under the root of a's tree. The workload is union(i+1, i) for i = 0, 1, …, 10^6 − 1, followed by a single find(0). How many parent pointers does that final find(0) follow before it reaches the root?
MCQ-15A Dijkstra run on this directed graph with non-negative weights: edges s→a (1), s→b (4), a→b (1), a→c (5), a→t (11), b→c (1), b→t (10), c→t (1), c→b (1): has settled s and a. The queue holds b with dist[b] = 2, c with dist[c] = 6, and t with dist[t] = 12. The algorithm now extracts b. Which statement is guaranteed at that moment?
MCQ-14A directed graph has source S and target T, with edges S→B = 1, S→A = 100, A→B = -150, and B→T = 5. A team runs Dijkstra's algorithm from S with a min-priority queue and reads the distance it reports for T. What does it report, and what is the true shortest distance from S to T?
MCQ-25A routing service runs Dijkstra with a binary min-heap over a graph of 4,000 nodes and 12,000 directed edges. Edge costs are integer cents, and 300 edges are negative (promotional credits). From the depot, Dijkstra returns a route costing 1,180 cents. An audit finds a valid route costing 940 cents, then another costing 700, then 460, each adding one more traversal of the same three-node loop. What should the team conclude?
MCQ-22A service runs Dijkstra from A on this directed graph: A→B (1), A→C (4), B→C (1), B→D (5), C→D (1). The implementation sets parent[v] only when v is first discovered, never when a later relaxation lowers dist[v]. After the run, dist[D]=3. What does walking parent from D produce, and what does it reveal?
MCQ-17A team implements 0-1 BFS with a deque, marks each vertex visited when it is popped, and pushes zero-weight relaxations to the back of the deque. On the graph s→a (weight 1), s→b (weight 0), b→a (weight 0), what does the run report for dist[a], and what is the correct value?
MCQ-16A routing daemon runs Bellman-Ford from source S on a 4-node graph with edges S→A (weight 1), A→B (−2), B→A (1), B→T (3) and S→T (10). Each round it relaxes every edge once, in that order, for V−1 = 3 rounds, then runs one more round to check for negative cycles. What does the daemon report?
MCQ-19A routing service runs bidirectional Dijkstra on a weighted road graph with non-uniform edge weights. It stops as soon as one node has been settled by both the forward and backward searches and returns the concatenated path. On a 50,000-node test graph it returns a route 8% longer than the true shortest path, and the gap widens as weight variance grows. What should change?