Growing with the Web

Given random5(), implement random7()

Published , updated
Tags:

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.

 

Comments

comments powered by Disqus
Like this article?
Subscribe for more!