Question 1

Explain the difference between an adjacency list and an adjacency matrix, and say when you pick each.

Accepted Answer

Split the answer into three parts: what it stores → what it costs → when I choose it. (1) What it stores: the list keeps a list of neighbours per vertex; the matrix is a V × V table where matrix[u][v] says whether the edge exists. (2) What it costs: the list is O(V + E) memory, O(deg(u)) to iterate neighbours and O(deg(u)) for an edge check. The matrix is O(V²) memory, O(1) for an edge check, but O(V) to iterate neighbours — you have to read the whole row. (3) The choice: I default to the list, because real graphs are sparse and BFS/DFS/Dijkstra all iterate neighbours. I pick a matrix only when the graph is small and dense, or when the algorithm itself is matrix-based (Floyd-Warshall, say). Add a concrete example — that is what makes the answer memorable: "On a social graph of a million users a matrix would need 10¹² cells; the list holds roughly 3 million elements." If you want to show depth, add one more sentence: "If it's sparse but I also ask 'does this edge exist?' constantly, I store neighbours as a Set rather than a list — that gives an O(1) check without going to a matrix."

Question 2

You are handed data about "microservices calling each other". How would you model it and what would you ask?

Accepted Answer

This tests whether you recognise a graph problem — structure the answer as the model → clarifying questions → what I can then compute. The model: vertex = service, edge = "service A calls B". The edge is directed, because a call goes one way. I can put the call count or average latency on it as a weight. Clarifying questions: how many services (V) and how many distinct call pairs (E)? Is the data static or updated live? Should repeated calls be merged into one edge or kept individually? What I can compute — this part makes the answer strong, because it shows the value of the model: find circular dependencies with cycle detection; derive a safe deploy order with a topological sort; find the blast radius of one service going down with BFS on the reversed graph; identify "critical" services by in-degree. Representation: with services in the hundreds this is a sparse graph — an adjacency list, Map>.

Question 3

How does the difference between a directed and an undirected graph show up in code?

Accepted Answer

The most compact answer: an undirected graph is a directed graph where every edge is stored twice. In code the difference is a single line — inside addEdge(u, v) the undirected case also does adj[v].push(u). With a matrix you fill matrix[v][u] alongside matrix[u][v], so the matrix becomes symmetric. Then say why it matters, because that is what is being assessed: In an undirected graph E edges create 2E entries — don't forget that in the memory estimate Cycle detection with DFS is written completely differently: undirected, you must exclude the parent you came from or every edge looks like a fake cycle; directed, you must track the nodes currently on the recursion stack In a directed graph in-degree and out-degree are separate notions, and topological sort is built on in-degree If they want an example: an Instagram follow is directed ("followers" and "following" are different lists), a LinkedIn connection is undirected.

Question 4

How does a graph being 'sparse' or 'dense' affect your decisions?

Accepted Answer

Start with the definition in one sentence: sparse means E is close to V; dense means E is close to V². Most real-world graphs are sparse, because a person can have a thousand friends but not a million. Then give three concrete consequences: Representation: sparse → adjacency list; dense → a matrix becomes reasonable (memory is near V² anyway, and you gain O(1) edge checks) Reading complexity: O(V + E) is effectively O(V) when sparse and O(V²) when dense. The same algorithm behaves completely differently on the two — saying that out loud is a strong signal Algorithm choice: Dijkstra with a binary heap is O((V + E) log V), excellent on sparse graphs; on a very dense graph the simple array-based O(V²) variant can be faster because it has no heap-operation constant That last point is a senior-level detail — you don't have to volunteer it if you're unsure, but if you know it, it noticeably strengthens the answer.

Question 5

When do you NOT need to write a separate graph class?

Accepted Answer

This question tests pragmatism. The answer: when the graph already exists in the data. Three typical cases: Grid/matrix problems (islands, flood fill, mazes) — each cell is a vertex and neighbours come from the offsets [[0,1],[1,0],[0,-1],[-1,0]]. Building a Graph class is 20 extra lines and extra memory State problems — vertices are generated combinatorially (the digit combinations of a lock, say). Building the whole graph up front is impossible and unnecessary: you compute neighbours with a function as BFS proceeds A plain edge list you only need to traverse once — sometimes a Map> is enough and no class is warranted Phrase it in the interview like this: "The graph here is implicit — cells are vertices and adjacent cells are edges. I won't build a structure, I'll compute neighbours on the fly; that saves O(V) extra memory." That sentence shows both that you recognise the pattern and that you don't build needless abstraction — the second is worth no less than the first in real work.

Operation	Adjacency list	Adjacency matrix
Memory	O(V + E)	O(V²) — independent of edge count
Add an edge	O(1)	O(1)
Check "is there a u–v edge?"	O(deg(u)) — you scan the neighbours	O(1) — direct index
Iterate all neighbours of u	O(deg(u)) — optimal	O(V) — you must read the whole row
Remove an edge	O(deg(u))	O(1)
When it wins	Sparse graphs, BFS/DFS, real networks	Small dense graphs, frequent edge checks, matrix algorithms (Floyd-Warshall)

Graph representation