How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Motive.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Motive during technical interviews.

Implement Union-Find and track components

Company: Motive

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Implement a Disjoint Set Union (Union-Find) data structure with union by rank and path compression. Design the API to support union(a, b), connected(a, b), and count() for the number of connected components. Given n nodes (0..n- 1) and a stream of operations, return the result of each connected query and the component count after each union. Analyze time and space complexity and discuss thread-safety considerations.

Quick Answer: This question evaluates understanding and implementation of the Disjoint Set Union (Union-Find) data structure, covering union by rank, path compression, API design for union(a, b), connected(a, b), count(), and analysis of time and space complexity.

Implement a Disjoint Set Union (Union-Find) data structure supporting `union(a, b)`, `connected(a, b)`, and a running component count over `n` nodes labeled `0..n-1`. You are given `n` and a list of `operations`. Each operation is a list: - `["union", a, b]` — merge the sets containing `a` and `b`. After processing, append the **current number of connected components** to the result list. - `["connected", a, b]` — append `true` if `a` and `b` are in the same set, else `false`. Return the list of results, one entry per operation, in order. Use **union by rank** and **path compression** so each operation runs in near-constant amortized time. Example: ``` n = 5 operations = [["union",0,1], ["union",2,3], ["connected",0,1], ["connected",0,2], ["union",1,3], ["connected",0,3], ["connected",0,4]] result = [4, 3, true, false, 2, true, false] ``` After unioning 0-1 there are 4 components; after 2-3 there are 3; 0 and 1 are connected (true); 0 and 2 are not (false); unioning 1-3 merges the {0,1} and {2,3} sets leaving 2 components; now 0 and 3 are connected (true); node 4 is still isolated so 0-4 is false.

Constraints

1 <= n <= 10^5
0 <= a, b < n
0 <= number of operations <= 10^5
Each operation type is either "union" or "connected"
Self-operations are allowed (e.g. connected(x, x) is always true; union(x, x) is a no-op that leaves the count unchanged)

Examples

Input: (5, [["union", 0, 1], ["union", 2, 3], ["connected", 0, 1], ["connected", 0, 2], ["union", 1, 3], ["connected", 0, 3], ["connected", 0, 4]])

Expected Output: [4, 3, true, false, 2, true, false]

Explanation: Union 0-1 -> 4 comps; union 2-3 -> 3 comps; 0~1 true; 0~2 false; union 1-3 merges {0,1} and {2,3} -> 2 comps; 0~3 now true; node 4 isolated so 0~4 false.

Input: (1, [["connected", 0, 0]])

Expected Output: [true]

Explanation: A single node is always connected to itself.

Input: (4, [["union", 0, 1], ["union", 1, 2], ["union", 2, 3], ["union", 0, 3]])

Expected Output: [3, 2, 1, 1]

Explanation: Chain unions reduce 4 -> 3 -> 2 -> 1 components. The final union(0,3) is redundant (already in the same set) so the count stays at 1.

Input: (3, [["connected", 0, 1], ["connected", 1, 2]])

Expected Output: [false, false]

Explanation: No unions performed; every node is in its own component, so all connectivity queries are false.

Input: (6, [["union", 0, 1], ["union", 2, 3], ["union", 4, 5], ["union", 1, 2], ["connected", 0, 3], ["connected", 0, 5]])

Expected Output: [5, 4, 3, 2, true, false]

Explanation: Three pairwise unions give 5->4->3 comps; union 1-2 merges {0,1} with {2,3} -> 2 comps; 0~3 true (same merged set); 0~5 false ({4,5} is separate).

Hints

Maintain a parent array where parent[i] points toward the representative (root) of i's set. Initialize parent[i] = i so every node starts in its own component.
find(x) walks to the root. Apply path compression by repointing every node on the path directly to the root, which flattens the tree for future queries.
Use union by rank: attach the shorter tree under the taller one, and only increment rank when two equal-rank roots merge. Decrement the component count only when the two roots actually differ.
connected(a, b) is simply find(a) == find(b). For thread-safety in a concurrent setting you'd guard find/union with a lock or use a lock-free CAS-based union, since path compression mutates shared state.

Quick Overview

This question evaluates understanding and implementation of the Disjoint Set Union (Union-Find) data structure, covering union by rank, path compression, API design for union(a, b), connected(a, b), count(), and analysis of time and space complexity.