Link similar user records by weighted field matches

Clarify first. The header row names the fields, and one of them is id. Each weight string is field:weight, and the weights add up to 1.0. Two users score the sum of the weights of the fields where their values are equal. Settle these points before you write code:

• What "equal" means. Use exact string equality for now. Normalization (case, spaces, Gmail dots) is a follow-up.
• Empty values. Two blank emails are missing data, not evidence of a match. An empty value never matches anything.
• Unweighted fields. A field that has no weight counts 0.
• Floating point. 0.1 + 0.2 is not 0.3. Compare with score >= threshold - 1e-9.
• Output order. For Part 1, sort by score (highest first), then by id. For Part 2, sort the ids in each group, and sort the groups by their first id.

Brute force. For Part 1, compare the target with every other row: O(n * f), where f is the number of fields. For Part 2, compare every pair: O(n^2 * f). This is correct, and it is a fine first answer for Part 1. For Part 2 it is too slow when n is 10^5.

Key idea: score only the pairs that share a value. The threshold is above 0, so a pair that shares no non-empty value scores 0 and can never qualify. Build an inverted index from (field, value) to the rows that hold that value. Then:

• Part 1. For each field of the target, go through the rows in its bucket and add the field's weight to that row's score. You only touch real candidates.
• Part 2. Every pair inside a bucket gets that bucket's field weight added to its score. Each pair with score >= threshold is an edge. Union-find merges the edges into connected components. "Linked" is transitive: A–B and B–C put A, B and C in one group, even when A and C are not similar.

Invariant. After the loop, pair_score[(a, b)] equals the sum of the weights of the fields where a and b hold the same non-empty value. That is exactly similarity(a, b), because each matching field puts the pair in exactly one shared bucket. Pairs that are not in the map score 0.

Where it costs. A value that many users share (a company such as "Acme") makes a bucket of size k with k^2 / 2 pairs. Bring this up yourself. It is what the interviewer will push on (see Follow-ups).

from __future__ import annotations

from collections import defaultdict

EPS = 1e-9


class UserLinker:
    """Weighted field-match similarity over user records, with linking."""

    def __init__(self, records: list[list[str]], weights: list[str]) -> None:
        if not records or "id" not in records[0]:
            raise ValueError("records need a header row with an 'id' column")
        header = records[0]
        col = {name: i for i, name in enumerate(header)}
        id_col = col["id"]

        self.weights: dict[str, float] = {}
        for item in weights:
            field, _, raw = item.rpartition(":")
            if field not in col or field == "id":
                raise ValueError(f"unknown weighted field: {field!r}")
            self.weights[field] = float(raw)
        if abs(sum(self.weights.values()) - 1.0) > 1e-6:
            raise ValueError("weights must sum to 1.0")

        self.ids: list[str] = []
        self.row_of: dict[str, int] = {}
        self.values: list[dict[str, str]] = []
        # (field, value) -> rows holding that value. Empty values never match.
        self.index: dict[tuple[str, str], list[int]] = defaultdict(list)
        for row in records[1:]:
            uid = row[id_col]
            if uid in self.row_of:
                raise ValueError(f"duplicate id: {uid!r}")
            r = len(self.ids)
            self.ids.append(uid)
            self.row_of[uid] = r
            vals = {f: row[col[f]] for f in self.weights}
            self.values.append(vals)
            for f, v in vals.items():
                if v != "":
                    self.index[(f, v)].append(r)

    def similarity(self, a: str, b: str) -> float:
        va, vb = self.values[self.row_of[a]], self.values[self.row_of[b]]
        return sum(w for f, w in self.weights.items() if va[f] != "" and va[f] == vb[f])

    def similar_users(self, user_id: str, threshold: float) -> list[str]:
        """Part 1: other users with similarity >= threshold, best first."""
        self._check_threshold(threshold)
        me = self.row_of[user_id]
        score: dict[int, float] = defaultdict(float)
        for f, v in self.values[me].items():
            if v == "" or self.weights[f] == 0:
                continue
            for other in self.index[(f, v)]:
                if other != me:
                    score[other] += self.weights[f]
        hits = [(s, self.ids[r]) for r, s in score.items() if s >= threshold - EPS]
        hits.sort(key=lambda t: (-t[0], t[1]))
        return [uid for _, uid in hits]

    def linked_groups(self, threshold: float) -> list[list[str]]:
        """Part 2: groups of users connected by chains of similar pairs."""
        self._check_threshold(threshold)
        pair_score: dict[tuple[int, int], float] = defaultdict(float)
        for (f, _), rows in self.index.items():
            w = self.weights[f]
            if w == 0 or len(rows) < 2:
                continue
            for i in range(len(rows)):
                for j in range(i + 1, len(rows)):
                    pair_score[(rows[i], rows[j])] += w

        parent = list(range(len(self.ids)))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        for (a, b), s in pair_score.items():
            if s >= threshold - EPS:
                ra, rb = find(a), find(b)
                if ra != rb:
                    parent[ra] = rb

        groups: dict[int, list[str]] = defaultdict(list)
        for r, uid in enumerate(self.ids):
            groups[find(r)].append(uid)
        out = [sorted(g) for g in groups.values() if len(g) > 1]
        out.sort(key=lambda g: g[0])
        return out

    @staticmethod
    def _check_threshold(threshold: float) -> None:
        if not 0 < threshold <= 1:
            raise ValueError("threshold must be in (0, 1]")

