Airbnb·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026

Summary

Airbnb ML engineer round with a graph/union-find coding problem. A variant of the classic accounts merge, extended to handle both emails and phone numbers as shared identifiers. Pretty standard for the space but the added contact type wrinkle tripped me up a bit.

Questions Asked (1)

Given a list of accounts where each account has a name and a list of contacts (both emails and phone numbers), merge all accounts that share any common email or phone number. Return the merged accounts with the union of all contacts.

Algorithms & Data StructuresSystem Design

Author's notes

My first instinct was to just do it for emails like the standard version, and I literally forgot to handle phone numbers as a separate identifier type for a solid two minutes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph where each account is a node and shared contacts create edges, then find connected components using Union-Find (Disjoint Set Union) for near-linear time. For each component, merge the names and union all contacts, ensuring no duplicates. This approach efficiently handles large datasets and is easy to explain and implement.

Pro tip: Mention that Union-Find with path compression and union by rank gives almost O(N) time, and that you can map each contact to an account index to build the graph without pairwise comparisons. Also note that if names differ within a component, you can either keep the first name or flag it for review, showing awareness of real-world data quality issues.

1. Clarify and Define

Confirm that accounts sharing any email or phone should be merged, and that the merged account should contain the union of all contacts. Ask about handling conflicting names and whether the output order matters.

2. Build Contact-to-Account Mapping

Iterate through each account and its contacts, storing for each unique email and phone the index of the account it belongs to. This mapping will be used to union accounts that share a contact.

3. Union Accounts via Shared Contacts

For each contact, if it appears in multiple accounts, union those account indices using Union-Find. After processing all contacts, accounts in the same connected component are merged.

4. Merge Components and Collect Contacts

Group accounts by their root in the Union-Find structure. For each group, pick a representative name (e.g., the first account's name) and collect all unique emails and phone numbers from all accounts in the group.

5. Return Merged Accounts

Format the result as a list of merged accounts, each containing the name and the sorted list of unique contacts. Optionally, discuss time and space complexity.

Key Points to Mention

Union-Find (Disjoint Set Union) with path compression and union by rank for efficient merging.
Using a hash map to map each email and phone number to an account index, avoiding pairwise comparisons.
Time complexity: O(N * α(N)) where N is total number of contacts, effectively linear.
Space complexity: O(N) for the Union-Find structure and contact mappings.
Handling duplicate contacts within the same account and across accounts.
Potential edge cases: accounts with no contacts, conflicting names, and large input sizes.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.