Roll a Weighted Die
LinkedIn● EasyFULLTIMEONSITE INTERVIEWProblem statement
A die has m faces numbered 1 to m. Face i + 1 comes up with probability probabilities[i]. Implement rolling this die.
To make the rolls testable, the random numbers are given to you. draws holds uniform random numbers in [0, 1), one per roll. Use inverse-CDF sampling: split [0, 1) into consecutive intervals in face order, where face i + 1 owns the half-open interval [probabilities[0] + ... + probabilities[i - 1], probabilities[0] + ... + probabilities[i]).
For each draw u, return the face whose interval contains u. Return the faces for all draws, in order.
Handle these corner cases:
- A face with probability
0has an empty interval and must never be returned. - A draw exactly on a boundary belongs to the next face with positive probability, because each interval includes its left end but not its right end.
- If floating-point rounding leaves a draw at or above the computed total, return the last face with positive probability.
Function
rollWeightedDie(probabilities: double[], draws: double[]) → int[]Examples
Example 1
probabilities = [0.5,0.25,0.25]draws = [0.1,0.5,0.74,0.75,0.99]return = [1,2,2,3,3]The running totals are 0.5, 0.75, and 1.0, so face 1 owns [0, 0.5), face 2 owns [0.5, 0.75), and face 3 owns [0.75, 1).
The draws 0.5 and 0.75 sit on boundaries, so they go to faces 2 and 3.
Example 2
probabilities = [0.0,0.5,0.0,0.5]draws = [0.0,0.49,0.5,0.999]return = [2,2,4,4]Faces 1 and 3 have probability 0, so their intervals are empty. Face 2 owns [0, 0.5) and face 4 owns [0.5, 1).
The draw 0.0 goes to face 2, and 0.5 skips the empty face 3 and goes to face 4.
Example 3
probabilities = [1.0]draws = [0.0,0.9]return = [1,1]A one-face die always shows face 1.
Constraints
1 <= probabilities.length <= 10^50 <= probabilities[i] <= 1- The probabilities sum to
1within10^-9. 1 <= draws.length <= 10^50 <= draws[j] < 1