Minimum index distance between two given words in a word list
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Given a list of words and two different words that both occur in it, return the smallest distance between a position of the first word and a position of the second word. The distance between positions `i` and `j` is `|i - j|`.
### Function Signature
```python
def shortest_word_distance(words: list[str], word1: str, word2: str) -> int:
```
`words` is the list to search; `word1` and `word2` are the two words to measure between.
### Rules
- Positions are indices into `words`. Either word may occur several times; consider every pair made of one occurrence of `word1` and one occurrence of `word2`, and return the smallest distance among them.
- The answer does not depend on the order in which `word1` and `word2` are given.
### Constraints
- `2 <= len(words) <= 10^5`
- Each word consists of 1 to 20 lowercase English letters
- `word1 != word2`, and both occur in `words` at least once
### Examples
**Example 1**
```text
Input: words = ["apple", "kiwi", "pear", "plum", "apple", "fig"], word1 = "pear", word2 = "fig"
Output: 3
```
`pear` is at index 2 and `fig` at index 5, so the distance is 3.
**Example 2**
```text
Input: words = ["red", "green", "blue", "yellow", "green", "red"], word1 = "yellow", word2 = "red"
Output: 2
```
`yellow` is at index 3 and `red` is at indices 0 and 5. The closer occurrence is at index 5, at distance 2.
**Example 3**
```text
Input: words = ["a", "b"], word1 = "b", word2 = "a"
Output: 1
```
The words are adjacent; listing `word1` after `word2` in the input does not change the answer.
Overview: Coding problem: given a list of words and two different target words that both appear in it, return the smallest distance between an index of one word and an index of the other. It tests single-pass scanning with position tracking, handling of repeated occurrences, and time complexity analysis.
Read the full LinkedIn Software Engineer interview experience this question came from
You are given a list of words `words` and two different words `word1` and `word2`, both of which occur in `words` at least once. Return the smallest distance between a position of `word1` and a position of `word2`, where the distance between positions `i` and `j` is `|i - j|`.
Positions are indices into `words`. Either word may occur several times: consider every pair made of one occurrence of `word1` and one occurrence of `word2`, and return the smallest distance among all such pairs. The answer does not depend on the order in which `word1` and `word2` are given.
Implement `shortest_word_distance(words, word1, word2)`, which returns this smallest distance as an integer.
### Example 1
```text
Input: words = ["apple", "kiwi", "pear", "plum", "apple", "fig"], word1 = "pear", word2 = "fig"
Output: 3
```
`pear` is at index 2 and `fig` is at index 5, so the distance is 3.
### Example 2
```text
Input: words = ["red", "green", "blue", "yellow", "green", "red"], word1 = "yellow", word2 = "red"
Output: 2
```
`yellow` is at index 3 and `red` is at indices 0 and 5. The closer occurrence is at index 5, at distance 2.
### Constraints
- `2 <= len(words) <= 10^5`
- Each word in `words` consists of 1 to 20 lowercase English letters
- `word1 != word2`, and both occur in `words` at least once
- The answer is between 1 and `len(words) - 1`, so it never exceeds 2^31 - 1 and fits in a 32-bit `int` in every language
Constraints
- 2 <= len(words) <= 10^5
- Each word in words consists of 1 to 20 lowercase English letters
- word1 != word2, and both occur in words at least once
- The answer is between 1 and len(words) - 1, so it never exceeds 2^31 - 1 (a 32-bit int suffices in every language)
Examples
Input: (['apple', 'kiwi', 'pear', 'plum', 'apple', 'fig'], 'pear', 'fig')
Expected Output: 3
Explanation: Source Example 1: pear is at index 2 and fig at index 5; the apple occurrences are ignored.
Input: (['red', 'green', 'blue', 'yellow', 'green', 'red'], 'yellow', 'red')
Expected Output: 2
Explanation: Source Example 2: yellow is at index 3 and red at indices 0 and 5; the later red is closer, at distance 2.
Hints
- Every pair made of one occurrence of word1 and one occurrence of word2 is a candidate, and either word may occur many times.
- The answer must not change if word1 and word2 are swapped, so an occurrence of word2 before word1 matters just as much as one after it.
- With up to 10^5 words, consider whether you really need to compare every occurrence of one word with every occurrence of the other.