Katkat
Back

Predict most likely next word from training data

BloombergSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to process textual data into an N-gram model, requiring efficient counting of sequence frequencies to predict the most probable subsequent word.

Problem Statement

Given a list of strings representing a corpus of sentences, implement a class NextWordPredictor that identifies the most likely word to follow a given sequence of words (a prefix of length N).

Requirements

  1. train(corpus: List[str]): Tokenizes sentences and builds the frequency map for N-grams. Use a space character as the delimiter.
  2. predict(prefix: List[str]) -> str: Returns the word that appears most frequently immediately after the given prefix. If there is a tie, return the word that is lexicographically smaller. If the prefix has never been seen, return None.

Constraints

  • The corpus contains M sentences with a total of W words.
  • The prefix length N is fixed after the first train call.
  • Efficiency: train should be optimized for memory; predict should operate in O(N) time complexity.

Example

corpus = ["the cat sat on the mat", "the cat ate the fish"]
predictor = NextWordPredictor(n=2)
predictor.train(corpus)

# Given prefix ['the', 'cat']
# Following words: 'sat' (count 1), 'ate' (count 1)
# Tie: 'ate' < 'sat', return 'ate'
print(predictor.predict(['the', 'cat'])) # Output: 'ate'

Edge Cases

  • Prefix length does not match N.
  • Prefix does not exist in the training data.
  • Multiple words share the same maximum frequency.

Hints

Hint 1

Use a nested dictionary or a hash map where the key is a tuple representing the N-word sequence and the value is another map of follower words to their frequencies.

Hint 2

For the tie-breaking condition, consider sorting the candidate words before counting or maintaining the lexicographical order during the count update.

Hint 3

Ensure the `predict` function handles the case where the input prefix tuple does not exist in your hash map by returning `None`.

Follow-up questions

  • How would you modify this structure to return the top K most likely words instead of just one?
  • If the training corpus is massive (multiple terabytes), how would you distribute this counting task across multiple machines?
  • How does your implementation change if you need to support variable-length prefixes instead of a fixed `N`?