4.2 of 5
www.google.com Mountain View, CA 5000+ Employees

"Make a perfect Random7() function to produce numbers from 1 to 7 using Random5() function which is perfect."

Part of a Software Engineer Interview Review - one of 2,998 Google Interview Reviews

0
of 2
a = 0;
do {
a = rand5() + rand5() - 1
while (a > 7);
return a;
- Claudio on Aug 21, 2012 Flag Response
0
of 1
vote
The above solution by Claudio is not correct.
1 = (1 + 1) - 1, with prob = x,
7 = (4 + 4) - 1, with prob = x,
But, 3 = (1 + 3) -1 and (2 + 2) -1, with prob = 2x.
And 4 = (2 + 3) - 1, (1 + 4) - 1, and (2 + 2) -1, with prob = 3x.
---
This "could" be the solution.
/**
* The probability for each number in 1 - 5 in rand5 is 1/5
* The probability for each number in 1 - 5 in rand7 should be 1/7
* and 6 and 7 should be 1/7 and 1/5.
* In order to achieve this, multiple the rand5 with 5 and divide it by 7.
*
*/
public class Q {

public static void main(String[] args) {
for(int i = 0; i < 10; i++){
// First, remove the added 1, multiply by 5, then get the remainder
// when divided by 7, and add the 1.
System.out.println((((rand5() - 1) * 5) % 7) + 1);
}
}

private static int rand5() {
// ((Math.random() * 10) % 5) returns 0 - 4; so add 1.
return (int) ((Math.random() * 10) % 5) + 1;
}

}
- PS on Sep 2, 2012 Flag Response