Three canonical patterns cover the vast majority of interview questions.
Process edges one by one. For edge (u, v), if find(u) == find(v) before you union them, adding this edge closes a cycle.
Tomorrow's Kruskal (Day 13) is literally: sort edges by weight, then add each edge iff it doesn't form a cycle (i.e. union returns true). Union-Find is the engine that makes the greedy cycle test O(α(n)) per edge.
"Merge accounts by shared email," "friends of friends," "islands as things connect over time." Map each entity to an index, union on every relationship, then read off groups by root. When new connections stream in and you must answer queries between them, DSU beats re-running BFS every time.
componentSize(x) answers "how big is this group" for free — a very common follow-up.Cycle detection using the optimized DSU from Day 9.
/** Returns true if adding edges introduces a cycle (undirected). */
public boolean hasCycle(int n, int[][] edges) {
UnionFind uf = new UnionFind(n); // Day 9 class
for (int[] e : edges) {
// union returns false when both ends already share a root
if (!uf.union(e[0], e[1])) return true;
}
return false;
}
/** Kruskal skeleton — the Day 13 payoff, shown for context. */
public int kruskal(int n, int[][] edges) {
Arrays.sort(edges, (a, b) -> a[2] - b[2]); // by weight
UnionFind uf = new UnionFind(n);
int total = 0, used = 0;
for (int[] e : edges) {
if (uf.union(e[0], e[1])) { // safe (no cycle) → take it
total += e[2];
if (++used == n - 1) break; // MST complete
}
}
return total;
}
Map<String,Integer> so every occurrence maps to the same node.Consolidating the three patterns above into a fast-recognition table of the disguises Big Tech uses:
| Disguise / phrasing | What's really asked | Twist to handle |
|---|---|---|
| "Detect the edge that creates a cycle" (undirected) | Cycle detection | union() returns false = cycle edge |
| "Merge accounts by shared email" | Grouping by shared attribute | Map strings→ids; union on shared key; group by root |
| "Earliest time everyone connected" | Watch components → 1 | Sort by time, union, stop when count == 1 |
| "Islands II — land added over time" | Streaming connectivity | Add cell, union with land neighbors, track count |
| "Min cost to connect all" (setup for MST) | Kruskal engine | Sort edges, union safe ones (Day 13) |
| "Regions cut by slashes / grid partitions" | Components on a subdivided grid | Split each cell into parts, union carefully |
| "Directed cycle / dependency" | NOT Union-Find | Use DFS 3-color / Kahn (Week 3) |