Re: some interview questions

Digital Puer wrote:
1. Given a function which produces a random integer in the range
1 to 5, write a function which produces a random integer in the
range 1 to 7.


Jim Gibson wrote:
For a solution to 1., how about this ...

int random17( )
{
int sum = 0;
int result;

// call function 7 times, summing the result [1..5]
for( int i = 0; i < 7; ++i)
sum += random15( );

// integer division truncates quotient
result = sum / 5;

// round up
if( (sum % 7) > 3 )
++result;

return result;
}


M.J.T. Guy wrote:
That produces nothing like the required distribution. There are 5^7
equiprobable possible outcomes from the 7 calls of random15(). Since
this isn't a multiple of 7, the probabilities of getting each of 1 .. 7
can't be equal.

Yep, this is the same problem with rolling multiple dice and adding the
face values of each die, which is why 7's are more likely than 11's.

Use William Hughes's approach and multiply each throw by a
power of 5 to get a larger range to choose from (e.g., [0,24] for
two throws), and simply ignore (rethrow) any results outside
the range of [0,7n-1].

Another approach is to make multiple calls to rand5, discard
the result if it's greater than 4, then add a bit to an accumulator,
where the bit is 0 if the rand5 call is even, and 1 if it's odd.
Do this until you get three bits. If the bits are 000, keep generating
bits until something other than 000 is produced, then those three
bits are your answer.

How come no one has attempted an answer to (2)?

.