Compare Sentences Using Transitive Synonym Groups
Company: Read.Ai
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Given synonym pairs and two tokenized sentences, return whether the sentences
are equivalent. They are equivalent only if they have the same number of words
and every pair of words at the same position is either identical or connected
through one or more synonym pairs. Synonymy is undirected and transitive.
### Constraints & Assumptions
- There are at most 100,000 synonym pairs.
- Each sentence contains at most 100,000 lowercase words.
- A word may appear in several pairs and form a larger synonym group.
- Words absent from all pairs are equivalent only to themselves.
### Clarifications
- Sentence word order cannot change.
- Synonym pairs are symmetric even if listed once.
- Transitive chains such as `hit -> hits -> hitted` belong to one group.
### Examples
```text
pairs = [["flat", "flatting"], ["hit", "hits"], ["hits", "hitted"]]
a = ["flat", "the", "word"]
b = ["flatting", "the", "word"]
output = true
a = ["hit", "the", "click"]
b = ["hitted", "one", "click"]
output = false
```
### Hints
```hint Build components
Treat words as vertices and synonym pairs as undirected connections.
```
```hint Compare aligned tokens
After grouping synonyms, sentence equivalence is a position-by-position check.
```
Overview: Compare two tokenized sentences using undirected, transitive synonym relationships. Sentence lengths and word positions must match, while a union-find or graph traversal groups chained synonyms and leaves unknown words equivalent only to themselves.
Given undirected synonym pairs and two tokenized lowercase sentences, return whether the sentences are equivalent. They are equivalent only when they contain the same number of words and each pair of aligned words is either identical or connected through one or more synonym pairs. Synonymy is symmetric and transitive, sentence word order cannot change, and words absent from all pairs are equivalent only to themselves.
Constraints
- There are at most 100000 synonym pairs.
- Each sentence contains at most 100000 lowercase words.
- A word may appear in several pairs and form a larger synonym component.
- Synonym pairs are undirected and transitive.
- Words absent from all pairs are equivalent only to themselves, and sentence order cannot change.
Examples
Input: ([['flat', 'flatting'], ['hit', 'hits'], ['hits', 'hitted']], ['flat', 'the', 'word'], ['flatting', 'the', 'word'])
Expected Output: True
Explanation: This is the first source example; flat and flatting are directly synonymous and the other words are identical.
Input: ([['flat', 'flatting'], ['hit', 'hits'], ['hits', 'hitted']], ['hit', 'the', 'click'], ['hitted', 'one', 'click'])
Expected Output: False
Explanation: This is the second source example; the middle aligned words are neither identical nor synonymous.
Hints
- Build connected components from synonym pairs.
- After grouping words, compare the two token lists position by position.