## Bloomberg LP Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
11
of 11 vote

``````To generalize the idea, let's say the random number generator generates from number 1 to 100. Then as per the question, the number of sequences that could be our desired output is (1..10) or (2..11) or (3..12) and so on till (91-100). So, there are 91 sequences. The total number of solution space that we have is 100^10.
The probability is 91/(100^10).
Guys, correct me if I am wrong.``````

Comment hidden because of low score. Click to expand.
0

I think you are absolutely correct. I have provided a detailed explanation as a separate answer.

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

Why NP10 ? The solution space has no restriction to be unique!

Comment hidden because of low score. Click to expand.
5
of 5 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

here solution space is infinity so you can not say anything about probability so its 0.

Comment hidden because of low score. Click to expand.
1
of 1 vote

@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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

here solution space is infinity so you can not say anything about probability so its 0.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess it will be (1/10)^9

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

So, going to your solution {(N-f)/N-1)}^9 might be the solution, where f=first number generated and N is the range of the generator.......
but this is not confirming the numbers are consecutive......

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Correct

Comment hidden because of low score. Click to expand.
0
of 0 vote

Prob. = (N - m + 1)/N * N^(-m + 1), where N is # of values that can be generated from the random generator and m is the length of the array consisting of the consecutive elements.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The calculation is straight forward and ans = (# of correct sequences)/(# of total combinations)
And hence the result is 91/100^10

Comment hidden because of low score. Click to expand.
0

exactly.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why should the range matter? We have 10 distinct numbers, which make 10! possible permutations, same as all possible sequences. Only single sequence is actually sorted in ascending order, which leaves us with 1/10! chance.
Does it sound correct?

Comment hidden because of low score. Click to expand.
0
of 0 vote

* Second one bigger than first one is 1/2.
* Third one bigger than first two is 1/3. (1/3 smaller than first two, 1/3 between first two, 1/3 bigger than first two)
* Fourth one bigger than first three is 1/4.
.
.
Total: (1/2) * (1/3) * .... (1/10)

Comment hidden because of low score. Click to expand.
0
of 0 vote

1 over 10!
Think about two consecutive numbers it is 1/2; three 1/6
Let's assume random generator of Unif(0,1) the probability to generate consecutive k numbers in ascending order is p(k)
Then p(k+1)=integral_from_0_to_1{p(k)*x^k} then 1/n!

Comment hidden because of low score. Click to expand.
0
of 0 vote

1 over 10!
Think about two consecutive numbers it is 1/2; three 1/6
Let's assume random generator of Unif(0,1) the probability to generate consecutive k numbers in ascending order is p(k)
Then p(k+1)=integral_from_0_to_1{p(k)*x^k} then 1/n!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Why nobody vote for this solution. It is the only correct one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

answer is 1/2^9. since probability of taking first<second is 1/2.first<second<third is 1/2^2. since in each picking we havee 2 choice select >/<

Comment hidden because of low score. Click to expand.
0
of 0 vote

(1/10)^n, where n is the amount of numbers generated. e.g., for 1 number generated, probability is 1/10 but for two it is 1/100. Notice as n -> infinity, the probability tends toward zero, as mentioned by the infinite solution space comments.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.. :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

ermmm..0?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.