Implement Union-Find for connectivity
Company: Motive
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Quick Answer: This question evaluates understanding and implementation of the Disjoint Set Union (Union-Find) data structure—including path compression and union by rank—and competency in processing online connectivity queries on undirected graphs, categorized under Coding & Algorithms in the graph algorithms and data structures domain.
Constraints
- 1 <= n <= 10^5
- 0 <= number of edges <= 2 * 10^5
- 0 <= number of queries <= 2 * 10^5
- 1 <= a, b, x, y <= n
- Edges are undirected; duplicate and reversed edges may appear.
Examples
Input: (6, [[1, 2], [2, 3], [4, 5]], [[1, 3], [1, 4], [4, 5], [5, 6]])
Expected Output: [True, False, True, False]
Explanation: Components: {1,2,3}, {4,5}, {6}. 1-3 connected, 1-4 not, 4-5 connected, 5-6 not.
Input: (1, [], [[1, 1]])
Expected Output: [True]
Explanation: A single isolated node is always connected to itself.
Input: (4, [[1, 2], [1, 2], [2, 1]], [[1, 2], [3, 4]])
Expected Output: [True, False]
Explanation: Duplicate and reversed unions of 1-2 have no extra effect; 3 and 4 stay isolated.
Input: (5, [[1, 2], [3, 4], [4, 5], [2, 3]], [[1, 5], [1, 4], [2, 5]])
Expected Output: [True, True, True]
Explanation: Edges chain all five nodes into one component, so every pair is connected.
Input: (3, [], [[1, 2], [2, 3], [3, 3]])
Expected Output: [False, False, True]
Explanation: No edges: distinct nodes are unconnected, but each node is connected to itself.
Input: (7, [[1, 2], [3, 4], [5, 6]], [[1, 2], [1, 3], [5, 6], [6, 7], [2, 1]])
Expected Output: [True, False, True, False, True]
Explanation: Components {1,2}, {3,4}, {5,6}, {7}; node 7 is isolated, and 2-1 is the same as 1-2.
Hints
- Maintain a parent array where each node initially points to itself; the root of a tree identifies its component.
- In find, follow parent pointers to the root, then re-point every node on the path directly to the root (path compression).
- In union, attach the shorter tree under the taller one using a rank array to keep trees shallow.
- Two nodes are connected exactly when find(x) == find(y). A node is always its own root, so self-queries on isolated nodes return true.