Union-Find Interview Questions: Connectivity, Rollback Limits, and Path Compression

Union-Find interview questions test whether you can model changing connectivity without turning every query into a graph traversal. The structure supports find(x) for a representative and union(a,b) for merging components. Its fast standard form uses union by size or rank plus path compression. The important follow-up is deletion or undo: connectivity is no longer monotone, and the optimization that rewrites many parents becomes awkward to reverse.

Remove the Maximum Number of Connected Stones is a useful modeling drill because rows and columns become shared component nodes. The candidate-reported prompt supports that exercise only. It does not prove that a particular employer will require DSU.

Use Remove the Maximum Number of Connected Stones as the closest PracHub drill while this guide develops the broader interview decision. PracHub question records are candidate-reported practice material: each record supports its own prompt, not a claim that every employer asks the same question.

Union-Find Interview: Quick Answer

Maintain a forest. A root satisfies parent[root] == root; its size[root] equals the component size. find follows parents to a root. union finds both roots, returns false if they match, otherwise attaches the smaller tree's root under the larger and updates one size. With path compression, every find rewrites traversed nodes toward the root.

Princeton's documented weighted quick-union implementation with path compression has inverse-Ackermann amortized performance for intermixed operations. Do not call one individual operation strictly O(1). For rollback, omit ordinary path compression, record the child root, parent root, and prior size for each successful union, and undo those constant-number writes. Union by size alone keeps height logarithmic, making rollback operations predictable.

State the Forest Invariant Before Coding

Every element belongs to exactly one rooted tree. Parent pointers stay inside that tree and cannot form a directed cycle except the root's self-loop. Only root metadata is authoritative. If size[3] is stale after node 3 becomes a child, that is harmless as long as code never reads it as component size without first finding the root.

Initialize parent[i]=i, size[i]=1, and components=n. On a successful union, attach one root to the other and decrement components; on a redundant union, change nothing. This return value matters in cycle detection and Kruskal-style problems. Validate indexes according to the API contract instead of letting Python's negative indexes silently refer to different elements.

Implement Both Heuristics Deliberately

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

The assignment to parent[parent[x]] is path halving: it preserves the root while shortening the route. Recursive full compression is also valid but can overflow the call stack if a defective or unbalanced forest becomes tall. In an interview, choose one version and explain its write behavior. Union by size limits height; compression makes later finds even shorter.

Trace Connectivity Rather Than Array Shapes

Start with eight singletons. Apply (0,1), (2,3), (0,2), (4,5), and (6,7). The first four nodes form one component even if valid implementations choose different roots under equal-size ties. Test connected(1,3) as true and connected(1,7) as false. After (4,6) and (0,4), all eight are connected.

Avoid tests that require one exact parent array unless the tie policy is part of the contract. A correct forest may compress at different moments. Instead assert that every node reaches a self-root, roots partition the expected sets, root sizes sum to n, and successful unions reduce the component count. Then inspect height or parent changes only in a heuristic-specific test.

Explain the Complexity without Saying Constant

Union by size alone gives logarithmic tree height because a node's depth increases only when its component attaches under one at least as large; the containing size then at least doubles. It can double at most log2(n) times. Adding path compression yields an amortized bound involving the inverse Ackermann function, conventionally written O(alpha(n)) per operation across a sequence.

“Practically constant” describes how slowly alpha grows, not a proof that every call is constant. The first find on a path can still visit multiple parents. Amortized analysis charges that work across later shortened paths. State space as O(n). If an interviewer asks for worst-case per operation, clarify which heuristic and analysis they want.

Rollback Changes the Optimization

A rollback DSU records each successful merge on a stack. With union by size and no compression, a merge changes exactly parent[child_root] and size[parent_root]. A snapshot is the stack length; rollback pops until that length and restores both values. A redundant union should push a marker or leave the stack unchanged under a clearly documented convention.

Ordinary path compression may rewrite every parent on a find. Undo would then need to log every rewrite in exact order, increasing history and coupling reads to rollback state. The common interview answer disables compression and retains union by size, giving O(log n) finds and constant-size merge history. That is a deliberate trade: slightly slower queries for simple, reliable reversibility.

Turn Offline Deletions into Active Intervals

Plain DSU cannot split a component after deleting an edge. If all operations are known in advance, compute each edge's active time interval. Add that edge to nodes of a segment tree over time whose ranges lie inside the interval. Traverse the time tree with rollback DSU: take a snapshot, apply the node's edges, answer queries at leaves, then roll back before visiting the sibling.

