Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
I don't think all of these answers consider the case that if you succeed, you won't continue making shots.
For example in challenge 1, you could make both shots ( p * p ), fail the first shot ( (1-p) * p * p) or fail the second shot ( p * (1 - p) * p). This sums to
2 * (1-p) * p^2 + p^2 (which simplifies to p^2 * (3-2p) )
And for the second challenge
p^4 (make all shots)
4 * (1-p) * p^4 (fail one shot)
10 * (1-p)^2 * p^4 (fail 2 shots)
which simplifies to
p^4 * ( 10 p^2 -24 p + 15 )
solving for these equations, you find that if shot percentage is less than about 78.5%, Challenge 1 should be picked. Challenge 2 should be picked if shot percentage is better than 78.5%
It depends on how good you are. Current posts on this thread assume you have a 50% shooting accuracy.
The longer method involves a [n choose p * x^p * (1-x)^n-p] vs [m choose q * x^q * (1-x)^m-q] computation.
The shorter solution is that if your shooting accuracy is x and the desired accuracy is y
If x<y, you choose lesser trials; Else choose more trials.
This is because, probabilities are truly reflected over a larger sample space. For example, coin toss probability starts at an extreme number and evens towards 1/2 over several trials.
If x<y, you are looking for an extreme result and hence better to choose small sample. If x>y, you are looking for the normal result and hence choose the larger sample.
Form is temporary. Class is permanent.
While the two challenges have the same probability, we might have to take into account the independence condition in between throws. Suppose that you choose 6 shoots, after each throw, you might have a better throw and thus the independence between the shoots are violated. The player might want to choose the second option in light of this!
Using Binomial Coefficient When taking 6 attempts:
Challenge 1: C(3,2) * C(3,2) = 9
Challenge 2: C(6,4) =15
Since there are 15 ways to score 4 out of 6 in challenge 2 scheme compared to 9 ways to score 4 out of 6 in challenge one scheme, challenge two is a better choice as it gives the more flexibility to the shot taker.
Why hasn't anyone considered the situations where a player wouldn't continue. For example, for 2 out of 3 shots, if the percentage change to succeed is 'p', then the chance to succeed is equal to:
(1-p) * p * p + p * (1-p) * p + p * p.
This simplifies to
2*(1-p) * p * p + p * p (which is basically the probability of only 1 miss plus the probability of no misses)
Here's a short table:
p | succeed
25% | 15.6%
50% | 50.0%
75% | 84.4%
for Challenge 2, the chances can be computed similarly:
10 * (1-p)^2 * p^4 + 4 * (1-p) * p^4 + p^4 = p^4 ( (1-p) * ( 10 * (1-p) + 4 ) + 1 )
Here's a table:
p | Win
25% | 3.8%
50% | 34.4%
75% | 83.1%
There is, however, a point a which it's better to choose challenge 2. That's when p gets to about 78.5%
One should remember that if you get 3 out of 3 you win and if you get 5 out of 6 or 6 out of 6 you also win. One should also realize that this is not a coin toss with a fare coin rather a basket ball game. So the probability of getting one basket in a toss is not necessarily 50%.
Call the probability of getting one basket p
So for the first option you get
p*p*(1-p) + p*(1-p)*p +(1-p)*p*p + p*p*p
corresponding to basket basket miss + basket miss basket + miss basket basket + basket+ basket+ basket
or 3*p^2*(1-p) + p^3
3*p^2- 3*p^3 + p^3
3*p^2-2*p^3
For 4 baskets out of 6 you get
6 choose 4 case when you get exactly 4 baskets
6!/4! /2!
6 * 5 / 2
15
With a probability of p^4*(1-p)^2
p^4*(1-2*p+p^2)
p^4 - 2*p^5 + p^6
for a total probability of
15*p^4 - 30*p^5 + p^6
for 1 miss you get
6 possible sequences with a probability of p^5 *(1-p)
6*(p^5- p^6)
6*p^5 - 6*p^6
And the probability of 6 out of 6 is
P^6
So the total probability is
15*p^4 - 24*p^5 -4*p^6
Verses 3*p^2-2*p^3
So I guess the answer is: it depends on P which is probably why one gets to chose
If you turn it into an equality and dived both sides by p^2 you get
15*p^2 - 24*p^3 -4*p^4 = 3 - 2*p
But I don’t think there is a closed from for this though you may be able to factor it to find the cross over point. If someone wants to write the code and run it you should be able to solve this numerically.
Transfor this to
I went to a web root finder and
O dear I only get negative and complex roots
So it guess one is better than the other or I have made a mistake
P <= 1
So for 3-2*p you would win with 100% probability if you could get a basket with 100% probability that seems to work
For the other then
15*p^2 - 24*p^3 -4*p^4
You get 15-24-4 which is not 1
so I have an error and now it is time to go to sleep
I hand it over to whomever wants to take up the problem where I left off
In 6 choose 4 case when you get exactly 4 baskets, the total probability should be 15*p^4 - 30*p^5 + 15*p^6 ——you have missed a 15 before p^6.
And I finally got the result: when p > 1 or 0 < p < 0.1*(2-sqrt(34) or 0.1*(2+sqrt(34)) < p < 1, 4 out of 6 shall have larger possiblity of success.
They should take challenge 1. This is an n choose k problem. The probability of getting 2 out of 3 throws is 50%. There are 2^3 = 8 possible outcomes (e.g., makes it, misses it, makes it). To figure out how many of these 8 possible outcomes results in a win, add (3 choose 2), which equals 3, with (3 choose 3), which equals 1. 4/8 = 50%
- JRS November 13, 2014In challenge 2, there are 2^6 = 64 possible outcomes. To figure out how many of these 64 possible outcomes results in a win add (6 choose 4), (6 choose 5), and (6 choose 6) together. (6 choose 4) =15, (6 choose 5) = 6, (6 choose 6) = 1. So there are 22/64 possible outcomes where the player would win, giving the player a 34.375% chance of winning.
Since 50% > 34.375%, the player should choose challenge 1.