This is tough. The higher the number of heads to win the game (N), the bigger the tree, and the more conditions there will be.
"Actually who gives a fuck ?" perhaps is the right answer ? The geniuses in those firms brought the world of finance to the brink of collapse. It's time to stop revering those so-called whiz kids with egos too big to fail . Time to go back to the old fashioned way of conducting interviews .
I believe this is the solution for N-heads winning and N-tails losing in Y tosses where N<=Y<= (2 *N)-1. Here is some pseudocode double MinBankRollNeeded(#headsStillNeeded, #tossesRemaining) { //if we dont need anymore heads, we //need to have reached our profit goal if(headsStillNeeded == 0) return minimumBankRollNeededIfWeWin; if(headsStillNeeded > tossesRemaining) return 0; //if we have 1 toss remaining, we need //at least half of our final balance if(#tossesRemaining == 1) return minimumBankRollNeededIfWeWin/2; //otherwise we need to be halfway //between the minimum bankroll needed should this toss be a heads //and the minimum bankroll needed //should this toss be a tails return 0.5 *(MinBankRollNeeded(headsStillNeeded -1, #tossesRemaining-1) + MinBankRollNeeded(headsStillNeeded, #tossesRemaining - 1)); } Now, to find out how much to bet @ a given step, bet the maximum amount allowed such that we have the minimum bank roll needed to still win the game, should this upcoming toss not be heads. bet = CurrentBankRoll - MinBankRollNeeded(#headsStillNeeded, #tossesRemaining - 1) Example N = 4, tosses = 7 first bet is 100 - (MinRoll(4,6) ->0.5 *(MinRoll(3,5) + MinRoll(4,5)...etc) = 31.25 Anyways, this should construct a minimum bankroll tree that looks like the following with Starting Bankroll = 100 and MinimumBankRollNeededIfWeWin = 200 Code: 4/7 4/6 4/5 4/4 3/3 2/2 1/1 100 68.75 37.50 12.50 25 50 100 3/6 3/5 3/4 131.25 100 62.50 2/5 2/4 2/3 1/2 162.50 137.50 100 150 1/4 1/3 187.50 175
This one comes close but no cigar, because in two instances when you win the game there is only $166.66 accumulated. I really didn't want the job anyhow. Betting strategy: 1.Call the game over and end the game after three 1's and place no further bets. 2. Start by betting 1/3 of the original $100 on every flip. 3. If the game is not over, after getting two zeros bet all in the pot in the next and successive flips until the game is over. 111,00 $200.00 1011,0 $166.66 10101 $200.00 00111 $266.66 10011 $266.66 0111,0 $166.66 01011 $266.66 11001 $200.00 01101 $200.00 By the way where is Sjfan with the solution anyhow?
First, no one said that it's the ONLY interview question. Second, you can bullshit your way through work experience and skills. We've all heard that. But you can either solve a logic problem or you can't. You either have the facility to think things through, or you don't. Can't really fake that can't you. No, so no one gives a fuck about the answer itself.
I'm not miscalling it this time. This is the right answer. Nice use of recursion, btw - exactly how I would do it. If I were conducting the interview, the final question (and one whose answer I won't weigh too heavily on except as a tie breaker) is - what's the algorithmic complexity of this algorithm? and how does it compare to a non-recursive implementation. Once again, good job.