PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Medium
  • Motive
  • Coding & Algorithms
  • Software Engineer

Implement Union-Find for connectivity

Company: Motive

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Implement a Disjoint Set Union (Union-Find) data structure with path compression and union by rank. Support operations: make_set, find(x), union(x, y), and connected(x, y). Then, given an undirected graph with n nodes labeled 1..n and a list of edges, process q online connectivity queries efficiently. Analyze time and space complexity, and discuss edge cases such as duplicate unions and isolated nodes.

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.

Implement a Disjoint Set Union (Union-Find) data structure with path compression and union by rank, then use it to answer connectivity queries on an undirected graph. You are given an integer `n` (nodes are labeled `1..n`), a list of undirected `edges` where each edge `[a, b]` connects nodes `a` and `b`, and a list of `queries` where each query `[x, y]` asks whether nodes `x` and `y` are connected (i.e. reachable from one another through the edges). First union all the edges, then answer each query in order. Return a list of booleans: `true` if `x` and `y` are in the same connected component, `false` otherwise. Notes: - Duplicate or reversed edges (e.g. `[1, 2]` and `[2, 1]`) must be handled gracefully and have no extra effect. - A node is always connected to itself, even if it is isolated (has no edges). - Use path compression in `find` and union by rank in `union` so the amortized cost per operation is nearly O(1). Example: ``` n = 6 edges = [[1, 2], [2, 3], [4, 5]] queries = [[1, 3], [1, 4], [4, 5], [5, 6]] returns [true, false, true, false] ``` Nodes {1,2,3} form one component and {4,5} form another; node 6 is isolated.

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

  1. Maintain a parent array where each node initially points to itself; the root of a tree identifies its component.
  2. In find, follow parent pointers to the root, then re-point every node on the path directly to the root (path compression).
  3. In union, attach the shorter tree under the taller one using a rank array to keep trees shallow.
  4. 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.
Last updated: Jun 26, 2026

Related Coding Questions

  • Implement Union-Find and track components - Motive (Medium)

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.