PPractick

The problem

A routing library must store undirected graphs of very different shapes: tiny dense ones where "is there a direct link from u to v?" must be instant, and huge sparse road networks where memory matters. Build both standard representations from an edge list:

• an adjacency matrix, n × n, where M[u][v] = 1 if there's an edge (O(1) lookup, O(V²) memory)
• an adjacency list, where adj[u] holds u's neighbours (O(V + E) memory, fast neighbour iteration)

Then print them to show the two agree.

Example: n = 4, edges [[0,1], [0,2], [1,2], [2,3]] → list 0:[1,2] 1:[0,2] 2:[0,1,3] 3:[2], matrix rows 0110 1010 1101 0010.

Function signature

vector<vector<int>> toAdjList(int n, const vector<pair<int, int>>& edges);
vector<vector<char>> toAdjMatrix(int n, const vector<pair<int, int>>& edges);

Test cases

Input (n, edges)	Output	Explanation
(4, [[0,1],[0,2],[1,2],[2,3]])	0:[1,2] 1:[0,2] 2:[0,1,3] 3:[2] matrix 0110 1010 1101 0010
(5, [[0,4],[1,3]])	0:[4] 1:[3] 2:[] 3:[1] 4:[0] matrix 00001 00010 00000 01000 10000	Vertex 2 is isolated
(2, [[0,1]])	0:[1] 1:[0] matrix 01 10
(3, [])	0:[] 1:[] 2:[] matrix 000 000 000	No edges

(Confirm: the graph is undirected, so each edge appears in both endpoints' lists and the matrix is symmetric; vertices are 0..n−1.)

How interviewers phrase it

• "How would you represent a graph in C++? Build the adjacency list and adjacency matrix from an edge list and compare them."

Clarifying questions to ask

1. Directed or undirected? Weighted? (Undirected and unweighted here.)
2. How many vertices and edges? (That decides between a matrix and a list.)
3. Are the vertices 0- or 1-indexed?

Follow-ups to expect

1. "When is a matrix better?"
2. "When is a list better?"
3. "How do weights change things?"
4. "Directed graphs?"
5. "Edge list?"

Related questions

• Introduction to Graph Easy
• Graph Representation | Java Easy
• MST theory Easy
• M Coloring Problem Hard
• Celebrity Problem Hard
• Connected Components Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in