Jobs

Interviews

Discussions

Implement Rand10() Using Rand7()

Medium

Asked by:

More companies

207 views

Topics:

Bit Manipulation

Given the API rand7() that generates a uniform random integer in the range [1, 7], write a function rand10() that generates a uniform random integer in the range [1, 10]. You can only call the API rand7(), and you shouldn't call any other API. Please do not use a language's built-in random API.

Each test case will have one internal argument n, the number of times that your implemented function rand10() will be called while testing. Note that this is not an argument passed to rand10().

Example 1:

Input: n = 1
Output: [2]

Example 2:

Input: n = 2
Output: [2,8]

Example 3:

Input: n = 3
Output: [3,8,10]

Constraints:

1 <= n <= 10⁵

Follow up:

What is the expected value for the number of calls to rand7() function?
Could you minimize the number of calls to rand7()?

Try coding it in LeetCode

Implement Rand10() Using Rand7()

Medium

Asked by:

207 views

Topics:

Bit Manipulation

Example 1:

Input: n = 1
Output: [2]

Example 2:

Input: n = 2
Output: [2,8]

Example 3:

Input: n = 3
Output: [3,8,10]

Constraints:

1 <= n <= 10⁵

Follow up:

What is the expected value for the number of calls to rand7() function?
Could you minimize the number of calls to rand7()?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is Rand7() truly uniformly random and unbiased?
What is the acceptable range of values for the output of Rand10(), specifically, are 0 and 10 inclusive?
Is it acceptable to call Rand7() multiple times in the implementation of Rand10()?
Are we aiming for a solution that minimizes the average number of calls to Rand7(), or just a correct solution?
Should I prioritize simplicity and readability over absolute minimal calls to Rand7(), given that Rand7() is an external function?

Brute Force Solution

Approach

We need to simulate rolling a ten-sided die using only a seven-sided die. The brute force method essentially keeps re-rolling the seven-sided die until we get a result that directly corresponds to a number between one and ten.

Here's how the algorithm would work step-by-step:

Roll the seven-sided die.
If the result is one, two, three, four, five, six, seven, return the result directly as if it were a roll of a ten-sided die.
If the result is not between one and seven then re-roll the seven-sided die.
Repeat the process until you get a value of one, two, three, four, five, six, or seven.
Transform the result to fit the range 1 to 10. For example, map one to one, two to two, three to three. Then use the same strategy for mapping additional values 8, 9, and 10

Code Implementation

def rand10_brute_force(rand7):
    while True:
        roll_result = rand7()

        # Discard values outside the range 1-7
        if roll_result <= 7:

            # Map the 7 possible outcomes to 1-7 directly
            return roll_result

Big(O) Analysis

Time Complexity

O(1) – The problem statement describes a rejection sampling approach. We repeatedly call rand7() until we get a value between 1 and 7 inclusive. The number of calls to rand7() is not dependent on an input size 'n'. Although we may need to re-roll the die several times, the expected number of re-rolls is constant. Because the expected number of calls to rand7() is constant, the algorithm runs in O(1) time (constant time).

Space Complexity

O(1) – The provided solution uses a rejection sampling approach within a loop. It rolls the seven-sided die and performs a transformation to simulate the ten-sided die. The only extra memory required is for storing the result of each roll and potentially a few temporary variables to perform the transformation, the amount of space used remains constant regardless of how many times the seven-sided die needs to be rolled. No additional data structures like arrays or hash maps are created that scale with any input size. Therefore, the space complexity is O(1).

Optimal Solution

Approach

We need to simulate a 10-sided die using only a 7-sided die. The key idea is to combine multiple rolls of the 7-sided die to create a larger range of possibilities that can then be mapped onto the numbers 1 to 10 efficiently, discarding results that don't fit.

Here's how the algorithm would work step-by-step:

Generate a number using the 7-sided die and store it.
Generate another number using the 7-sided die and store it.
Combine these two numbers to create a new number with more possibilities than either die alone.
If the combined number falls within the range we can use to fairly map to 1-10, then perform the mapping and return the result.
If the combined number is outside the usable range, repeat the entire process from the start, generating two new numbers using the 7-sided die.
By repeatedly combining rolls and rerolling when outside the target range, you eventually get a number that can be fairly mapped to the desired 1-10 range.

