Combine Token Posteriors With Naive Bayes
Updated
Problem statement
A sentiment model labels each text as positive (+) or negative (-). You know prior = P(+), the share of all texts that are positive. For each token t_i that appears in a new text, you also know posteriors[i] = P(+ | t_i): the share of texts containing that token that are positive.
Assume the naive Bayes model: within each class, the tokens appear independently of each other. Return P(+ | t_1, ..., t_k), the probability that a text containing all k tokens is positive.
Bayes' rule turns each given value into a likelihood: P(t_i | +) = P(+ | t_i) * P(t_i) / P(+) and P(t_i | -) = (1 - P(+ | t_i)) * P(t_i) / (1 - P(+)). The unknown P(t_i) cancels out of the final answer.
Answers within 10^-9 of the expected value are accepted.
Function
combinePosterior(prior: double, posteriors: double[]) → doubleExamples
Example 1
prior = 0.5posteriors = [0.6,0.2]return = 0.2727272727272727The prior odds are 0.5 / 0.5 = 1. The two tokens have odds 0.6 / 0.4 = 1.5 and 0.2 / 0.8 = 0.25. The combined odds are 1 * (1.5 / 1) * (0.25 / 1) = 0.375, so the posterior is 0.375 / 1.375 = 3/11, about 0.2727272727.
Example 2
prior = 0.3posteriors = [0.6,0.6]return = 0.84The prior odds are 0.3 / 0.7 = 3/7. Each token has odds 1.5, which is 1.5 / (3/7) = 3.5 times the prior odds. The combined odds are (3/7) * 3.5 * 3.5 = 5.25, so the posterior is 5.25 / 6.25 = 0.84.
Example 3
prior = 0.8posteriors = [0.35]return = 0.35With one token, the answer is that token's own value: 0.35.
Constraints
1 <= posteriors.length <= 200.001 <= prior <= 0.999and0.001 <= posteriors[i] <= 0.999, each with at most three digits after the decimal point.
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
- Integers With Multiple Sum of Two CubesCharta Health · PHONE SCREEN · ONSITE INTERVIEWCharta Health interview questions
- Retrieve Vectors by Cosine SimilarityHarvey · ONSITE INTERVIEWHarvey interview questions
- Integer BreakAmazon · ONSITE INTERVIEW
- Knight Probability in ChessboardGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Path Between Two Nodes of a Fibonacci TreeDatabricks · ONSITE INTERVIEWDatabricks interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
- Babysitter Quote with Hourly RatesUpstart · ONSITE INTERVIEWUpstart interview questions
- Calculate a Token-List ExpressionCollege Vine · ONSITE INTERVIEW
- Maximize the Even-Odd Index Product GapInfosys · ONSITE INTERVIEWInfosys interview questions
- Add Two Numbers IIBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions