How should I practice Weighted Next-Word Prediction From Training Sequences?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen problems in FastPrep.

Is Weighted Next-Word Prediction From Training Sequences associated with Google?

FastPrep tags this as a Google phone screen coding practice problem when the problem catalog has that company and stage context.

Weighted Next-Word Prediction From Training Sequences

Google● MediumNEW GRADPHONE SCREEN

Learn

Problem statement

sentences contains training word sequences. Every adjacent pair contributes one observed transition from the first word to the second.

Given currentWord, count how often each word immediately follows it. Sort candidate next words lexicographically and lay out one ticket for every observed occurrence. ticket is a zero-based index into those weighted tickets.

Return the candidate owning that ticket. Return the empty string when currentWord has no observed successor. In that case ticket is 0.

Function

predictNextWord(sentences: String[][], currentWord: String, ticket: int) → String

Examples

Example 1

sentences = [["a","b","c"],["a","s","d"]]currentWord = "a"ticket = 0return = "b"

b and s each follow a once; lexicographic weighted tickets are [b,s].

Example 2

sentences = [["a","b"],["a","b"],["a","c"]]currentWord = "a"ticket = 1return = "b"

The tickets are [b,b,c], so ticket 1 still selects b.

Example 3

sentences = [["a","b"],["c"]]currentWord = "b"ticket = 0return = ""

b never appears before another word.

Constraints

0 <= sentences.length <= 100000.
The total number of words is at most 500000.
Words contain lowercase English letters and have length from 1 through 50.
If successors exist, 0 <= ticket < total successor occurrences; otherwise ticket == 0.