Group Words into Transitive Synonym Sets by Shared Two-Words-Before-and-After Context
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of sentences. Two words are considered synonyms if they appear in the same context: the same two words immediately before them and the same two words immediately after them. Synonymy is transitive: if A and B are synonyms and B and C are synonyms, then A and C are synonyms.
Find all synonym groups.
### Function Signature
```python
def synonym_groups(sentences: list[str]) -> list[list[str]]:
```
### Rules
- Words in a sentence are separated by single spaces. Number them `0, 1, 2, ...` within the sentence.
- The word at position `i` has a context only if it has at least two words before it and at least two words after it in the same sentence. Its context is the 4-tuple `(w[i-2], w[i-1], w[i+1], w[i+2])`.
- Two different words are direct synonyms if some occurrence of the first and some occurrence of the second have identical contexts. The occurrences may be in the same sentence or in different sentences.
- A word is identified by its exact string: every occurrence of the same string is the same word.
- Groups are the classes of the transitive closure of the direct-synonym relation. A word with no synonym belongs to no group and is not reported.
- Return the groups as lists of distinct words. Sort the words inside each group in ascending lexicographic order, and sort the groups by their first word. Return an empty list if there are no groups.
### Constraints
- `1 <= len(sentences) <= 10^4`
- Each sentence has between 1 and 100 words, and all sentences together have at most `2 * 10^5` words.
- Every word consists of 1 to 20 lowercase English letters.
- Sentences have no leading or trailing spaces.
### Examples
**Example 1**
```text
Input: sentences = [
"i really like the movie a lot",
"i really love the movie a lot",
"we really love the show very much",
"we really enjoy the show very much"
]
Output: [["enjoy", "like", "love"]]
```
`like` and `love` share the context `(i, really, the, movie)`. `love` and `enjoy` share the context `(we, really, the, show)`. By transitivity all three form one group.
**Example 2**
```text
Input: sentences = [
"p q red r s",
"p q blue r s",
"m n big o t",
"m n large o t",
"m n huge o u"
]
Output: [["big", "large"], ["blue", "red"]]
```
`huge` has the context `(m, n, o, u)`, which no other word shares, so it is not reported.
**Example 3**
```text
Input: sentences = ["the cat sat"]
Output: []
```
No word in a three-word sentence has two words on both sides.
Overview: Given a list of sentences, treat two words as synonyms when they share the same two words before and two words after, close the relation transitively, and return every synonym group in a canonical sorted order. Tests context hashing, union-find or connected components, and exact output formatting.
You are given a list of sentences. Two words are considered synonyms if they appear in the same context: the same two words immediately before them and the same two words immediately after them. Synonymy is transitive: if A and B are synonyms and B and C are synonyms, then A and C are synonyms.
Implement `synonym_groups(sentences)`, which finds all synonym groups.
### Rules
- Words in a sentence are separated by single spaces. Number them `0, 1, 2, ...` within the sentence.
- The word at position `i` has a context only if it has at least two words before it and at least two words after it in the same sentence. Its context is the 4-tuple `(w[i-2], w[i-1], w[i+1], w[i+2])`.
- Two different words are direct synonyms if some occurrence of the first and some occurrence of the second have identical contexts. The occurrences may be in the same sentence or in different sentences.
- A word is identified by its exact string: every occurrence of the same string is the same word.
- Groups are the classes of the transitive closure of the direct-synonym relation. A word with no synonym belongs to no group and is not reported.
- Return the groups as lists of distinct words. Sort the words inside each group in ascending lexicographic order, and sort the groups by their first word. Return an empty list if there are no groups.
### Examples
**Example 1**
```text
Input: sentences = [
"i really like the movie a lot",
"i really love the movie a lot",
"we really love the show very much",
"we really enjoy the show very much"
]
Output: [["enjoy", "like", "love"]]
```
`like` and `love` share the context `(i, really, the, movie)`. `love` and `enjoy` share the context `(we, really, the, show)`. By transitivity all three form one group.
**Example 2**
```text
Input: sentences = [
"p q red r s",
"p q blue r s",
"m n big o t",
"m n large o t",
"m n huge o u"
]
Output: [["big", "large"], ["blue", "red"]]
```
`huge` has the context `(m, n, o, u)`, which no other word shares, so it is not reported.
### Constraints
- `1 <= len(sentences) <= 10^4`
- Each sentence has between 1 and 100 words, and all sentences together have at most `2 * 10^5` words.
- Every word consists of 1 to 20 lowercase English letters.
- Sentences have no leading or trailing spaces.
The result contains only strings, so no value can exceed 2^31-1.
Constraints
- 1 <= len(sentences) <= 10^4
- Each sentence has between 1 and 100 words, and all sentences together have at most 2 * 10^5 words.
- Every word consists of 1 to 20 lowercase English letters.
- Sentences have no leading or trailing spaces.
- Words in a sentence are separated by single spaces.
Examples
Input: (['i really like the movie a lot', 'i really love the movie a lot', 'we really love the show very much', 'we really enjoy the show very much'],)
Expected Output: [['enjoy', 'like', 'love']]
Explanation: Example 1: like~love and love~enjoy merge transitively into one sorted group.
Input: (['p q red r s', 'p q blue r s', 'm n big o t', 'm n large o t', 'm n huge o u'],)
Expected Output: [['big', 'large'], ['blue', 'red']]
Explanation: Example 2: two disjoint pairs ordered by first word; huge has a unique context and is dropped.
Hints
- In a sentence of n words, only positions 2 through n-3 have two words on both sides, so only those positions have a context.
- Every word that ever appears with a given 4-word context is a direct synonym of every other word seen with that exact context, so the context itself can act as a lookup key.
- Because synonymy is transitive, two words can end up in the same group without ever sharing a context directly: view words as linked whenever they share a context and look for the connected pieces.