Let n be the number of users, f the number of weighted fields, and b_1 … b_m the sizes of the index buckets (sum b_i <= n * f).

• Build: O(n * f) time and space for the values and the index.
• similarity(a, b): O(f).
• similar_users: O(f + sum of the target's bucket sizes) time, plus O(c log c) to sort the c candidates. Worst case O(n * f). Extra space is O(c).
• linked_groups: O(sum b_i^2) to score the pairs. That is O(n^2 * f) in the worst case, when everyone shares one value, and close to O(n * f) when values are mostly distinct. Union-find adds O(P * α(n)) for P scored pairs. Space is O(P + n).

Weights ["name:0.3", "email:0.5", "company:0.2"], rows:

• similarity("u1", "u2") → 0.5 (name + company).
• similar_users("u1", 0.5) → ["u6", "u2", "u5"]. u6 scores 0.8, so it comes first. u2 and u5 tie at 0.5 and are sorted by id.
• similar_users("u1", 0.7) → ["u6"].
• similar_users("u2", 0.5) → ["u1", "u3", "u5"]. All score 0.5, so the order is by id.
• similar_users("u2", 0.6) → [].
• similar_users("u4", 0.1) → []. u4 shares nothing with anyone.
• linked_groups(0.5) → [["u1", "u2", "u3", "u5", "u6"]]. u3 joins only through u2 (a shared email), so this shows that linking is transitive.
• linked_groups(0.7) → [["u1", "u6"]].
• linked_groups(1.0) → [].
• Two users who both have an empty email and weights ["email:1.0"] → not similar, and no groups.
• Floating point: weights x:0.1, y:0.2, z:0.7, and two users who match on x and y. With threshold 0.3, they match, even though 0.1 + 0.2 = 0.30000000000000004.
• Weights that do not sum to 1, a weight on id or on an unknown field, or a threshold <= 0 → ValueError.

1. Normalize before matching. Lowercase and trim the names. For emails, lowercase them, drop +tag, and (for Gmail) drop the dots. For phones, keep only the digits. Normalize once, when you build the index, so that each field has its own normalizer. The rest of the code stays the same.
2. Fuzzy similarity per field. Let a field add weight * sim(a, b), using edit distance or Jaro–Winkler for names. Exact buckets no longer find every candidate. Use blocking keys instead: the first letters plus a phonetic code, or n-gram / MinHash LSH buckets. Score only the pairs that land in a shared block. Say plainly that blocking trades recall for speed.
3. Hot values. If 50k users share one company, that bucket alone makes about 10^9 pairs. Prune by weight. Choose a set S of fields such that the weights outside S add up to less than the threshold. Then every qualifying pair must match on some field in S. So generate candidate pairs only from the buckets of fields in S, and score each candidate in full in O(f). Leave the low-weight, high-collision fields (such as company) out of S. You can also cap the bucket size and log what you skip, but that loses recall.
4. Streaming inserts. New users arrive one at a time. Insert into the index, score the new user against its buckets as in Part 1, and union it with every user that crosses the threshold. Union-find supports this incrementally. Deletes or edits break union-find. Rebuild the component, or keep the edge list per component.
5. Explain the link. Return, for each group, the edges and the fields that matched on each edge. The path from user A to user C is a BFS over the stored edges. Reviewers on a data-quality team need this before they merge accounts.

Mid-level (L4)

• Parses the header and the weights correctly, and computes pairwise similarity with brute force.
• Handles empty values, ties and the float comparison once asked.
• Writes Part 1 cleanly and tests it with a small hand-made example.

Senior (L5)

• Raises the edge cases unprompted: empty values, float tolerance, the ordering rules, input validation.
• Reaches the inverted index without help, explains why a pair with no shared value can be skipped, and uses union-find for transitive groups.
• States the sum b_i^2 cost and names the hot-value problem.

Staff (L6+)

• Treats this as entity resolution: blocking versus recall, normalization per field, fuzzy scores, and how to explain a link to a reviewer.
• Designs for scale: bounding hot buckets, pruning by remaining weight, sharding the index, and incremental linking as users stream in.
• Points out the risk of transitive chaining (one bad edge merges two real people) and suggests guards, such as a stricter threshold for merges or a cap on group size.