FastPrepN-gram Language Model with Add-Alpha Smoothing
Problems/N-gram Language Model with Add-Alpha Smoothing

N-gram Language Model with Add-Alpha Smoothing

Google logoGoogle● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A report on the ML round of a Google SWE ML loop, held after the phone screen, says the candidate coded an n-gram model in Python and answered ML questions about it. This page treats that round as part of the onsite. The interviewer felt the resulting probabilities were too small, since the candidate had added the vocabulary size to the denominator as a guard against zero. The candidate replied that they would use alpha (additive) smoothing.

The report gives no corpus, value of n, interface, or examples, and the other ML questions are not described. Here, you get training sentences, n, and alpha. Each query's probability is (count(h w) + alpha) / (count(h) + alpha * V), where V is the number of distinct training words. N-grams stay inside a sentence, the context count only includes n-grams that start with it, and every query word is in the training vocabulary. The limits are our choice.

Our version is about 60% the same as the reported question.

Build an n-gram language model from training text and use it to estimate word probabilities.

sentences holds the training sentences. Each one is a string of words separated by single spaces. An n-gram is a run of n consecutive words inside one sentence. N-grams never run from the end of one sentence into the next. The vocabulary is the set of distinct words in sentences, and V is its size.

Each query is a string of exactly n words. Its first n - 1 words are the context h, and its last word is w. Estimate the probability of w after h with add-alpha smoothing:

P(w | h) = (count(h w) + alpha) / (count(h) + alpha * V)

  • count(h w) is the number of training n-grams equal to the query.
  • count(h) is the number of training n-grams whose first n - 1 words are h. A context that only appears at the end of a sentence starts no n-gram, so its count is 0.
  • When n = 1 the context is empty, so count(h) is the total number of words in sentences.

Return the probability for each query, in query order. Answers within 10^-9 of the expected value are accepted.

Function

ngramProbabilities(sentences: String[], n: int, alpha: double, queries: String[]) → double[]

Examples

Example 1

sentences = ["the cat sat","the cat ran","a dog sat"]n = 2alpha = 0.5queries = ["the cat","cat sat","dog ran","sat the"]return = [0.5,0.3,0.125,0.16666666666666666]

The vocabulary is the, cat, sat, ran, a and dog, so V = 6 and alpha * V = 3. The bigrams are the cat (twice), cat sat, cat ran, a dog and dog sat.

  • the cat: (2 + 0.5) / (2 + 3) = 0.5, because two bigrams start with the.
  • cat sat: (1 + 0.5) / (2 + 3) = 0.3.
  • dog ran: never seen, so (0 + 0.5) / (1 + 3) = 0.125.
  • sat the: sat appears twice, but always at the end of a sentence, so no bigram starts with it. The answer is 0.5 / (0 + 3) = 1/6, about 0.1666666667.

Example 2

sentences = ["b a b"]n = 1alpha = 1.0queries = ["a","b"]return = [0.4,0.6]

With n = 1 the context is empty, so count(h) is the total number of words, 3. The vocabulary has V = 2 words. a appears once: (1 + 1) / (3 + 2) = 0.4. b appears twice: (2 + 1) / (3 + 2) = 0.6.

Example 3

sentences = ["i like green tea","i like tea"]n = 3alpha = 0.1queries = ["i like tea","like green tea","green tea i"]return = [0.4583333333333333,0.7857142857142857,0.25]

V = 4, so alpha * V = 0.4. The trigrams are i like green, like green tea and i like tea.

  • i like tea: two trigrams start with i like, and one of them is this one, so (1 + 0.1) / (2 + 0.4), about 0.4583333333.
  • like green tea: (1 + 0.1) / (1 + 0.4), about 0.7857142857.
  • green tea i: green tea ends the first sentence, and n-grams never run into the next sentence, so nothing starts with green tea. The answer is 0.1 / (0 + 0.4) = 0.25.

Constraints

  • 1 <= sentences.length <= 200
  • Each sentences[i] has 1 to 50 words separated by single spaces, with no leading or trailing spaces, and has at most 549 characters.
  • Every word has 1 to 10 lowercase English letters.
  • 1 <= n <= 4
  • 0.01 <= alpha <= 1, and alpha has at most two digits after the decimal point.
  • 1 <= queries.length <= 100
  • Each queries[j] has exactly n words separated by single spaces, and every one of them appears in sentences.

More Google Onsite Interview questions

  • Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
  • Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
  • Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
  • Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
  • Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
  • Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • Reconstruct Digits from Jumbled English WordsMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Text Embedding and Vector SearchNike, Inc. · PHONE SCREEN · ONSITE INTERVIEWNike, Inc. interview questions
  • Fraction to Recurring DecimalGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
  • Rank Bipedal Dinosaurs by SpeedMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
  • Reorderable Task Scheduler With CooldownWaymo · PHONE SCREENWaymo interview questions
  • Minimum Anagram PeriodVisa · OAVisa interview questions
  • Maximum Equal Parts for PrefixesAmazon · OA
  • Per-Segment SpeedingOnePay · PHONE SCREENOnePay interview questions
  • Find Accounts with Negative Converted BalancesStripe · PHONE SCREENStripe interview questions
  • Minimum Anagram PeriodWells Fargo · OAWells Fargo interview questions

Interview reports that mention this question

  • Google SWE III ML Loops in India: 10 Experiences (Part 2 of 3)

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public double[] ngramProbabilities(String[] sentences, int n, double alpha, String[] queries) {
        // Write your code here.
    }
}
Checking account…