Group Accounts Linked Directly or Transitively by Shared Metadata Fields
Company: Stripe
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A platform stores many accounts, and each account carries the same fixed list of metadata fields, such as a name, an email address and a phone number. Find the accounts that belong to the same person. Two accounts are directly related when they have the same value in at least one field. Relations are transitive: if account A is related to B and B is related to C, then A, B and C belong to one person even when A and C share no field value.
The reported interview built up to this in steps: first comparing accounts pairwise and treating a matching field (such as the name) as the same person, then adding the transitive rule. This version asks for the final grouping and fixes the exact matching rule in Rules below.
### Function Signature
```python
def group_related_accounts(accounts: list[list[str]]) -> list[list[int]]:
```
### Rules
- `accounts[i]` is account `i`, and `accounts[i][f]` is its value for field `f`. Every account has the same number of fields `m`, in the same order.
- The empty string `""` means the field is missing. A missing value never matches anything, including another missing value.
- Accounts `i != j` are directly related when there is a field index `f` with `accounts[i][f] == accounts[j][f]` and that value is not `""`. Values are compared exactly: case-sensitive, with no trimming or normalization. A value in one field never matches the same text in a different field.
- Two accounts belong to the same group when they are connected by a chain of directly related accounts.
- Return only the groups that contain at least two accounts. List the indices inside each group in increasing order, and order the groups by their smallest index. If no two accounts are related, return `[]`.
### Constraints
- `1 <= n = len(accounts) <= 10^5`
- `1 <= m <= 5`, and every `accounts[i]` has exactly `m` values.
- Each value has length 0 to 30 and consists of lowercase English letters, digits and the characters `@`, `.`, `_` and `-`.
- The total length of all values is at most `2 * 10^6`.
### Examples
**Example 1**
```text
Input: accounts = [["alice", "a@x.com", ""],
["bob", "b@x.com", "555"],
["alicia", "a@x.com", "777"],
["carl", "", "777"],
["bob", "d@x.com", ""]]
Output: [[0, 2, 3], [1, 4]]
```
The fields are name, email and phone. Accounts 0 and 2 share the email `"a@x.com"`, and accounts 2 and 3 share the phone `"777"`, so 0, 2 and 3 form one group even though 0 and 3 share no value directly. Accounts 1 and 4 share the name `"bob"`. Accounts 0 and 4 both lack a phone, but missing values never match, so that does not relate them.
**Example 2**
```text
Input: accounts = [["p", "e1"], ["q", "e2"], ["r", "e1"], ["q", "e3"]]
Output: [[0, 2], [1, 3]]
```
Accounts 0 and 2 share the email `"e1"`, and accounts 1 and 3 share the name `"q"`. The group whose smallest index is 0 comes first.
**Example 3**
```text
Input: accounts = [["sam", "s1"], ["s1", "sam"]]
Output: []
```
The same text appears in both accounts, but in different fields, so the accounts are not related and no group has two or more accounts.
Overview: Group accounts that belong to the same person, where two accounts are directly related when they share a non-empty value in the same metadata field and relations chain transitively. Return the groups in a canonical order. Tests moving from pairwise field matching to an efficient grouping over indirect links.
Read the full Stripe Machine Learning Engineer interview experience this question came from
A platform stores many accounts, and each account carries the same fixed list of `m` metadata fields (for example a name, an email address and a phone number), always in the same order. Find the accounts that belong to the same person.
You are given `accounts`, where `accounts[i]` is account `i` and `accounts[i][f]` is its value for field `f`. Implement `group_related_accounts(accounts)`, which returns the groups as a list of lists of account indices.
**Rules**
- The empty string `""` means the field is missing. A missing value never matches anything, including another missing value.
- Accounts `i != j` are **directly related** when there is a field index `f` with `accounts[i][f] == accounts[j][f]` and that value is not `""`. Values are compared exactly: case-sensitive, with no trimming or normalization. A value in one field never matches the same text in a different field.
- Relations are transitive: two accounts belong to the same group when they are connected by a chain of directly related accounts, even if they share no field value with each other.
- Return only the groups that contain at least two accounts. List the indices inside each group in increasing order, and order the groups by their smallest index. If no two accounts are related, return `[]`.
Every returned index is smaller than `n <= 10^5`, so all returned values fit in a 32-bit integer.
**Constraints**
- `1 <= n = len(accounts) <= 10^5`
- `1 <= m <= 5`, and every `accounts[i]` has exactly `m` values.
- Each value has length 0 to 30 and consists of lowercase English letters, digits and the characters `@`, `.`, `_` and `-`.
- The total length of all values is at most `2 * 10^6`.
**Example 1**
```text
Input: accounts = [["alice", "a@x.com", ""],
["bob", "b@x.com", "555"],
["alicia", "a@x.com", "777"],
["carl", "", "777"],
["bob", "d@x.com", ""]]
Output: [[0, 2, 3], [1, 4]]
```
The fields are name, email and phone. Accounts 0 and 2 share the email `"a@x.com"`, and accounts 2 and 3 share the phone `"777"`, so 0, 2 and 3 form one group even though 0 and 3 share no value directly. Accounts 1 and 4 share the name `"bob"`. Accounts 0 and 4 both lack a phone, but missing values never match, so that does not relate them. The group whose smallest index is 0 comes before the group whose smallest index is 1.
**Example 2**
```text
Input: accounts = [["sam", "s1"], ["s1", "sam"]]
Output: []
```
The same text appears in both accounts, but in different fields, so the accounts are not related and no group has two or more accounts.
Constraints
- 1 <= n = len(accounts) <= 10^5
- 1 <= m <= 5, and every accounts[i] has exactly m values.
- Each value has length 0 to 30 and consists of lowercase English letters, digits and the characters '@', '.', '_' and '-'.
- The total length of all values is at most 2 * 10^6.
Examples
Input: ([['alice', 'a@x.com', ''], ['bob', 'b@x.com', '555'], ['alicia', 'a@x.com', '777'], ['carl', '', '777'], ['bob', 'd@x.com', '']],)
Expected Output: [[0, 2, 3], [1, 4]]
Explanation: Source Example 1: 0-2 share the email and 2-3 share the phone (transitive group 0, 2, 3); 1-4 share the name; the missing phones of 0 and 4 do not match.
Input: ([['p', 'e1'], ['q', 'e2'], ['r', 'e1'], ['q', 'e3']],)
Expected Output: [[0, 2], [1, 3]]
Explanation: Source Example 2: 0-2 share the email, 1-3 share the name; groups ordered by smallest index.
Hints
- Two accounts can only be directly related through a (field position, non-empty value) pair that both hold. How can you find every account holding such a pair without comparing all pairs of accounts?
- Relations chain: once two accounts are known to be together, anything related to either of them joins the same group, even when it appears much later in the list and connects groups you built separately.
- Build the groups first and format last: drop one-account groups, keep indices increasing inside a group, and order groups by their smallest index rather than by when they formed.