Bloomberg LP Interview Question Software Engineer / Developers
A. Divide in 4 groups consisting 3,3,3 and 1 coins. Weigh 3,3. The odd coin can be in one of these groups or may not be. If the weights are not same, you get the lighter group of coins. You have narrowed down to 3 coins in 1 weigh. Now do the same with groups of 1,1,1 coins. So in 2 weighs you have the answer. If the odd coin is not in the initial 3,3 group. Then it can be in the 2 groups of 3,1 You can find the odd one in 2 more weighs at the max.
My main question with this one is whether or not you're given a balance scale (comparing A to B) or one of those newer, digital style ones where you can weigh only one thing at a time. If it's a balance scale, its easy, just split into halves and select the lightest group each time. If it's not, then I don't know.
Case B: Divide up the coins 3, 3, 3, 1. Measure two groups of 3 coins.
If the initial weights differ, then take note which group is lighter and which is heavier. Take the lighter group and measure with the remaining 3 coins. If the weights are equal, then you know the special coin is heavier and if the weights are different, the special coin is lighter. For the last weigh, just measure any two coins of the group containing the special coin to find the differing coin.
If the initial weights are equal, replace one group of 3 coins with the remaining group of 3 coins. If they now differ, the newly added group of coins contains either the heavier or lighter coin and you can just measure any two coins from this group. If all 9 coins just measured are the same, the last coin is either heavier or lighter, so just measure it with any other coin.
(A) It's a case of binary search. Randomly divide 10 coins into two groups of 5 each. Now weigh them. Group containing the oin with lesser weight will weigh less. This is one weigh. Now take that group and randomly pick any 4 coins and divide those 4 coins in two group. Again weigh them: Two cases are possible:
- Anonymous May 18, 2009[1] They will be equal, which means the remaining coin is the one which weigh less. You can get the answer in 2 weighs in total in this case.
[2] One will weigh less. Pick that group and again weigh. One of them will be the coin with lesser weigh. You can get the answer in 3 weighs in total in this case.
(B) Pick any 8 coins randomly and divide into two groups of 4 each. Two cases are possible:
[1] First, the easy one. They will weigh same. In that case, one of the two remaining coins contains the odd one. Let the two remaining coins be X1 and X2. In this case, remove 2 coins from one group and one coin from another group . Pick one randomly from X1 and X2, let it be X1, and add it to the group containing one coin. If they weigh same, X2 is the odd one out or X1. Total number of weighs is 2.
[2] If they don't weigh the same, then remove two coins randomly from the first group and 2 coins from the second group. Now, two cases may happen. Either they will weigh same or not. If they weigh same, throw them away and pick the other group of 2 coins. If they donot weigh the same, continue. Now, again remove 1 coin from each of the group. ... if the two group weighs the same, then odd one is from the two coin removed, repeat the last steps of (B)[1] . Though in this case, we are use 4 weighs.