Accounts Merge: Turning a Messy Input into a Graph in a Coding Interview
Linkjob AIThe problem
Each account is a name followed by emails. Two accounts belong to the same person if they share any email. Merge them and return each person's emails sorted.
Spot the graph
Emails are nodes. Every account says "all of these emails are connected." Merging accounts means finding connected components. Once you say that out loud, the problem stops looking like string bookkeeping.
Approach 1: DFS over an adjacency list
Link the first email of each account to every other email in it, then DFS from each unvisited email to collect its component. O(N log N) for the final sort, where N is the total number of emails.
Approach 2: union-find keyed by email
Give each email a parent. Union every email in an account with the first one. Then group emails by root and sort each group. With path compression and union by rank this is near-linear before sorting.
def accounts_merge(accounts):
parent, owner = {}, {}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for name, *emails in accounts:
for e in emails:
parent.setdefault(e, e)
owner[e] = name
parent[find(e)] = find(emails[0])
groups = {}
for e in parent:
groups.setdefault(find(e), []).append(e)
return [[owner[r]] + sorted(g) for r, g in groups.items()]
Traps interviewers watch for
- Two different people can share a name; never merge by name.
- An account with a single email still needs to appear in the output.
- Union the emails, not the account indexes, or you will double-count.
How to explain it
Lead with "this is connected components", pick one approach, and mention the other as an alternative. That framing is usually worth more than the code.
If you want to rehearse explaining graph reductions like this under time pressure, Linkjob AI is built for coding interview practice. Disclosure: I work on Linkjob AI.