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 QA: 25
Edition: v7
Editorial status: Reviewed
Relevant for: AI EngineerBackend EngineerBlockchain DeveloperComputational BiologistData ScientistEmbedded Systems EngineerFrontend EngineerFull-Stack DeveloperMachine Learning EngineerQuantum Software EngineerRobotics EngineerSoftware Engineer

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

Interview QA

Treat each question like a live interview question: answer out loud first (structure, assumptions, tradeoffs), then open the model answer to spot gaps and rehearse a tighter follow-up.

Curated: 2026-10-05 · Written: 2026-10-05 · Reviewed: 2026-10-03

QA-1

Explain modelling a problem as a graph and how it changes a production decision.

QA-2

How would you reason about adjacency list versus adjacency matrix in a system you own?

QA-3

Walk through complexity in terms of V and E, including where engineers most often get it wrong.

QA-4

What does breadth-first search and shortest paths guarantee, and what does it deliberately leave open?

QA-5

Describe marking visited at enqueue time and the evidence you would collect before relying on it.

QA-6

When is depth-first search the right traversal for a graph problem, and when is breadth-first search the better tool?

QA-7

Where does recursion depth in depth-first search matter, and where is it irrelevant?

QA-8

Teach cycle detection in directed graphs to an engineer who has only seen it as a rule of thumb.

QA-9

How do you detect a cycle in an undirected graph, and why does the standard directed-graph method fail here?

QA-10

How does Kahn's algorithm detect cycles during topological sorting, and how does its practical behavior differ from depth-first search (DFS) cycle detection in directed graphs?

QA-11

Given a DAG, how do you tell whether its topological order is unique, and why is counting all valid orders a different class of problem?

QA-12

How does connected components change if the workload grows by two orders of magnitude?

QA-13

Explain the time complexity of Disjoint Set Union with both path compression and union by rank, and describe a scenario where path compression alone is insufficient.

QA-14

When would you refuse a design because of dijkstra's algorithm?

QA-15

How would you explain the priority queue in Dijkstra without using the usual slogan?

QA-16

How does the Bellman-Ford algorithm detect negative weight cycles in a directed graph, and why does Dijkstra's algorithm fail when negative edge weights are present?

QA-17

You need single-source shortest paths in a graph where every edge weight is 0 or 1. How do you do better than Dijkstra here, and why does your approach work?

QA-18

Given several source nodes (or cells), find the distance from every node to its nearest source. How do you answer that in one traversal instead of one search per source?

QA-19

When is bidirectional search preferred over unidirectional BFS or Dijkstra, and what exact termination conditions guarantee the shortest path?

QA-20

What trade-off does grids as implicit graphs force that a junior answer usually skips?

QA-21

Problems like Word Ladder, a sliding puzzle, or minimum moves to reach a target are usually solved as graph search, but the graph is never given to you. How do you model one of these as a state-space graph and keep the search tractable?

QA-22

Your search returns the length of the shortest path, but the interviewer wants the path itself. How do you reconstruct it?

QA-23

How does bipartite testing interact with rollback, and where do people ignore that?

QA-24

What causes frontier and state memory exhaustion in large graph traversals, and how do iterative deepening and external-memory techniques mitigate it?

QA-25