Barclays Capital Interview Question
Software Engineer / Developers- Initially you have 29 head 71 tails.
- Now randomly choose 29 from here.
- Now the original pile has 29-x head and 71-y tail where x is the number of heads in new pile and y is the number of tails in new pile.
- So x+y = 29 and y = 29-x
- Now if you flip all the coins in the new pile you will have y many head coins and you already know 29-x = y. So there you go, you have the same number of heads in each pile.
He is correct with respect to the spirit of it, but the answer he gives is not as clear as it could be.
Say you take at random 29 coins from the pile and leave the other pile with 71. In the first pile of 29, there are 29 - x heads and x tails. In the second pile there are x heads and 71 - x tails. So, if you flip all the coins in the first pile, there will be x heads in it. So the two piles have the same number of heads.
For example, if you by a stroke of luck happen to choose all 29 heads for your first pile, it leaves none in the 71 coin pile. If you flip all the coins in the 29 coin pile, you will have none in either pile.
Wrong answer. How can you say X in pile 1 has same value of X in pile 2? Doesn't make sense.
In 29 set, I say 10 (29 -X) are heads, rest are tails (X). And then I flip it. Now, there 19 heads. Alright?!
How can you say that the other set has 19 heads (or tails, for that matter). Or 10 head/tails in second set. My assumption says other set has 50, 21; or 0, 71, or 43, 28... which one is equal to X ????
100 coins (71 tails+ 29 Heads)
Pick 29 Coins (Heads+tails) in one pile at random
Say in one pile (20 Tails + 9 Heads)
in second pile (51 tails + 20 Heads)
Now flip all the 29 coins of first pile......so it will contain
20 Heads + 9 Tails....Now both pile will contain same number of Heads......Cheers......
classic coin flipping problem.
- blueskin.neo November 18, 2010divide 100 coins into 29 and 71 piles.
flip all 29 coins in the first pile. DONE!
how? Consider we have a bit string of length 100, 29 bits are set and 71 are 0's.
if we split the string into 29 and 71 strings randomly, we should have 29-k bits set in the first pile and k bits set in the pile, i.e. bit count for these piles is (29-k) and k. what we want same bit count on both sides or consider we want precisely k on both sides because we dont know 'k'. :D
you can observe that if you flip (n-k) bits then you get k bits
Ex: if 3 out of 5 bits are 1's then the flipping all would give you 2 1's
so flip all in the first pile and you're done