PPractick

The problem

A CRM system has duplicate customer records. Each account is a name followed by some emails. Two accounts belong to the same person if they share at least one email, even when listed separately, and sharing is transitive. Two different people can have the same name, so names never merge accounts by themselves. Output each person once: their name, followed by all their emails sorted. Union-find over accounts does it. Map each email to the first account that listed it, and union any later account that repeats it.

Example: two "John" accounts share johnsmith@mail.com → merged; a third "John" with a different email stays separate.

Function signature

vector<vector<string>> accountsMerge(const vector<vector<string>>& accounts);  // [name, emails...]

Test cases

Input	Output (sorted)	Explanation
[[John,johnsmith@mail.com,john_newyork@mail.com],[John,johnsmith@mail.com,john00@mail.com],[Mary,mary@mail.com],[John,johnnybravo@mail.com]]	[[John,john00@mail.com,john_newyork@mail.com,johnsmith@mail.com],[John,johnnybravo@mail.com],[Mary,mary@mail.com]]	Same name, different people
[[A,a@x,b@x],[B,c@x],[A,b@x,d@x]]	[[A,a@x,b@x,d@x],[B,c@x]]	Linked through b@x
[[A,a@x,b@x],[A,c@x],[A,c@x,b@x]]	[[A,a@x,b@x,c@x]]	The third account bridges the first two
[[A,a@x],[A,b@x]]	[[A,a@x],[A,b@x]]	The same name alone doesn't merge
[[A,a@x]]	[[A,a@x]]

(Confirm: accounts with a shared email always have the same name; the output order is free, and it's sorted here for display.)

How interviewers phrase it

• "Given a list of accounts where each element is a name followed by emails, merge accounts belonging to the same person; two accounts belong to the same person if there is some common email" (LeetCode 721).

Clarifying questions to ask

1. Can the same name belong to different people? (Yes.)
2. Is merging transitive? (Yes: A shares with B, and B with C, puts A, B and C together.)
3. What output order is required? (Emails sorted; accounts in any order.)

Follow-ups to expect

1. "Why union accounts, not emails?"
2. "How is transitivity handled?"
3. "Graph alternative?"
4. "Why not merge by name?"
5. "Complexity?"

Related questions

• Disjoint Set Hard
• Number of islands II Hard
• Most stones removed with same row or column Medium
• Number of operations to make network connected Hard
• Making a large island Hard
• Number of provinces Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in