Given random5(), implement random7()
This article looks at the interview question - Given the function random5
that generates and returns a uniformly distributed random integer from 1 to 5, implement random7
that returns a uniformly distributed random integer from 1 to 7.
This is a classic probability problem that turns out to be deceptively tricky since solutions that seem fine don’t end up filling the uniformly distributed requirement.
Analysis
To start off, let’s reread what we’re supposed to do:
implement
random7
that returns a uniformly distributed random integer from 1 to 7.
We’re dealing with integers not floats, so it’s not as simple as multiplying random5
by 7/5
. It also needs to be uniformly distributed just like random5
, meaning we cannot just return the result of random5() * 2 % 7 + 1
since that will favour the integers 2, 3 and 4 twice as much as the rest.
How about this then?
(random5() + random5() + random5() + random5() + random5() + random5() + random5()) % 7 + 1
This turns out to be a very common answer to the problem, but does each number have an equal chance of being generated?
random5
gives a 20\% chance to return each of the numbers from 1 to 5. Adding random5
7 times will give up a number from 7 to 35. In order to get the value 7, we need to ‘roll’ 1 every time random5
is called which would be 0.2^{7} = 0.00128\% chance, this is also the chance of any particular permutation of rolls occurring. Whereas the value 8 can be generated by rolling 1 on 6 of the calls to random5
and 2 on the other one, giving up a possible 7 different permutations that could occur and therefore a 0.2^{7} \cdot 7 = 0.00896\% chance of occurring.
This trend continues, leading to the middle numbers having a larger chance of occuring.
A good solution to the problem would be to look at it like a decision tree. Calling random5
once to get 5 choices (20\% chance each) that are then split up into another 5 choices (4\% chance each). Giving 25 choices in total, each of which map to a particular action.
Choice number | Action |
---|---|
1-21 | Return choice number % 7 + 1 |
22-25 | Return random7() |
With this solution, in a single call each number has a 12\% chance of returning and there is a 16\% chance that random7()
will be called again recursively and returned.
Code
public static int random5() {
return new Random().nextInt(5) + 1;
}
public static int random7() {
// Get 0, 5, 10, 15 or 20 then add 0-4 (4% chance for 0-24)
int val = (random5() - 1) * 5 + (random5() - 1);
// If 0-20, return the result modulo 7 + 1 (12% chance for 1-7), otherwise
// call recursively (16% chance)
return val >= 21 ? random7() : val % 7 + 1;
}
function random7(random5) {
// Get 0, 5, 10, 15 or 20 then add 0-4 (4% chance for 0-24)
var val = (random5() - 1) * 5 + (random5() - 1);
// If 0-20, return the result modulo 7 + 1 (12% chance for 1-7), otherwise
// call recursively (16% chance)
return val >= 21 ? random7(random5) : val % 7 + 1;
}
Textbooks
Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.