Two engineers implemented union-find but their solution is slow on large inputs because they only added one of the two standard optimizations. Walk me through path compression versus union by rank, why you need both, and what goes wrong with only one.

technical-conceptual · Senior level · software-engineering

What the interviewer is really asking

Assesses whether the candidate understands the two distinct optimizations that give union-find its near-constant amortized cost, how each independently bounds tree height, and the senior skill of diagnosing a performance regression from a half-applied technique.

What to say

• Describe each optimization's job: union by rank/size attaches the shorter (or smaller) tree under the taller one so a single union can't grow height unnecessarily; path compression flattens the find path by repointing every node visited directly to the root, so future finds on that branch are short.
• Explain why one alone is weak: union by rank alone bounds height to O(log n) — better than degenerate but not near-constant; path compression alone helps amortized cost but, without rank, a bad union order can still build tall trees that compression must repeatedly repair.
• State the combined result and the diagnosis: only with BOTH do you get the amortized O(alpha(n)) bound; if a teammate's union-find is slow, I'd check the find() actually repoints nodes (compression) and that union compares ranks/sizes rather than blindly attaching one root to the other.

What to avoid

• Treating the two optimizations as interchangeable or assuming either one alone gives the inverse-Ackermann bound.
• Implementing union by always attaching the first argument's root under the second's, ignoring rank/size, which can build O(n)-tall chains.
• Writing find() that returns the root without repointing the visited nodes, so it never actually compresses the path.

Example answers

Strong: Union by rank keeps the shorter tree under the taller one so a union never makes the tree taller than it must be — on its own that bounds height to O(log n). Path compression is in find(): once I reach the root, I repoint every node on the path straight to it, so the next find on that branch is O(1)-ish. Either alone is decent but not near-constant; you need both together to hit amortized O(alpha(n)). If a teammate's version is slow, the two things I'd check are whether find() actually mutates the parent pointers — a lot of people return the root but forget to repoint — and whether union compares rank or size instead of just hanging one root off the other, which is how you end up with linear chains.

Weak: I'd add path compression in find so the tree stays flat — that's the main optimization, so union by rank is kind of redundant once you have it.