Find linked user records by weighted similarity

Problem Statement

You are given a list of user objects, where each object contains a unique id, a name, and an email. Two users are considered 'linked' if their similarity score meets or exceeds a given threshold T. The similarity score is calculated as follows:

• +0.6 points if the email fields are identical.
• +0.4 points if the name fields are identical.

Your task is to group all users into 'clusters' where a cluster is defined as a set of users connected directly or indirectly (e.g., if A is linked to B, and B is linked to C, then A, B, and C are in the same cluster).

Function Signature

def find_user_clusters(users, threshold) -> List[List[str]]

Constraints

• users: List of dicts with id (int), name (str), email (str).
• threshold: float (0.0 to 1.0).
• Number of users: up to 10,000.
• Return a list of lists, where each inner list contains the ids of users in that cluster.

Example

Input:

users = [
    {"id": 1, "name": "Alice", "email": "[email protected]"},
    {"id": 2, "name": "Alice", "email": "[email protected]"},
    {"id": 3, "name": "Bob", "email": "[email protected]"}
]
threshold = 0.4

Output: [[1, 2, 3]] Explanation:

• (1, 2) have same name: score 0.4. Since 0.4 >= 0.4, they are linked.
• (2, 3) have same email: score 0.6. Since 0.6 >= 0.4, they are linked.
• By transitivity, all three are in the same cluster.

Edge Cases

• Empty input list.
• Threshold > 1.0 (no users should be linked).
• Users with no shared attributes.