Implement Rand10() Using Rand7()

Implement Rand10() Using Rand7()

What is this problem about?

The Implement Rand10() Using Rand7() coding problem is a probability and statistics challenge. You are given a library function rand7() that returns a uniform random integer in the range [1, 7]. You need to use this function to implement rand10(), which must return a uniform random integer in the range [1, 10].

Why is this asked in interviews?

Companies like Google and Yandex ask this to test a candidate's understanding of Rejection Sampling and probability distributions. It’s not just a coding problem; it's a math problem. It evaluations whether you can generate a larger uniform range from a smaller one without introducing bias (i.e., every number 1-10 must have an exact 10% chance of occurring).

Algorithmic pattern used

This problem uses Rejection Sampling on a 2D coordinate space.

1. Generate a larger range: Call rand7() twice to generate a range from 1 to 49. The formula is (rand7() - 1) * 7 + rand7(). This creates a uniform distribution of 49 values.
2. Filter for Uniformity: We need a multiple of 10. The largest multiple of 10 less than 49 is 40.
3. If the generated number is $\le 40$, return (num - 1) % 10 + 1.
4. If the number is $> 40$, "reject" it and try again. Because the 40 numbers are used uniformly to map to 1-10, the output is perfectly unbiased.

Example explanation

1. First call rand7() $o$ 2. Second call $o$ 5.
2. Calculate: $(2-1) imes 7 + 5 = 12$.
3. $12 \le 40$, so map it: $(12-1) \pmod{10} + 1 = 2$. Return 2.
4. If the calculation had resulted in 45, we would discard it and restart the loop.

Common mistakes candidates make

• Naive Summation: (rand7() + rand7()) % 10 is NOT uniform. Some sums (like 7 or 8) occur much more frequently than others (like 2 or 14).
• Introduce Bias: Mapping the 49 values to 10 by using num % 10. This makes 1-9 slightly more likely than 10 because they have 5 source values while 10 only has 4.
• Inefficiency: Not realizing that you can "recycle" the rejected values (41-49) to reduce the number of calls to rand7(), though basic rejection sampling is usually sufficient.

Interview preparation tip

Always emphasize Unbiasedness. In any "RandX to RandY" problem, the source range ($X^2, X^3, \dots$) must be larger than or equal to $Y$, and you must discard the "leftover" values that would prevent an even distribution.