Link similar user records by weighted field matches

A data-quality team wants to find user profiles that probably belong to the same person.

You get records, a 2D list of strings. The first row is a header of field names, and one of them is "id". Each later row is one user, with one string per field. Ids are unique.

You also get weights, a list of strings in the form "<field>:<weight>". Each field is a header field other than "id". Each weight is a decimal in [0, 1], and the weights add up to 1.0. A field with no weight counts 0.

The similarity of two users is the sum of the weights of the fields where both users have the same non-empty value. Compare values with exact string equality. An empty value never matches, not even another empty value.

Implement:

class UserLinker:
    def __init__(self, records: list[list[str]], weights: list[str]) -> None: ...
    def similarity(self, id_a: str, id_b: str) -> float: ...
    def similar_users(self, user_id: str, threshold: float) -> list[str]: ...
    def linked_groups(self, threshold: float) -> list[list[str]]: ...

Part 1: similar users

similar_users(user_id, threshold) returns the ids of every other user whose similarity to user_id is at least threshold. Sort them by similarity, highest first, and break ties by id, ascending.

Part 2: linked groups

Two users are linked if their similarity is at least threshold. Linking is transitive: if A is linked to B and B is linked to C, then A, B and C are in one group, even if A and C are not similar. linked_groups(threshold) returns every group that has at least two users. Sort the ids inside each group, and sort the groups by their first id.

Rules

• 0 < threshold <= 1. Raise ValueError otherwise.
• Raise ValueError if a weight names "id" or an unknown field, or if the weights do not sum to 1.0.
• Allow for floating-point error when you compare a score with the threshold.

Example

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

• similarity("u1", "u6") → 0.8 (name + email).
• similar_users("u1", 0.5) → ["u6", "u2", "u5"] (0.8, then a tie at 0.5 sorted by id).
• linked_groups(0.7) → [["u1", "u6"]].
• linked_groups(0.5) → [["u1", "u2", "u3", "u5", "u6"]]. u3 is similar only to u2 (shared email), but the link through u2 puts it in the group.

Constraints

• Up to 10^5 users and up to 20 fields; each value has at most 100 characters.
• A brute-force pairwise comparison is fine for Part 1. For Part 2, aim to do better than comparing every pair when most values are distinct, and state the time and space complexity.

Reconstructed from the reported question; details may differ from what interviewers ask.