Union-Find with Path Compression and Union by Rank

Reported in interviews at Barclays Citadel

Problem statement

Design a Union-Find (disjoint-set) data structure that supports the following operations efficiently:

  1. find(x) -- return the representative (root) of the set containing element x, using path compression.
  2. union(x, y) -- merge the sets containing x and y, using union by rank (or union by size).
  3. component_size(x) -- return the number of elements in the set containing x.
  4. num_components() -- return the current number of disjoint sets.

All operations should run in near-constant amortized time.

Constraints:

  • $1 \leq n \leq 10^6$ (number of elements, labeled $0$ to $n-1$)
  • Up to $10^6$ total operations
  • Element labels are non-negative integers

Examples:

uf = UnionFind(5)        # elements: {0}, {1}, {2}, {3}, {4}
uf.num_components()       # => 5
uf.union(0, 1)
uf.union(2, 3)
uf.num_components()       # => 3
uf.component_size(0)      # => 2
uf.component_size(4)      # => 1
uf.union(1, 3)
uf.num_components()       # => 2
uf.component_size(0)      # => 4
uf.find(3) == uf.find(0)  # => True (same component)

Additionally, discuss:

  • How integer overflow in the size field can occur with adversarial inputs when using 32-bit integers, and how to guard against it.
  • How you would test your implementation with adversarial operation sequences.

Function signature

Implement run_ops(n, ops) where n is the number of elements (labeled 0..n-1) and ops is a list of operations. Each op is a list beginning with its name:

  • ["union", x, y]: merge the sets containing x and y (produces no output)
  • ["connected", x, y]: append True/False for whether x and y are in the same set
  • ["component_size", x]: append the size of the set containing x
  • ["num_components"]: append the current number of disjoint sets

Return the list of results, one entry per query op (in order); union contributes nothing.

Example

run_ops(3, [["connected", 0, 2], ["union", 0, 1], ["union", 1, 2], ["connected", 0, 2], ["num_components"], ["component_size", 1]]) -> [false, true, 1, 3]

Initially 0 and 2 are separate (false); after unioning 0-1 and 1-2 all three merge, so 0 and 2 are connected (true), there is 1 component, and its size is 3.

Show hint

What single representative could every member of a group agree on, and how would you reach it from any member?

Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.

Related free problems