Bloomberg LP Interview Question for Software Engineer / Developers






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.

- Jit October 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- rayhan August 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- ktk180 June 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- pyne.suvodeep November 06, 2012 | Flag
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

- rayhan August 12, 2011 | Flag Reply
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.

- Harit October 24, 2010 | Flag Reply
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
Please correct me I'm wrong.

- shekhar2010us February 10, 2011 | Flag Reply
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

- Ali_BABA February 15, 2012 | Flag Reply
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.

- Harit October 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- gulusworld1989 October 24, 2010 | Flag Reply
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

- beo November 01, 2010 | Flag Reply
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......

- shekhar2010us February 10, 2011 | Flag Reply
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.

- shekhar2010us February 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correct

- James March 01, 2011 | Flag
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.

- Anonymous February 24, 2011 | Flag Reply
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

- KeepTrying March 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

exactly.

- rayhan August 12, 2011 | Flag
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?

- wolfy July 15, 2011 | Flag Reply
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)

- Anonymous July 25, 2011 | Flag Reply
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!

- Pegasi February 26, 2012 | Flag Reply
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!

- Pegasi February 26, 2012 | Flag Reply
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.

- Doctor Jones May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Pegasi September 08, 2012 | Flag
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?

- ktk180 June 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- ktk180 June 18, 2012 | Flag
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 >/<

- shibin November 07, 2012 | Flag Reply
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.

- ethan January 11, 2013 | Flag Reply
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.. :)

- maxp February 28, 2014 | Flag Reply
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

- Olcay Boz December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

ermmm..0?

- Anonymous October 24, 2010 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More