He asked me to give him the algorithm for the Fibonacci number in both iterative and using recursion.
I failed to solve a problem regarding the algorithm of a rand7 function by using a rand5 function.

Question

He asked me to give him the algorithm for the Fibonacci number in both iterative and using recursion. 
I failed to solve a problem regarding the algorithm of a rand7 function by using a rand5 function.

Matteo Gobbi · Accepted Answer

Supposing you have the rand5 function which return a number between 1 and 5,
you just need to launch rand5 for 7 time to have so an equal probabilistic distribution to cover the number from 1 to 7:

public int rand7() {

    int num = 0;
    
    for(int i = 0; i < 7; i++) {
        num += rand5();
    }
    
    return num%7+1;
}

Matteo Gobbi · Answer

Sorry, the mine previous expiation is right, but need to call rand5 8 time, and return the value without the +1:

public int rand7() {

    int num = 0;
    
    for(int i = 0; i < 8; i++) {
        num += rand5();
    }
    
    return num%7;
}
    

And this is the distribution:
        
        8   <---   1
        9   <---   2
        10  <---   3
        11  <---   4
        12  <---   5
        13  <---   6
        14  <---   7
        
        15  <---   1
        16  <---   2
        17  <---   3
        18  <---   4
        19  <---   5
        20  <---   6
        21  <---   7
            
        22  <---   1
        23  <---   2
        24  <---   3
        25  <---   4
        26  <---   5
        27  <---   6
        28  <---   7
            
        29  <---   1
        30  <---   2
        31  <---   3
        32  <---   4
        33  <---   5
        34  <---   6
        35  <---   7
        
        36  <---   1
        37  <---   2
        38  <---   3
        39  <---   4
        40  <---   5
        41  <---   6
        42  <---   7

Matteo Gobbi · Answer

Sorry guys the previous are wrong.
The key is to find "n" t.c.  n*5-(n-1) = n*5-n+1 is a multiple of 7

n = 5

25 - 4 = 21 = 7 * 3


public int rand7() {

    int num = 0;

    for(int i = 0; i < 5; i++) {
        num += rand5();
    }

    return num%7+1;
}


And this is the distribution:

5 <— 6
6 <— 7
7 <— 1
8 <— 2
9 <— 3
10 <--	4
11 <--	5

12		6
13		7
14		1
15		2
16		3
17	        4
18		5

19		6
20		7
21		1
22		2
23		3
24		4
25		5

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches

Work With Us