Google·Software Engineer·Technical Phone Screen
- Design a word prediction system: write a training function that takes a list of sentences and tracks which words follow each word, then write a predictor function that takes a word and returns the most likely next word.
- Follow-up: how would you optimize the predictor function to return the most likely next word in O(1) time instead of O(k)?
- Second follow-up: modify the predictor to return a word sampled according to probability rather than always returning the top word. For example, 'I' should return 'am' 2/3 of the time and 'like' 1/3 of the time.
“The core problem wasn't bad.”