This is different from the spatial segment tree used for range sums, but the interval decomposition idea is similar. It handles offline dynamic connectivity without fully dynamic tree structures. State limitations: operations must be collected before answering, parallel edges need independent lifetimes or reference counts, and the rollback stack must restore component count and every changed metadata field.

Know When DSU Is the Wrong Tool

Use DFS or BFS when you need an actual path, component contents immediately, or one static traversal. Use DSU when edges arrive and queries ask only whether vertices are connected, how many components exist, or whether an addition closes a cycle. DSU discards path evidence: two connected nodes do not reveal which edges connect them.

Directed reachability is not an equivalence relation, so ordinary DSU cannot answer it. Weighted or parity DSU can maintain relative constraints such as coordinate differences or opposite colors, but their find must accumulate metadata consistently. Deletion in an online stream generally needs a different dynamic-connectivity structure or a product restriction. Saying these limits is stronger than forcing DSU onto every graph prompt.

For grid islands, DSU is attractive when land cells activate over time; a static grid scan is often simpler. For minimum spanning trees, DSU detects whether a sorted edge joins different components, but the edge sort dominates time. Match the data structure to the query schedule and required evidence.

Make the Answer Reviewable

Turn the union-find design into a small deterministic review before adding more scale. Write the initial state, five to ten timestamped inputs, every expected state transition, and the exact read result at two watermarks. Replay one input, deliver another out of order, pause one consumer, and rebuild the serving view from its durable boundary. The replay should not create an extra effect, the stale input should follow the declared version rule, and the rebuilt read should match the authoritative result through the same watermark.

Keep expected results independent of the implementation. If the same code produces both the output and the assertion, a shared assumption can hide the defect. Add one invariant check that scans all state, even if production serves a faster index. For a distributed design, say which part this fixture does not prove: it does not measure production latency, network partitions, or capacity. Load and fault tests come next, using the traffic and error budgets already stated.

Finish with an operational table: signal, healthy range, action, and user-visible consequence. Include ingestion or queue age, rejected or duplicate work, authoritative-versus-serving divergence, and tail read latency. This makes the proposal inspectable. An interviewer can now change one requirement and see exactly which state, test, and alert must change with it.

Separate what the review establishes from what it leaves open. A passing deterministic fixture proves the declared state transitions for those inputs. It does not establish performance at scale, fairness across real users, or behavior during every network failure. Add a capacity test for the estimated peak, a skew test concentrated on one key or partition, and a fault test at the acknowledgment boundary. Record versions and random seeds so failures can be replayed. When a result differs from expectation, reduce it to the smallest trace, name the violated invariant, and repair that transition before retuning capacity. This evidence-first sequence keeps correctness questions from being hidden inside infrastructure changes.

Keep the review artifact beside the implementation and date the environment that produced it. If a later optimization changes ordering, batching, numeric width, or retry behavior, rerun the same trace before accepting the new result. The invariant is the stable comparison point; the component diagram is not.

Practice Five Related PracHub Questions

The first column links directly to five complete PracHub question records. Treat them as drills for transferable reasoning. They are candidate-reported practice evidence, not a forecast of a specific company interview.

A 45-Minute Interview Structure

Use five minutes to classify operations: additions, queries, deletions, paths, or offline history. Spend eight on the forest invariant and APIs. Code standard DSU in twelve, then trace redundant unions and equal-size ties. Use eight minutes to prove the height and amortized claims. Spend eight on rollback and the active-interval conversion. Close with four minutes of tests and limits. If deletion appears late, do not pretend compression can split a tree; change the plan explicitly.

Final Takeaway

The strongest Union-Find answer begins with monotone connectivity. Union by size controls height, path compression improves a sequence of finds, and the amortized claim is near-constant rather than literal constant time. Rollback changes the write budget, so omit compression and log reversible root changes. For deletions, either process lifetimes offline with rollback or choose a data structure that truly supports splits.

Sources and Further Reading

• Princeton Algorithms: Union-Find
• Princeton WeightedQuickUnionUF
• CP-Algorithms: Disjoint Set Union
• CP-Algorithms: Deleting from a data structure in O(T(n) log n)

Research note: Technical documentation and linked PracHub practice records were checked on September 13, 2026. Documentation supports the stated system or algorithm behavior; individual question records support only their own practice contracts. Architecture recommendations and interview sequencing are editorial inference.