Katkat
Back

Implement Union-Find and track components

MotiveSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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 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.