DSA interview question

Disjoint Set Union (Union by Size + Path Compression)

Hard · Data structures · Topics: graph, dsu, union find

The problem

A social platform receives a stream of "A and B are now connected" events and "are A and B in the same group?" queries, millions of each. Recomputing connectivity every time is hopeless. A disjoint set union (DSU, union-find) keeps each group as a tree with a representative root. find follows parent links to the root, compressing the path so later calls are nearly instant. union attaches the smaller tree under the larger one. Together these give amortised O(α(n)), effectively constant time per operation.

Example: n = 5: union(0,1), union(2,3), same(0,1) → true, same(1,2) → false, union(1,3), same(0,2) → true.

Function signature

class DisjointSet {
public:
    explicit DisjointSet(int n);
    int find(int x);
    bool unite(int a, int b);   // false if already in the same set
    bool same(int a, int b);
};

Test cases

Operations (n)	Output	Explanation
(5) `U 0 1, U 2 3, F 0 1, F 1 2, U 1 3, F 0 2`	`true false true`	Two groups merge
(3) `U 0 1, U 1 2, F 0 2`	`true`	Connected through 1
(4) `U 0 1, U 2 3, F 0 3`	`false`
(2) `U 0 1, U 0 1, F 1 0`	`true`	A repeated union is harmless
(3) `F 0 0`	`true`	Every element is in its own set

(Confirm: elements are 0..n−1; "F a b" asks whether a and b are in the same set.)

How interviewers phrase it

"Implement a Disjoint Set Union data structure with union by rank/size and path compression" (GeeksforGeeks "Disjoint set (Union-Find)").

Clarifying questions to ask

Which operations are needed? (find, union, and a same-set query.)
How many elements and operations? (Up to about 10⁵–10⁶, so near-constant time per operation.)
Do I need the set sizes? (Union by size gives them for free.)

Follow-ups to expect

"What does path compression do?"
"Why union by size or rank?"
"What's α(n)?"
"Where is DSU used?"
"Can it support deletions?"

Practise questions like this with a real engineer

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 interview