Code Implementation

def rand7():
    # Assume this function exists and returns a random integer in the range 1 to 7 (inclusive).
    pass

def rand10():
    while True:
        first_roll = rand7()
        second_roll = rand7()

        # Effectively create a uniform distribution from 1 to 49
        combined_result = (first_roll - 1) * 7 + second_roll

        # If the result is greater than 40, we reroll because it's biased.
        if combined_result <= 40:

            # Map the range 1-40 to 1-10, since 40 is divisible by 10.
            return (combined_result - 1) % 10 + 1

Big(O) Analysis

Time Complexity

O(1) – The algorithm involves repeatedly calling rand7() until a value within a specific range is obtained. While the number of calls to rand7() is not fixed, the probability of obtaining a usable value in each iteration is constant. Therefore, the expected number of iterations is constant, and the time complexity does not depend on any input size. Thus, the average runtime is O(1), a constant time operation.

Space Complexity

O(1) – The algorithm uses a fixed number of variables to store the results of the rand7() calls and potentially perform calculations. The number of variables used, such as the temporary storage for the two rolls of the 7-sided die, doesn't depend on any input size. Thus, the space used remains constant regardless of how many times the loop iterates, making the auxiliary space complexity O(1).

Edge Cases

Case	How to Handle
rand7() returns values clustered at one end of its range (e.g., mostly 1s)	The solution should still produce a uniform distribution for rand10() regardless of non-uniformity in rand7().
rand7() has a slight bias towards certain numbers	The rejection sampling method in rand10() is designed to minimize the impact of any slight biases in rand7().
Integer overflow when combining results from multiple rand7() calls.	Carefully choose combinations and modulo operations to avoid exceeding integer limits.
The theoretical maximum number of calls to rand7() before a valid rand10() value is generated is very high.	The algorithm should still terminate eventually, but consider logging or monitoring if the average number of calls is significantly higher than expected.
rand7() returns 0 (although this is outside its specified range, it's important to consider unexpected behavior).	Handle this case by treating 0 as an invalid return and re-calling rand7().
Stack overflow if using recursion excessively in case of extremely biased rand7() function.	Convert the recursive approach to an iterative one, if implemented using recursion.
The generated number has a high probability of being a certain value.	The solution should produce numbers between 1 and 10 with equal probability, even when called many times.
The number of calls to rand7() impacts performance.	Minimize the average number of calls to rand7() required to generate a single rand10() value by efficiently combining its outputs.

rand7() returns values clustered at one end of its range (e.g., mostly 1s)

How to Handle:

The solution should still produce a uniform distribution for rand10() regardless of non-uniformity in rand7().

rand7() has a slight bias towards certain numbers

How to Handle:

The rejection sampling method in rand10() is designed to minimize the impact of any slight biases in rand7().

Integer overflow when combining results from multiple rand7() calls.

How to Handle:

Carefully choose combinations and modulo operations to avoid exceeding integer limits.

The theoretical maximum number of calls to rand7() before a valid rand10() value is generated is very high.

How to Handle:

The algorithm should still terminate eventually, but consider logging or monitoring if the average number of calls is significantly higher than expected.

rand7() returns 0 (although this is outside its specified range, it's important to consider unexpected behavior).

How to Handle:

Handle this case by treating 0 as an invalid return and re-calling rand7().

Stack overflow if using recursion excessively in case of extremely biased rand7() function.

How to Handle:

Convert the recursive approach to an iterative one, if implemented using recursion.

The generated number has a high probability of being a certain value.

How to Handle:

The solution should produce numbers between 1 and 10 with equal probability, even when called many times.

The number of calls to rand7() impacts performance.

How to Handle:

Minimize the average number of calls to rand7() required to generate a single rand10() value by efficiently combining its outputs.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is Rand7() truly uniformly random and unbiased?
What is the acceptable range of values for the output of Rand10(), specifically, are 0 and 10 inclusive?
Is it acceptable to call Rand7() multiple times in the implementation of Rand10()?
Are we aiming for a solution that minimizes the average number of calls to Rand7(), or just a correct solution?
Should I prioritize simplicity and readability over absolute minimal calls to Rand7(), given that Rand7() is an external function?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Roll the seven-sided die.
If the result is one, two, three, four, five, six, seven, return the result directly as if it were a roll of a ten-sided die.
If the result is not between one and seven then re-roll the seven-sided die.
Repeat the process until you get a value of one, two, three, four, five, six, or seven.
Transform the result to fit the range 1 to 10. For example, map one to one, two to two, three to three. Then use the same strategy for mapping additional values 8, 9, and 10

Code Implementation

def rand10_brute_force(rand7):
    while True:
        roll_result = rand7()

        # Discard values outside the range 1-7
        if roll_result <= 7:

            # Map the 7 possible outcomes to 1-7 directly
            return roll_result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Generate a number using the 7-sided die and store it.
Generate another number using the 7-sided die and store it.
Combine these two numbers to create a new number with more possibilities than either die alone.
If the combined number falls within the range we can use to fairly map to 1-10, then perform the mapping and return the result.
If the combined number is outside the usable range, repeat the entire process from the start, generating two new numbers using the 7-sided die.
By repeatedly combining rolls and rerolling when outside the target range, you eventually get a number that can be fairly mapped to the desired 1-10 range.

Code Implementation

def rand7():
    # Assume this function exists and returns a random integer in the range 1 to 7 (inclusive).
    pass

def rand10():
    while True:
        first_roll = rand7()
        second_roll = rand7()

        # Effectively create a uniform distribution from 1 to 49
        combined_result = (first_roll - 1) * 7 + second_roll

        # If the result is greater than 40, we reroll because it's biased.
        if combined_result <= 40:

            # Map the range 1-40 to 1-10, since 40 is divisible by 10.
            return (combined_result - 1) % 10 + 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
rand7() returns values clustered at one end of its range (e.g., mostly 1s)	The solution should still produce a uniform distribution for rand10() regardless of non-uniformity in rand7().
rand7() has a slight bias towards certain numbers	The rejection sampling method in rand10() is designed to minimize the impact of any slight biases in rand7().
Integer overflow when combining results from multiple rand7() calls.	Carefully choose combinations and modulo operations to avoid exceeding integer limits.
The theoretical maximum number of calls to rand7() before a valid rand10() value is generated is very high.	The algorithm should still terminate eventually, but consider logging or monitoring if the average number of calls is significantly higher than expected.
rand7() returns 0 (although this is outside its specified range, it's important to consider unexpected behavior).	Handle this case by treating 0 as an invalid return and re-calling rand7().
Stack overflow if using recursion excessively in case of extremely biased rand7() function.	Convert the recursive approach to an iterative one, if implemented using recursion.
The generated number has a high probability of being a certain value.	The solution should produce numbers between 1 and 10 with equal probability, even when called many times.
The number of calls to rand7() impacts performance.	Minimize the average number of calls to rand7() required to generate a single rand10() value by efficiently combining its outputs.

rand7() returns values clustered at one end of its range (e.g., mostly 1s)

How to Handle:

The solution should still produce a uniform distribution for rand10() regardless of non-uniformity in rand7().

rand7() has a slight bias towards certain numbers

How to Handle:

The rejection sampling method in rand10() is designed to minimize the impact of any slight biases in rand7().

Integer overflow when combining results from multiple rand7() calls.

How to Handle:

Carefully choose combinations and modulo operations to avoid exceeding integer limits.

The theoretical maximum number of calls to rand7() before a valid rand10() value is generated is very high.

How to Handle:

The algorithm should still terminate eventually, but consider logging or monitoring if the average number of calls is significantly higher than expected.

rand7() returns 0 (although this is outside its specified range, it's important to consider unexpected behavior).

How to Handle:

Handle this case by treating 0 as an invalid return and re-calling rand7().

Stack overflow if using recursion excessively in case of extremely biased rand7() function.

How to Handle:

Convert the recursive approach to an iterative one, if implemented using recursion.

The generated number has a high probability of being a certain value.

How to Handle:

The solution should produce numbers between 1 and 10 with equal probability, even when called many times.

The number of calls to rand7() impacts performance.

How to Handle:

Minimize the average number of calls to rand7() required to generate a single rand10() value by efficiently combining its outputs.