FastPrepMost-Frequent Next-Word Predictor
Problems/Most-Frequent Next-Word Predictor

Most-Frequent Next-Word Predictor

Google logoGoogle● MediumFULLTIMENEW GRADPHONE SCREENONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The following-word frequency model and O(1) prediction requirement are source-backed. The source leaves token serialization, batched queries, ties, unseen words, and portable bounds unspecified; this practice version supplies those details.

Train a next-word predictor from one ordered array of case-sensitive tokens. Every adjacent pair contributes one observation from its first token to its second.

For each query token, return the observed following token with highest frequency. Break frequency ties by lexicographically smaller token. Return the empty string when the query has no observed successor. Precompute the winning successor while processing the training data so each query is answered in average O(1) time.

Function

predictNextWords(trainingTokens: String[], queries: String[]) → String[]

Examples

Example 1

trainingTokens = ["i","like","tea","i","like","coffee","i","like","tea"]queries = ["i","like"]return = ["like","tea"]

The word after i is always like, while tea follows like twice and coffee once.

Example 2

trainingTokens = ["x","z","x","a"]queries = ["x"]return = ["a"]

The successors a and z tie, so the lexicographically smaller a wins.

Constraints

  • 1 <= trainingTokens.length, queries.length <= 200000
  • Every token is a nonempty printable ASCII string of length at most 40.
  • The total number of token characters across both arrays is at most 1000000.

More Google problems

  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public String[] predictNextWords(String[] trainingTokens, String[] queries) {
        // Write your code here
    }
}
Checking account…