Graph interview questions, with answers

The questions, with answers

1. 1.How do you represent a graph, and when do you choose a matrix over a list?

   An adjacency matrix is a V × V table where cell [u][v] says whether the edge u to v exists (and its weight): O(V²) space regardless of how many edges there are, O(1) to test an edge, O(V) to list a vertex's neighbours. An adjacency list keeps, for each vertex, a list of its neighbours: O(V + E) space, O(degree) to list neighbours, and O(degree) to test an edge unless the lists are sets. Most real graphs are sparse — a social network has far fewer than V² friendships — so the list wins on memory and makes BFS and DFS run in O(V + E) instead of O(V²). Choose the matrix for dense graphs, for algorithms that ask "is u adjacent to v" constantly, or when V is small enough that V² does not matter.

2. 2.What is the difference between BFS and DFS, and when do you use each?

   BFS explores level by level using a queue: everything at distance 1 from the start, then distance 2, and so on. DFS goes as deep as it can along one path using a stack — usually the recursion stack — and backtracks. Both visit every reachable vertex in O(V + E) with an adjacency list, and both need a visited set to avoid loops. BFS is the choice when distance matters: shortest path in an unweighted graph, the nearest anything, level-order output. DFS is the choice when structure matters: detecting cycles, topological sort, connected components, finding any path, exploring a maze. Memory differs too — BFS holds a whole frontier, which can be huge in a wide graph, while DFS holds one path, which can be deep.

   void bfs(List<List<Integer>> adj, int start) {
       boolean[] seen = new boolean[adj.size()];
       Deque<Integer> q = new ArrayDeque<>();
       q.add(start); seen[start] = true;
       while (!q.isEmpty()) {
           int u = q.poll();
           for (int v : adj.get(u))
               if (!seen[v]) { seen[v] = true; q.add(v); }   // mark when enqueued, not when dequeued
       }
   }

3. 3.How do you find the shortest path in an unweighted graph?

   BFS from the source, recording each vertex's distance as one more than the distance of the vertex it was discovered from. Because BFS discovers vertices in order of distance, the first time a vertex is reached is along a shortest path, and its recorded distance is final — which is why a vertex must be marked visited when it is enqueued, not when it is dequeued. To recover the path itself, store each vertex's parent and walk back from the target. O(V + E). This works only when every edge counts the same; with weights, the first discovery is no longer the cheapest, and you need Dijkstra. A grid maze where each step costs 1 is the most common disguise of this question.

4. 4.How do you detect a cycle, and why is the directed case different?

   In an undirected graph, DFS finds a cycle when it reaches a vertex that is already visited and is not the parent it came from — the parent check matters because the edge you arrived by would otherwise look like a cycle of length two. In a directed graph a visited vertex is not enough evidence: two paths can legitimately converge on the same vertex with no cycle. So the directed version tracks three states — unvisited, on the current recursion stack, and finished — and reports a cycle only when DFS reaches a vertex that is still on the stack, meaning the path has looped back onto itself. The undirected shortcut of union-find also works: an edge whose endpoints are already in the same set closes a cycle. Both are O(V + E).

5. 5.What is a topological sort, and how do you compute one?

   An ordering of the vertices of a directed acyclic graph such that every edge goes from earlier to later — the order you can take courses with prerequisites, or build modules with dependencies. Two standard methods. Kahn's algorithm: compute each vertex's in-degree, repeatedly remove a vertex with in-degree 0 and decrement its neighbours, and output vertices in removal order; if you run out of zero-in-degree vertices before outputting all V, the graph has a cycle, which makes Kahn's algorithm a cycle detector too. DFS: run a DFS and output each vertex when it finishes, then reverse the list. Both are O(V + E). A DAG can have many valid orders; a question that asks for "the" order usually wants any one, or the lexicographically smallest via a min-heap in Kahn's.

6. 6.How does Dijkstra's algorithm work, and what is its complexity?

   Dijkstra finds shortest paths from a source in a graph with non-negative edge weights by always settling the unsettled vertex with the smallest tentative distance, then relaxing its edges — lowering a neighbour's tentative distance when the path through the settled vertex is shorter. A min-heap keyed by tentative distance supplies the next vertex; each edge is relaxed once and each relaxation may push into the heap, so the standard implementation runs in O((V + E) log V). With an adjacency matrix and a linear scan for the minimum it is O(V²), which is better for dense graphs. The precondition is the whole exam question: a negative edge can make a settled vertex wrong, and Bellman-Ford (O(VE)) is the algorithm that tolerates negative weights and detects negative cycles.

7. 7.How do you count connected components, or check whether a graph is connected?

   Loop over every vertex; whenever you meet one that is unvisited, start a BFS or DFS from it and increment a component counter — the traversal marks everything reachable, so each traversal corresponds to exactly one component. The graph is connected if the counter is 1, or equivalently if a single traversal from any vertex visits all V. O(V + E) in total, since every vertex and edge is examined once across all the traversals. Union-find gives the same count incrementally as edges arrive, which is the version for streaming or for Kruskal's algorithm. For directed graphs the notion splits into weakly connected (ignore directions) and strongly connected (paths both ways), the latter needing Kosaraju's or Tarjan's algorithm — name them, but freshers are rarely asked to write them.

8. 8.What is a bipartite graph, and how do you test for one?

   A graph whose vertices can be split into two sets with every edge running between the sets and none inside either — equivalently, a graph that can be two-coloured. Test it with BFS or DFS: colour the start vertex 0, colour each neighbour the opposite of the vertex you came from, and report failure if you ever find an edge whose endpoints already have the same colour. Run it from every unvisited vertex to cover disconnected components. O(V + E). The theorem behind it, worth stating, is that a graph is bipartite exactly when it has no odd-length cycle. Matching problems — students to projects, workers to shifts — are the practical setting, and "can these people be divided into two teams with no rivals on the same team" is the interview disguise.

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 4 on graphs (bfs/dfs/shortest-path basics) and 60 across DSA.