Probability That Die A Beats Die B
Given two sorted arrays representing the face values of two fair dice A and B, calculate the probability that a single roll of die A shows a strictly greater value than a single roll of die B. Optimize beyond the naive O(n·m) brute-force approach using a two-pointer technique to achieve O(n + m) time complexity.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late July, 2026
You are given two fair dice, A and B. Each die has a set of face values (positive integers, duplicates allowed), and the face values of each die are provided already sorted in ascending order. Each face has an equal chance of being rolled. Both dice are rolled once. Calculate the probability that the value shown on die A is strictly greater than the value shown on die B. Follow-ups asked in the interview: Optimize from the O(n·m) brute-force comparison to O(n + m) using the fact that both arrays are sorted (two-pointer). Handle overflow concerns when the number of faces is very large (denominator n * m, and the favorable count). Solve it in a way that avoids overflow entirely when no integer type is large enough to hold n * m (accumulate probability incrementally / running mean instead of counting then dividing). Extend the function to return all three probabilities: P(A wins), P(B wins), and P(tie) — ideally by reusing the win-counting function with swapped arguments and deriving the tie as 1 − P(A) − P(B). What unit tests would you write? (Boundary cases: all-A-wins, all-B-wins, all-ties, duplicates, single-face dice, different-sized dice, large-scale overflow check.)
Hello Interview Premium
Your account is free and you can post anonymously if you choose.