Accounts Merge
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Each account is [name, email, email, ...]. Two accounts belong to the same person if they share an email. Merge them; each result lists the name and the sorted emails.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What links two accounts together?
- Hint 2Remember for each email the first account that owns it.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A pile of visiting cards for the same people under different cards. Each card has a name and some emails. Walk through the cards and keep a note of which card first showed each email. If a later card shows an email already noted, those two cards belong to the same person: staple them together. At the end gather all emails of every stapled bundle, sort them and write the name on top.
- The obvious way
Compare every pair of accounts for common emails and merge repeatedly: O(n² x emails).
- The key insight
Give each account a head. Go through accounts and emails: if an email already belongs to an earlier account, merge the two accounts' groups; otherwise record the owner. Then collect every email under the head of its owner, sort each group, and put the account name in front.
- The algorithm
- head[account] = account.
- For each email: first time, note its owner; seen before, merge the two accounts.
- Group emails by the head of their owner.
- Sort each group, prefix with the name.
Watch it run
Example[[John, a, b], [John, b, c], [Mary, m]] (emails shortened)
Card 0 introduces emails a and b: their owner is card 0.
owner: a, b -> 0
Where people slip
- Two different people can have the same name: only shared emails join accounts, never names.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
from collections import defaultdict
def accounts_merge(accounts):
head = list(range(len(accounts)))
def find(card):
while head[card] != card:
head[card] = head[head[card]]
card = head[card]
return card
owner_of_email = {} # which card first showed each email
for card, account in enumerate(accounts):
for email in account[1:]:
if email in owner_of_email:
head[find(card)] = find(owner_of_email[email]) # shared email: staple the cards together
else:
owner_of_email[email] = card
emails_of = defaultdict(set)
for email, card in owner_of_email.items():
emails_of[find(card)].add(email)
return [[accounts[card][0]] + sorted(emails) for card, emails in emails_of.items()]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.