Google Interview Question

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

Interview Answers

Anonymous

Sep 2, 2012

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; } }

Anonymous

Aug 21, 2012

a = 0; do { a = rand5() + rand5() - 1 while (a > 7); return a;