Microsoft Interview Question
Developer Program EngineersCountry: United States
Interview Type: In-Person
Total amount is X
Total loosing moves are N
To survive these N loosing moves and still have some cash left, the amount we can bet on a move is X/(N+1)
Therefore at each stage of the game we bet X/(N+1) amount, where X is the total amount left after each move, and N is the number of loosing cards remaining in the deck.
qouestion is not so clear that whether to bet all amount I am having a particular time or to bet a part of it as per my desire.
Assumption - we can bet any amount which is less than X
- 2n cards have to play
- So in first bet, I will use 2n/x amount.
- in worst case, if i am loosing in all first n bets
- again n+1 to 2n , all left cards are winning card.
Hence we can play with all cards, if starting amount is 2n/x.
Assuming that one can bet any amount between 0 and one's bankroll, the strategy maximizing the expected earnings is to bet 0 if there is at least one losing card remaining and everything otherwise.
Clearly if the remaining deck is all winning or all losing this is the optimal strategy. Otherwise, define Value(W, L) to be the value of a game with starting bankroll 1 and W winning cards and L losing. For all W > 0 and L > 0 we have the recurrence
Value(W, L) = max_{0 <= Y <= 1} (W/(W+L)) (1+Y) Value(W-1, L) + (L/(W+L)) (1-Y) Value(W, L-1).
The quantity being maximized is linear in Y, and clearly Value(W-1, L) < Value(W, L-1). Thus the optimum is Y=0.
I got one approach for this,not sure if it is optimum.But with this algorithm in worst case also player will have more money at the end of the game what was with him at the begining.
1- Determine LossCount=n and WinCount=n
2- Determine the money to be bet.
a- If LossCount =0 then bet the whole money
b - Else devide the remaining money by (LossCount + 1)
3- Play the card.
a- If it is loss then LossCount-- and RemaningMoney = RemainingMoney - BetMoney.
b - Else WinCount-- and RemainingMoney=RemainingMoney+BetMoney
4- Go to Step 2 and repeat this till nth time.
Logic for choosig the divider as (LossCount +1) - We need to survive in the game till we start wining.Suppose we have X money and n win and n Loss chnaces.In worst case for the first nth time we lose.So for the next (n+1)th time we need minimum money to play.
It is horrible to put up ill-specified problems on such a useful forum . It wastes time. Moreover, the phrase in the problem "I solved it" is itchy. One must put good questions and realise that he solved it because he encountered it first
sorry bro, my intension is not to irritate/ demotivate any one.
I am so curious to know the answer.
this is the qn. asked in 4th round for 6+ yr. experienced.
I got one approach for this,not sure if it is optimum.But with this algorithm in worst case also player will have more money at the end of the game what was with him at the begining.
- ravi July 08, 20121- Determine LossCount=n and WinCount=n
2- Determine the money to be bet.
a- If LossCount =0 then bet the whole money
b - Else devide the remaining money by (LossCount + 1)
3- Play the card.
a- If it is loss then LossCount-- and RemaningMoney = RemainingMoney - BetMoney.
b - Else WinCount-- and RemainingMoney=RemainingMoney+BetMoney
4- Go to Step 2 and repeat this till nth time.
Logic for choosig the divider as (LossCount +1) - We need to survive in the game till we start wining.Suppose we have X money and n win and n Loss chnaces.In worst case for the first nth time we lose.So for the next (n+1)th time we need minimum money to play.