← Airbnb Interview InsightsMachine Learning Engineer

Airbnb·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
May 2026

Summary

Airbnb ML engineer interview with a graph/union-find coding problem that's basically a beefed-up version of a well-known accounts merge problem. Pretty standard algorithmic round but the twist of mixing emails and phone numbers as contact identifiers tripped me up more than I expected.

Questions Asked (1)

Q1

Given a list of accounts where each account has a name and a list of contact identifiers (emails and phone numbers), merge accounts that share any common email or phone number. Return the merged accounts with the union of all contacts, and write your own test cases along with a time/space complexity analysis.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I recognized the base problem pretty fast but the phone number part threw off my initial approach.

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 edges connect accounts sharing an email or phone. Use Union-Find (Disjoint Set Union) to efficiently merge connected components, then aggregate contacts per component. Alternatively, build a bipartite graph between accounts and identifiers and find connected components via BFS/DFS.

Pro tip: Emphasize that the choice between Union-Find and BFS/DFS depends on the data scale and whether you need to process streams; for Airbnb-scale data, Union-Find with path compression and union by rank is often preferred for its near-linear time and simplicity.

1. Clarify requirements and edge cases

Ask about input size, whether identifiers are unique per account, and if accounts can have duplicate identifiers. Clarify output format: merged accounts should have a name (if multiple names, pick one) and sorted unique contacts.

2. Choose data structure and algorithm

Decide between Union-Find and graph traversal. Union-Find is efficient for merging; graph traversal (BFS/DFS) is intuitive. Map each email/phone to an account index to build connections.

3. Implement merging logic

For Union-Find: initialize parent array, union accounts sharing an identifier, then group by root. For BFS/DFS: build adjacency list via identifiers, traverse to find components, and collect contacts.

4. Aggregate and format results

For each component, collect all unique emails and phones, sort them, and assign a name (e.g., first account's name). Ensure output is list of lists with name followed by sorted contacts.

5. Write test cases and analyze complexity

Create tests: no merges, all merge, transitive merges, duplicate identifiers, empty input. Analyze time: O(N α(N) + M log M) for Union-Find with sorting, where N is total identifiers and M is total contacts; space: O(N).

Key Points to Mention

  • Union-Find with path compression and union by rank for near-constant time operations.
  • Graph representation: bipartite graph between accounts and identifiers, or direct account-account edges via shared identifiers.
  • Handling transitive merges: if A shares email with B and B shares phone with C, all three merge.
  • Time complexity: O(N α(N) + M log M) where N is number of accounts/identifiers and M is total contacts; space O(N).
  • Test cases: include edge cases like no common identifiers, all accounts connected, duplicate identifiers within an account, and empty input.
  • Trade-offs: Union-Find vs BFS/DFS in terms of implementation complexity, memory, and suitability for streaming data.

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