Predict the Most Frequent Next Word in Constant Time
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Predict the Most Frequent Next Word in Constant Time
You are given training sequences of words and a list of query words. For every adjacent pair in each training sequence, count how often the second word immediately follows the first. For each query, return its most frequent immediate successor.
Implement `predictNextWords(trainingSequences, queries)`. Predictions must be precomputed while processing training data so each query is answered in average `O(1)` time.
## Tie and Boundary Semantics
- Adjacent pairs do not cross from the end of one training sequence to the start of another.
- If several successors share the greatest count, return the one whose first occurrence after that query word appeared earliest in the overall training input order.
- Return `null` when a query word has no observed successor.
- Preserve query order in the returned array.
## Constraints
- `1 <= trainingSequences.length <= 100,000`
- The total number of training words is at most `200,000`.
- `1 <= queries.length <= 100,000`
- Each word contains 1 to 50 lowercase English letters.
## Example 1
```text
Input: trainingSequences = [["i", "like", "tea"], ["i", "like", "coffee"], ["you", "like", "tea"]], queries = ["i", "like", "tea"]
Output: ["like", "tea", null]
```
`like` follows `i` twice, and `tea` follows `like` twice.
## Example 2
```text
Input: trainingSequences = [["go", "right"], ["go", "left"], ["stay", "left"]], queries = ["go", "stay", "missing"]
Output: ["right", "left", null]
```
`right` and `left` tie after `go`, so the successor observed first wins.
Quick Answer: Build a next-word predictor from adjacent training pairs and answer each query with its most frequent successor in average constant time. The exercise defines sequence boundaries, missing predictions, deterministic frequency ties, repeated pairs, and large training input.
For every adjacent pair within each training word sequence, count how often the second word immediately follows the first. Precompute one prediction for every observed predecessor while processing the training data, then return the most frequent immediate successor for each query in average O(1) lookup time. Ties use the successor whose first occurrence after that predecessor appeared earliest in overall training input order. Pairs do not cross sequence boundaries, query order is preserved, and a query without an observed successor returns null.
Constraints
- 1 <= trainingSequences.length <= 100,000
- The total number of training words is at most 200,000.
- 1 <= queries.length <= 100,000
- Each word has 1 to 50 lowercase English letters.
- Adjacent pairs never cross training-sequence boundaries.
- Ties use earliest first occurrence in overall training input order; missing successors return null.
Examples
Input: ([['i', 'like', 'tea'], ['i', 'like', 'coffee'], ['you', 'like', 'tea']], ['i', 'like', 'tea'])
Expected Output: ['like', 'tea', None]
Explanation: The first source example returns the frequency winners and null for a word with no successor.
Input: ([['go', 'right'], ['go', 'left'], ['stay', 'left']], ['go', 'stay', 'missing'])
Expected Output: ['right', 'left', None]
Explanation: The second source example resolves the go tie by the successor observed first.
Hints
- Store counts by predecessor and successor, along with when each pair was first seen.
- Update each predecessor's best successor as its pair counts change so queries need only one map lookup.