Generate a Random Number Between 1 and 7, Given a Method that Generates a Random Number Between 1 and 5.

Full Question:

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. The distribution between each of the numbers must be uniform.

The given function, let's call rand(5), generates a random number between 1 to 5 in uniform manner. So, we can generate a random number from 1 to 5ⁿ in also uniform manner. For example, 25*(rand(5)-1) + rand(5) generates a random number between 1 to 125, and 5*(rand(5)-1)+rand(5) generates a random number between 1 to 25 uniformly. From this derivation, we can get a random number between 1 to 7 under uniform distribution.

public static void main(String args[]) {
Random g = new Random(1929304);
int N = 100000000;
int num[] = {0, 0, 0, 0, 0, 0, 0};

for(int i=0; i<N; i++ ) {
int j;
do {
j = 5*g.nextInt(5) + (g.nextInt(5)+1); // uniform between 1 and 25
} while(j>21); // uniform between 1 and 21
num[(j%7)]++; // uniform between 1 and 7 (0 and 6)
}

for(int i=0; i< 7; i++ )
System.out.println(i+1 + ": " + num[i]);
}

Following box shows results after a hundred million times try.

1: 14289981
2: 14288932
3: 14286841
4: 14284775
5: 14283995
6: 14285958
7: 14279518

Posted in C, Google Interview Question, Interview Question, Java, MS interview Question, Programmer Interview Question, Programming, Random Number, Software Engineer Interview Question