Re: some interview questions

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

Digital Puer wrote:
I got these questions on computer job interviews but could not
figure them out.


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.

I came up with a function that returns a random integer between
1 and 7, but it is not uniformly distributed. Basically, re-map 1 to 5
to be 0 to 4, then add two of those random numbers together
to get a value between 0 to 8, then do modulo 7, returning a
number between 0 and 6, and then re-map to 1 to 7. This
solution more heavily favours 0 and 1; I do not know how
to make a solution with uniform distribution.

2. Suppose you have a function that returns random 64-bit integers
without checking if a particular integer has already been used. How
many integers would be returned before the probability that an integer
has been repeated is above 0.5?

This is probably similar to the birthday problem, which I didn't
quite remember.

.

Relevant Pages

  • Re: some interview questions
    ... int random17() ... sum += random15; ... // integer division truncates quotient ... many integers would be returned before the probability that an integer ...
    (sci.math)
  • Re: some interview questions
    ... int random17() ... sum += random15; ... // integer division truncates quotient ... many integers would be returned before the probability that an integer ...
    (sci.math)
  • Re: Algorithm
    ... Wont sum of all positive numbers will be the largest sub-array? ... int getint ... struct sofar *next; ... struct sofar *discard(struct sofar *trail) ...
    (comp.lang.c)
  • Re: Arrays vs Buffers
    ... and the next array access is dependent on the value ... and then return the overall sum to the test harness ... nextPointer(int[] array, int point) ... pointer = nextPointer; ...
    (comp.lang.java.programmer)
  • Re: sum(2,4,3,5,-1,...)
    ... The only example I have to imitate is the one on p.289 ... of an array related to the first argument of the function sum I'm ... int sum ... no args, and get 0, like you can do in Scheme or C++. ...
    (comp.lang.c.moderated)
Quantcast