N-gram Language Model with Add-Alpha Smoothing
Updated
Problem statement
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 firstn - 1words areh. A context that only appears at the end of a sentence starts no n-gram, so its count is 0.- When
n = 1the context is empty, socount(h)is the total number of words insentences.
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 <= 40.01 <= alpha <= 1, andalphahas at most two digits after the decimal point.1 <= queries.length <= 100- Each
queries[j]has exactlynwords separated by single spaces, and every one of them appears insentences.
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