Probability That One Fair Die Beats Another
Company: Bytedance
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Probability That One Fair Die Beats Another
Two fair dice, `A` and `B`, are represented by integer arrays. Each array element is one physical face, so duplicate values are allowed and count as distinct, equally likely outcomes. The dice may have different numbers of faces.
Implement:
```python
def solution(a: list[int], b: list[int]) -> float:
```
Return the probability, as a floating-point value, that a single roll of `A` is strictly greater than a single roll of `B`. Ties do not count.
Examples:
- `a = [1, 2, 3]`, `b = [1, 2, 3]` returns `3 / 9`.
- `a = [2, 2]`, `b = [1, 2]` returns `2 / 4`.
Assumptions:
- Both arrays are non-empty.
- Face values are integers.
- Inputs may be large.
- Your solution should avoid enumerating all `len(a) * len(b)` outcome pairs.
Quick Answer: Solve a coding interview problem about the probability that one fair die beats another when the dice may have different sizes and duplicate face values. The challenge emphasizes strict tie handling and an efficient approach that avoids comparing every possible pair of faces.
Given two non-empty integer arrays representing equally likely die faces (duplicates count as distinct faces), return the probability that a roll from A is strictly greater than a roll from B.
Constraints
- Both dice contain at least one face
- Face values are integers
- Inputs may be large; avoid enumerating every ordered pair
- Duplicate values represent distinct equally likely faces
Examples
Input: ([1, 2, 3], [1, 2, 3])
Expected Output: 0.3333333333333333
Explanation: Three of nine ordered outcomes satisfy A > B.
Input: ([2, 2], [1, 2])
Expected Output: 0.5
Explanation: Each 2 from A beats only the 1 face on B.
Hints
- For a fixed face value from A, count how many values in B are strictly smaller.
- Sort one die, then use binary search for each face of the other die.