DSA interview question
A social network wants to list its friend circles: groups of users connected directly or through friends of friends, with no connection between different groups. Those groups are the connected components of the friendship graph. Start a DFS (or BFS) from any unvisited user. Everyone it reaches is one component. Repeat from the next unvisited user until everyone has been assigned.
Example: n = 5, edges [[0,1], [1,2], [3,4]] → [[0,1,2], [3,4]].
vector<vector<int>> connectedComponents(int n, const vector<pair<int, int>>& edges);
// each component sorted; components ordered by their smallest vertex
Input (n, edges) | Output | Explanation |
|---|---|---|
(5, [[0,1],[1,2],[3,4]]) | [[0, 1, 2], [3, 4]] | |
(6, [[0,5],[2,4],[5,3]]) | [[0, 3, 5], [1], [2, 4]] | 1 is alone |
(4, [[0,1],[1,2],[2,3]]) | [[0, 1, 2, 3]] | A single chain |
(3, []) | [[0], [1], [2]] | No edges |
(1, []) | [[0]] |
(Confirm: edges are undirected; isolated vertices form their own components.)
On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.
Book a free mock interviewAll 474 dsa interview questions
DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in