Katkat
Back

Build a next-word frequency predictor

GoogleSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to process sequential text data, efficiently store word adjacency frequencies, and retrieve the most likely successor.

Problem Statement

Given a large list of sentences, design a system that predicts the most frequent next word given a current word. If multiple words have the same frequency, return the one that is lexicographically smaller.

Implement a class NextWordPredictor with the following methods:

  • void add_sentences(List sentences): Processes a list of sentences to build an internal frequency map. You can assume sentences consist of space-separated words.
  • String get_next_word(String word): Returns the most frequent word that immediately follows the input word. If no successor exists, or if the input word is unknown, return null.

Constraints

  • The total number of words across all sentences will be at most 10^5.
  • get_next_word may be called frequently; your solution should optimize for query performance.

Example

Input sentences: 
["cat sat on mat", "cat sat on rug", "dog sat on mat"]

Calls:
get_next_word("cat") -> "sat" (frequency 2, successor is always "sat")
get_next_word("sat") -> "on" (frequency 3)
get_next_word("on") -> "mat" (frequency 2, "mat" < "rug")

Edge Cases

  • What happens if the input word is the last word in a sentence?
  • How should ties in frequency be handled if the words have different lexicographical values?

Hints

Hint 1

Use a nested hash map (e.g., Map>) to store the frequency of each successor word for every given word.

Hint 2

During the preprocessing phase, iterate through each sentence to populate the maps, incrementing the count for every word-pair encountered.

Hint 3

When querying, retrieve the inner map for the given word and iterate through its entries to find the one with the highest frequency, applying lexicographical ordering for ties.

Follow-up questions

  • How would you optimize the `get_next_word` method if it is called significantly more often than `add_sentences`?
  • If the dataset was too large to fit in memory, how would you change your storage strategy?
  • How would you modify your system to suggest the top 3 most frequent next words instead of just one?