Bloomberg LP Interview Question
Software Engineer / DevelopersI think you are absolutely correct. I have provided a detailed explanation as a separate answer.
For the people above you claim that 91/100^10 is the correct solution, should the solution not be:
(N-9)/(NP10) ??
As it wasn't given in the question that our data set has only 100 numbers. It could have an infinite number of numbers?
For istance if there are only 10 numbers in the data set to draw from then:
(10-9)/(10P10) = 1/3628800
Which is correct as there are 10P10 (3628800) ways to arrange the numbers 1 to 10 but only 1 of these solutions has consecutive ascending numbers?
Let us assume that the number generator generates numbers in the range [1..N]. Each number is equally likely to be generated (as the generator is perfect) and each generation is independent of the other. For example, picking the third (or any other) number from the generator has no effect on the subsequent picking (fourth, fifth...tenth number).
Now, let us think about the problem as having ten slots. How many ways this slots can be filled up? The first slot can have any values from [1..N] and hence N values. Similarly, the second slot can have any values in the range [1..N] (as repetition is allowed). Therefore, the total number of ways ten numbers can be generated by the generator is N*N*... (ten times multiplication) = N^10.
Now how many ways, 10 consecutive numbers can be generated from the range [1..N]. Let's see,
1 2 3 4 5 6 7 8 9 10 --- that's 1 way
2 3 5 6 6 7 8 9 10 11 --- that's another way
3 4 5 7 7 8 9 10 11 12 --- that's again another way
I hope you can see the pattern and the last consecutive element possible is
N-9 N-8 N-7 N-6 N-5 N-4 N-3 N-2 N-1 N --- that's the final consecutive element possible.
Therefore, the total number of consecutive elements possible is N-9.
So, the probability of a perfect generator generating ten consecutive number is
total number of consecutive numbers
= -------------------------------------------------
number of ways ten numbers can be generated
(N-9)
= --------------------
N^10
@beo
I don't think your statement "The probability to generate a number that is bigger is equal to the probability to generate a smaller number, i.e the probability for a bigger is 1/2" is true...
This is true only if your number is average of the min and max of the random number generated by the generator. For e.g. if the range is 1-100 and your first number is 25, then p(smaller)=24/99 and p(bigger)=75/99
Please correct me I'm wrong.
if random generator generates number from a to b
then the first number it has to select from a to b-9( because it has to select next 9 more consecutive number)
so the probability of selecting first number will be->((b-9)-a)/b-a
=>(b-a-9)/(b-a)
for second no.->1/b-a
for third no.->1/b-a
..
..
..
for tenth no.->1/b-a
so the total prob-
(b-a-9)/b-a * 1/(b-a)^9
=>(b-a-9)/(b-a)^10
After the first random number has been generated, the next one could be either bigger, or smaller than the first one (let's assume that for a perfect random generator the probability to generate a number that is EQUAL to the previous one is zero).
The probability to generate a number that is bigger is equal to the probability to generate a smaller number, i.e the probability for a bigger is 1/2.
The probability to generate 9 consecutive ascending numbers is therefore (1/2)^9
I think the answer should be:
{(1/N)}*{1/(N-1)}*{1/(N-2)}*{1/(N-3)}*....*{1/(N-10)}
N = range of the random number generator... As N increases, the solution converges to ZERO.
The calculation is straight forward and ans = (# of correct sequences)/(# of total combinations)
And hence the result is 91/100^10
If the numbers are chosen from an arbitrary probability distribution f(x)
defined from a to b (so that
integral_a^b f(x) dx=1
)
then the probability that we choose one number is 1, the probability
that we choose two numbers such that x2>x1 is 1/2:
P(x2>x1)=int_a^b f(x1) (int_x1^b f(x2) dx2) dx1 = 1/2!
This is true with very few restrictions on f(x) except that it be
continuous function of x, i.e, not a purely discrete distribution (like
choose 10 integers from 1 to 100). The 1/2 makes sense because
if we choose 2 numbers randomly, 50% of the time x1 will be
bigger than x2 (if they are chosen randomly and independently from the
continuous distribution f(x)). For three numbers, to get 1/6, calculate:
P(x3>x2>x1)=int_a^b f(x1) (int_x1^b f(x2) (int_x2^b f(x3) dx3) dx2) dx1 = 1/3!
Again, it is quite independent of the shape of f(x). You can try the uniform distribution given by others in the forum, or you can test it with f(x)=exp(-x) with
a=0 and b=infinity.
For the people above you claim that 91/100^10 is the correct solution, should the solution not be:
(N-9)/(NP10) ??
As it wasn't given in the question that our data set has only 100 numbers. It could have an infinite number of numbers?
The first number x1 you can select almost freely - any number except the last nine numbers of the generator - so the probability of choosing any but the last nine numbers is:
p1 = 1 - 9/N
assuming that the rnd-gen generates numbers from {1,...,N}
The next number x2 has to be x2=x1+1 so the probability of getting it is: 1/N
The next number x3 has to be x3=x2+1 so the probability of getting it is: 1/N
The next number x4 has to be x4=x4+1 so the probability of getting it is: 1/N
...
The next number x10 has to be x10=x9+1 so the probability of getting it is: 1/N
=>
P = p1*(1/N)^9 = (1-9/N)*(1/N)^9
Or at least close.
Am I hired? What's Bloombergs.. :)
We assume that probability of creating two equal numbers is 0 considering we have a good random number generator.
if you have two numbers x and y, x being bigger than y will be 50%. (a > b, b > a)
if you have a, b, c then you have 3! possible combinations.
a > b > c, a > c > b, b > a > c, b > c > a, c > a > b, c > b > a
for 10 number you have 10! possible combinations. Therefore probability is 1/10!.
You can try it with this perl code (this is for 4 numbers)
perl -e 'for ($i = 0; $i < 100000000; $i++) { $a = rand(); $b = rand(); $c = rand(); $d = rand(); if ($a > $b && $b > $c && $c > $d ) { $count++; } } $count = $count/100000000; print $count, "\n";'
0.04169784
0.04169784 is pretty close to 1/4! = 1/24
- Jit October 24, 2010