Katkat
Back

Merge Accounts by Shared Identifiers

OracleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests graph traversal techniques (BFS/DFS) and Disjoint Set Union (DSU) to group connected entities based on shared attributes.

Problem Statement

You are given a list of accounts where each account consists of a unique name and a list of email addresses. If two accounts share at least one email address, they must belong to the same person. Two accounts may belong to the same person even if they don't share any emails directly (transitive relationship).

Your task is to merge these accounts. After merging, each account should include all unique emails sorted in lexicographical order. The name of the account can remain the same (the problem implies that even if multiple accounts have the same name, they are merged if they share emails; if they do not share emails, they remain separate).

Function Signature

def merge_accounts(accounts: list[list[str]]) -> list[list[str]]:

Constraints

  • 1 <= accounts.length <= 1000
  • 2 <= accounts[i].length <= 10
  • 1 <= accounts[i][j].length <= 30

Examples

Example 1: Input: [['John', '[email protected]', '[email protected]'], ['John', '[email protected]', '[email protected]'], ['Mary', '[email protected]']] Output: [['John', '[email protected]', '[email protected]', '[email protected]'], ['Mary', '[email protected]']]

Example 2: Input: [['Gabe', '[email protected]', '[email protected]'], ['Gabe', '[email protected]'], ['Gabe', '[email protected]', '[email protected]']] Output: [['Gabe', '[email protected]', '[email protected]', '[email protected]', '[email protected]']]

Edge Cases

  • Accounts with no common emails should remain distinct even if they share the same name.
  • An account might contain duplicate emails internally.

Hints

Hint 1

Treat each email as a node in a graph and draw an edge between all emails present in the same account list.

Hint 2

Use a Disjoint Set Union (DSU) data structure or perform a depth-first search (DFS) to find all connected components of emails.

Hint 3

After grouping the emails, map each email group back to the account owner's name and sort the emails alphabetically.

Follow-up questions

  • How would you optimize the space complexity if you had billions of email records?
  • What changes are needed if an account can have a 'primary' email that must always be listed first in the merged result?
  • How would you handle a scenario where two accounts have the same emails but different names (data inconsistency)?