7.7 Jane Street Interview Question...Needing Help

[myownstrategy]

Hello everyone:

I need some help on two interview questions. They are given during Janestreet interview:

1. There are 50 noodles in a bowl. You can tie two ends of either one noodle or two different noodles, forming a nod.
Q: After 50 nods are tied. What is the expected value of number of circles in the bowl?

2. There are two dice. The game is as following: two dice will be thrown at once. Adding the number together you will get a number ranging from 2 to 12.
The probability of getting 12 is 40%, and 6% for getting 2,3,4,5,...11
Person A and B will need to guess what the number would be. The one who has a closer guess will win.
Q: A will guess first and then B guess, after they've guessed, two dice will be thrown at once, what number should A guess and what number should be B guess?

 

[euroazn]

2 Seems pretty simple.
We have the following probability distribution:
2 3 4 5 6 7 8 9 10 11 12
6 6 6 6 6 6 6 6 6 6 40

A starts at the right and keeps going left until his aggregate probability exceeds 50%. Then, if B chooses the next number on the left, B's chance is under 50% by the definition of the number we picked. If B chooses the number on the left, his chance is under 50% because 100->50% = <50%. So A chooses 10; B will end up choosing 9.

 

[pruse]

1) Say there are (n) noodles in the bowl. Condition on whether the first knot results in a loop or just a longer noodle. The probability of the former is (\frac{1}{2n-1}) while the probability of the latter is (\frac{2n-2}{2n-1}). Denote by (E_n) the expected number of loops given (n) noodles. Then (E_n = \frac{1}{2n-1}(E_{n-1}+1)+\frac{2n-2}{2n-1}E_{n-1}=E_{n-1}+\frac{1}{2n-1}) from which (E_{50}=1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{99})

 

[myownstrategy]

1) Say there are (n) noodles in the bowl. Condition on whether the first knot results in a loop or just a longer noodle. The probability of the former is (\frac{1}{2n-1}) while the probability of the latter is (\frac{2n-2}{2n-1}). Denote by (E_n) the expected number of loops given (n) noodles. Then (E_n = \frac{1}{2n-1}(E_{n-1}+1)+\frac{2n-2}{2n-1}E_{n-1}=E_{n-1}+\frac{1}{2n-1}) from which (E_{50}=1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{99})

great solution !

 

[toolzmanz]

2 Seems pretty simple.
We have the following probability distribution:
2 3 4 5 6 7 8 9 10 11 12
6 6 6 6 6 6 6 6 6 6 40

A starts at the right and keeps going left until his aggregate probability exceeds 50%. Then, if B chooses the next number on the left, B's chance is under 50% by the definition of the number we picked. If B chooses the number on the left, his chance is under 50% because 100->50% = <50%. So A chooses 10; B will end up choosing 9.

I got a reverse answer of what you had. When A is choosing, he should choosing the number that has the expected distance to the rest of the numbers as close to zero as possible. For example, the expected distance of 9 is " (7+6+5+4+3+2+1+0)*0.06-0.06-0.12-3*0.4=0.3" which is the smallest expected distance in this case. Therefore, Person A who chooses first will pick "9". Then when B is choosing, if he picks "8", his chance to win is "0.06*7=0.42"; if he picks "10", his chance to win is "0.06*2+0.4=0.52" thus he will choose "10" Thus person A chooses 9 and Person B choses 10.

 

[BBB]

A picks 10, B picks 9. Picking 10 guarantees the highest chance of winning. If A picks 9 then B can choose 10 and B will have a 52/48 advantage to win.

 

[euroazn]

I got a reverse answer of what you had. When A is choosing, he should choosing the number that has the expected distance to the rest of the numbers as close to zero as possible. For example, the expected distance of 9 is " (7+6+5+4+3+2+1+0)*0.06-0.06-0.12-3*0.4=0.3" which is the smallest expected distance in this case. Therefore, Person A who chooses first will pick "9". Then when B is choosing, if he picks "8", his chance to win is "0.06*7=0.42"; if he picks "10", his chance to win is "0.06*2+0.4=0.52" thus he will choose "10" Thus person A chooses 9 and Person B choses 10.

This is clearly sub-optimal for A; I outlined a strategy where he can win 52% of the time whereas you gave one where he only wins 48 percent of the time.

 

[ecoskian]

About the first problem: the first knot has a probability of 1 out of 99 of forming a circle (connecting two ends of the same noodle), the second one has 1 in 97 if the first was tied to itself, otherwise 1 in 98 (the previous knot eliminated one end, and even if it was tied to the other end of the noodle you can imagine being handled, a circle can still be formed but it will be comprised of two noodles). So on so forth, and from this one can obtain a distribution...Looking clearer now?

 

[Kangxi]

1) Say there are (n) noodles in the bowl. Condition on whether the first knot results in a loop or just a longer noodle. The probability of the former is (\frac{1}{2n-1}) while the probability of the latter is (\frac{2n-2}{2n-1}). Denote by (E_n) the expected number of loops given (n) noodles. Then (E_n = \frac{1}{2n-1}(E_{n-1}+1)+\frac{2n-2}{2n-1}E_{n-1}=E_{n-1}+\frac{1}{2n-1}) from which (E_{50}=1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{99})

When there are n noodles, why the total number of possible outcomes is n + n-1 = 2*n-1 , instead of n + 2Cn?

 

[Kangxi]

Is there any standard solution for Problem #2?

 

[pruse]

When there are n noodles, why the total number of possible outcomes is n + n-1 = 2*n-1 , instead of n + 2Cn?

Among the \(n\) noodles there are \(2n\) ends. Picking one end leaves \(2n-1\) other ends to match it with.

 

[Kangxi]

Among the \(n\) noodles there are \(2n\) ends. Picking one end leaves \(2n-1\) other ends to match it with.

OK, thanks

 

[nfernand]

I want to clarify something about Pruse's solution to the problem. Because there were 50 noodles and 50 knots, he could simply write the expectation as E( n). But in reality, the problem is more general, there are n noodles and m knots, and the expression is E(n,m). Then the recursive formula becomes:

E(n,m) = 1/(2n-1) * (E(n-1,m-1) + 1) + (2n-2)/(2n-1) * E(n-1,m-1)
= E(n-1,m-1) + 1/(2n-1)

This is because in each case (whether the first knot creates a loop or not) we end up with n-1 remaining noodles, and m-1 remaining knots to do.

To calculate E(n,m) then we just start at E(n-(m-1),1) = 1/(2(n-(m-1))-1) and add on the terms that he described. The point I'm trying to make is that you're not going down to when n = 1, you're going down to when m =1 (because that is the case where we know the answer). It just happens to be the case that in this particular problem, n=m, but if n > m (making fewer knots than noodles) the approach still works, you just have to cut it short.