Amazon Interview Question
Software Engineer / DevelopersIf game 1 is throwing the ball once and game 2 is attempting 3 time and getting atleast 2 shots in, then isn't it game 1 if p>1/2 and game 2 if p<1/2 ?
This was what I thought, In the case of game 1 the chances of basketing is 1/2
In the case of game 2, there are 8 possible outcomes for the event of shooting the ball thrice. Only 4 out of the 8 are successfull cases. Hence the chances of getting the price is 1/2, irrespective of the probability of getting one shoot right.
If p is the probability of putting a basket:
Of the 8 possible outcomes not putting a single basket in 3 attempts is one such outcome. Probability of not making a single basket in 3 attempts is (1-p)^3 If you remove that outcome from the possible outcomes, the remaining probability is 1-(1-p)^3. Now the probability of not putting 2 baskets (where not putting all three baskets is already considered) is (1-p)^2.
Removing the probability of not putting 2 baskets we are left with
1 - (1-p)^3 - (1-p)^2 equate this with p to find the breakeven point
Hence:
p = 1 - (1-p)^3 - (1-p)^2
Solve this for p to arrive at p = 0.382 (approx)
Hence if you can put a basket with a probability greater than 0.382 go for the 2 in 3 option. Else if your probability of putting a basket is below 0.382 stick with just one shot. Cheers.
Amol, your soln makes more mathematical sense, I am not sure how you arrived at "the probability of not putting 2 baskets (where not putting all three baskets is already considered) is (1-p)^2"
I think it is the same value as the probability of getting exactly 1 shot in out of 3,
ie 1*(1-p)*(1-p)
which is of course
(1-p)^2, is that
right?
This is a trick question. For all values of p, you are better off taking the 2-shot game rather than the the 3-shot game. In my opinion, this is also a terrible interview question for a software development position (unless, of course, the application domain involves statistics/probabilities).
Intuitively, think of it this way: Assume you take the 3-shot game. On your first shot, there are two cases to consider: you either hit or miss. In the case where you hit, then you have to make one of your next two shots to win the money. This is the same odds as the 2-shot game. In the case where you miss the first shot, you have to make *both* of the next two shots, which is considerably worse than the 2-shot game. Therefore, irrespective of p, you are always better off going with the 2-shot game.
Probablisticaly, this is derived as follows:
Proabilities in the 2-shot game
-----------------------
make 2/2: p^2
make 1/2: 2 * (p*(1-p))
make 0/2: (1-p) * (1-p)
Probabilites in the 3-shot game
--------------------------------
make 3/3: p^3
make 2/3: 3 * (p^2 * (1-p))
make 1/3: 3 * (p * (1-p) * (1-p) )
make 0/3: (1-p)^3
Note that the outcomes of the 2-shot game & the 3-shot game both sum up to 1, which is what you expect.
So, the probability of winning the 2-shot game is the sume of the 2/2 or the 1/2 outcomes, namely:
p^2 + 2((1-p) * p)
And the probability of the three shot game is the sum of the 3/3 or the 2/3 outcomes, namely:
p^3 + 3 * (p^2 * (1-p))
So, we want to know for what values of p is
p^2 + 2((1-p) * p) > p^3 + 3 * (p^2 * (1-p))
Through algrebraic manipulation, we get the following inequality:
0 < (p-1) ^ 2
Which is always true, for all values of p.
assuming your prob of scoring is 50%
each game, u hv 2 outcomes, u score or u miss.
so in game 1.
ur winning is 50% = 1/2
and in game 2.
ur winning is 1/2 * 1/2 = 25%
and that p value represents the prob of scoring.
hence, p^2 >1/2 would give u the value of p
needlessly to say, that would be sqrt(1/2).
p = 0.7071....
i believe this is kinda same as the above explanation
but i just think this is much easier to understand without heavy mathematical proof.
I think it should be as follows
expected value of game 1
1000*p
expected value of game 2
1000*((3choose2)p^2(1-p) + p^3)
so if you solve it comes out to be
game 1 = 1000*p
game 2 = 1000*(3p^2-2p^3)
so 1000*p = 1000 *(2p^2-2p^3)
then quad eq s.t. -2000p^2 + 3000p -1000 = 0
solve for p
p=1 or p=0.5
meaning if u r more skilled (i.e. above 50%) then take the first game.
To be precise:
1000*p = 1000 *(2p^2-2p^3) is cubic equation, not quadratic.
when you transform it to quad 1=3p-2p^2 , you are diving by p and assuming p not = 0, which is incorrect
It should be calculated as:
p=3p^2 - 2p^3 //diving by 1000
=> p (2p^2 - 3p^1 + 1) =0
=> either p=0 or 2p^2 - 3p^1 + 1=0
Thus three solutions of p=0,1/2,1
The reason I pointed this out is
for p=0, wining change game1=wining change game2
for 0.5>p>0 wining change game1 > wining change game2
for p=0.5, wining change game1=wining change game2
for 1>p>0.5 wining change game1 < wining change game2
for p=1.0, wining change game1=wining change game2
The probability that you miss all three: (1-p)^3.
Then 1-(1-p)^3 is the probality that you make at least one out of three (the probability that you don't miss all three).
Given two shots the probability that you miss both: (1-p)^2
Then 1-(1-p)^3 is the probality that you make at least one out of two (the probability that you don't miss all two).
That's all you need to find the probability of winning the second scenario, you just multiply them together: (1-(1-p)^3) * (1-(1-p)^2)
Just graph y = (1-(1-p)^3) * (1-(1-p)^2)
versus y = p
You will the intercepts are when p = 0 and when p is around .24 and when p is 1.
Look at the graph and you will see the answer, both are equal at 0 and 1, choice 1 is better < .24, choice 2 is better > .24.
Get out your probability textbook, this is a simple problem if you understand Binomial Distribution.
The "crossover" value for p is 0.5
If p < 0.5, you have a better chance at winning the first game.
If p > 0.5, you have a better chance at winning the second game.
Honestly though, this is an absolutely terrible question for a programming interview. If a candidate is just out of school and has just taken a probability class, they will answer this easily. Anyone else will probably get it wrong. Either way, it doesn't say anything about their ability to program.
If you go through an entire day's worth of interviewing, you'll be asked 10,000 programming questions - atoi, reverse the words in a string, deck of cards, etc. - of which, probably 3 are necessary to understand whether the person can actually write code on a day to day basis. As it turns out, you need employees to do more than just write code because ultimately -- a candidate's ability to reason, think and problem solve on their own says a great deal about their ability to program. Truly great candidates are able to do this.
The solution is :
for p=0, wining change game1=wining change game2
for 0.5>p>0 wining change game1 > wining change game2
for p=0.5, wining change game1=wining change game2
for 1>p>0.5 wining change game1 < wining change game2
for p=1.0, wining change game1=wining change game2
Amol-B2 used the equation :p = 1 - (1-p)^3 - (1-p)^2
This is wrong coz, left side = chance of wining game1
right side = chance of loosing game2, and both can't be same
use either (1) p=3p^2 - 2p^3 //equating winning chances
or (2) 1-p=1 - (1-p)^3 - (1-p)^2 //equating loosing chances
Both equations (1) and (2) has three solutions for p at 0, 1/2 and 1
Logic:
Amol-B2 has posted his logic, which seems to me very reasonable except the equation is faulty and
hence the result.
For those still willing to have my approach see below:
Lets say o denoted failure in one try to basket and x represent success in busketting in one try.
Now in the second game, the number of the possible out come = 2 outcome of first throw X 2 outcome of
second throw X 2 outcome of third throw
=2*2*2
=8
They can be denoted as,
E1> 000
E2> x00
E3> 0x0
E4> 00x
E5> xx0
E6> x0x
E7> oxx
E8> xxx
Pr of winning in game 2 = Pr (E5 or E6 or E7 or E8) //where E denotes event
= Pr(E5) + Pr(E6) + Pr (E7) + Pr(E8) //since events are mutually exclusive
=pp(1-p) + p(1-p)p + (1-p)pp + ppp //each event consists of three independent
//events(trials) of throwing the ball
=3p^2 - 2p^3
Of coure the chance of winning first game=p
Now solve p=3p^2 - 2p^3 and remember this is a cubic equation and must have three solutions (real or
imaginary)
Refer to my reply to posting of 'math' above for the solution.
Note: Those who are wondering why Pr(E5) != [(no of ways E5 can happen) / (Total Possible E's)] = 1/8
You must remember that this rule is true only when all events E1 thru E8 are equaly likely.
Even though each throw can have either basket or not, still these two outcomes are not equaly likely due
the p associated with each outcome. Thus the probability that one throw will end up as basket is p, not
1/2. Similarly the probability that each throw will end up as not-basket is (1-p) not (1-1/2=1/2).
Since each throw is not equally likely, the events E1, E2..E8 being collection of three successive throws
are not equally likely.
To be even more precise, lets say three throws are denoted bt T1, T2 and T3.
Thus Pr(E5)=Pr( T3=not basket given T1 and T2 are basket)
=Pr (T3= not basket) . Pr(T1 and T2 are basket) //since each throw is independent events
=Pr (T3=not basket).[Pr(T2=basket given T1=basket)]
=Pr(T3=not basket).[Pr(T2=basket). Pr(T1=basket)]
=(1-p)p.p
Hope I made sense
Expected value of one shot game, E1 = 1000p
- Kevin June 02, 2005Expected value of three shot game, E3 = 1000(probabiliy of making 2 or 3 balls)
= 1000(p^3 + 3p^2(1-p))
= 1000(-2p^3 + 3p2)
Looking at these two expected values, E1 = E3 when when p=1,0, and E3 > E1 when p > 1/2.
In English, it doesn't matter which game I play if p=1 or 0.
If p < 1/2, I'll take game 1. If p > 1/2, I'll take game 2.