Problem statement
Design the object model and public API for a disjoint-set forest (union-find) that maintains a partition of elements into disjoint groups under merge and same-group queries.
Operating context. One process, in-memory. A universe of elements each begins in its own singleton set; new elements may be added over time. Two optimizations are in play — union by rank (or size) and path compression — giving near-constant amortized cost. It backs incremental connectivity: tracking connected components as edges arrive, or the merge step of a minimum-spanning-tree build.
Out of scope. De-union or rollback (name the rollback-union-find seam only), serialization, distributed partitioning across machines, storing edge weights or the graph itself, and the surrounding graph algorithms that call into it.
What to produce. The class model (an element registry and parent / rank storage, whether arrays or node objects), the public API (makeSet, find, union, connected, componentCount, componentSize), the find algorithm with path compression, the union algorithm with union-by-rank / size, and the single-representative-per-set invariant — stated explicitly.
Requirements
This assessment is a Premium feature.
The statement above is free to read. The functional and non-functional requirements, and the graded canvas that scores your design against them, come with Premium.
Topics
- System Design LLD
- Ds Union-Find
- Algo Amortized
- Oop Encapsulation
- Patterns Strategy