9. Cluster Near-Duplicate Support Queries (Union-Find)

Problem

An upstream embedding-similarity check has already flagged certain pairs of incoming support queries as similar enough to be near-duplicates of each other. Given those pairs, group all queries into clusters of mutually-connected duplicates so that only one representative per cluster needs a fresh answer, and the rest can reuse it.

Similarity is transitive across the given pairs: if q1~q2 and q2~q3 are both flagged, q1, q2, and q3 all belong to the same cluster even though q1~q3 was never directly flagged.

Source: src/9_cluster_similar_queries.py

def cluster_queries(query_ids: list[str], similar_pairs: list[tuple[str, str]]) -> list[list[str]]

>>> cluster_queries(["q1", "q2", "q3", "q4"], [("q1", "q2"), ("q3", "q4")])
[['q1', 'q2'], ['q3', 'q4']]

>>> cluster_queries(["q1", "q2", "q3", "q4"], [("q1", "q2"), ("q2", "q3")])
[['q1', 'q2', 'q3'], ['q4']]

Step-by-Step Approach

1. Recognize that "group items connected by pairwise edges, including transitively" is exactly the Union-Find (Disjoint Set Union) problem — every query starts in its own singleton set.
2. Initialize a parent map where every query id points to itself, and a rank map for union-by-rank, all starting at 0.
3. Write a find function that walks up parent pointers to the root of a query's set, applying path compression (point each visited node directly at its grandparent) to keep future lookups fast.
4. Write a union function that finds the roots of both queries and, if they differ, attaches the lower-rank root under the higher-rank root (bumping rank on a tie) — this keeps the resulting trees shallow.
5. Process every pair in similar_pairs with union, merging all transitively-connected queries into one set regardless of pair order.
6. After all unions, do a final pass over every query id, calling find to get its root, and bucket ids by root into a dict of lists.
7. Sort each cluster's members and sort the clusters themselves (e.g. by first member) to get a deterministic output order.

The key insight is that Union-Find turns "is item A transitively connected to item B through a chain of pairwise edges?" into two near-constant-time operations, avoiding an explicit graph traversal (BFS/DFS) for each connectivity query.

Reference solution

def cluster_queries(
    query_ids: list[str], similar_pairs: list[tuple[str, str]]
) -> list[list[str]]:
    # Union-Find with path compression + union by rank: ~O(n + m * alpha(n)) total.
    # every element starts as its own root
    parent = {qid: qid for qid in query_ids}
    rank = {qid: 0 for qid in query_ids}

    def find(x: str) -> str:
        while parent[x] != x:
            # path halving: point at grandparent
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a: str, b: str) -> None:
        root_a, root_b = find(a), find(b)
        if root_a == root_b:
            return
        if rank[root_a] < rank[root_b]:
            # swap so root_a is higher-or-equal rank
            root_a, root_b = root_b, root_a
        # attach shorter tree under taller one
        parent[root_b] = root_a
        if rank[root_a] == rank[root_b]:
            rank[root_a] += 1

    for a, b in similar_pairs:
        union(a, b)

    groups: dict[str, list[str]] = {}
    for qid in query_ids:
        # get-or-create bucket by root
        groups.setdefault(find(qid), []).append(qid)

    # deterministic member order
    clusters = [sorted(members) for members in groups.values()]
    # deterministic cluster order
    clusters.sort(key=lambda members: members[0])
    return clusters

Key Functions & Tricks

• Union-Find (Disjoint Set Union) — partition into disjoint sets via a parent forest
• Dict comprehensions {qid: qid for qid in ...} / {qid: 0 for qid in ...} — init parent/rank maps
• Path compression (path halving) — parent[x] = parent[parent[x]] flattens tree, near-O(1) amortized
• Union by rank — attach shorter tree under taller root, keeps trees shallow
• Tuple swap a, b = b, a — swaps variables in one line, no temp needed
• dict.setdefault(key, []) — get-or-create bucket list, one-line idiom
• List comprehension [sorted(m) for m in groups.values()] — deterministic member order
• list.sort(key=lambda m: m[0]) — deterministic cluster order by first member

How to Recognize This Pattern