Microsoft Interview Question
Software Engineer / DevelopersTrial and error might take a while since the number of ways to weigh the coins is large.
You need to find the rules that the coins on the scale must observe in order to determine the fake coin uniquely. The rules will reduce the number of possible ways and they will even help construct the solution.
Let's code the result of each weighing by L,E or R (left side down, equal, right side down, respectively).
Analysis determines the following:
(1) Each coin must be put on the scale at least once
(2) For the coins C1 and C2: C1 and C2 cannot appear only together on one side of the scale or on both sides of the scale
(3) Each side has the same number of coins and the number is lower than 6
Further analysis determines that from the set of all 27 possible outcomes (LLL, LEL, LRE, etc) EEE is not valid and the set of needed 24 outcomes (12 coins, each being either lighter or heavier) contains the same enumber of Es, Ls and Rs. From that we know that each weighing has exactly four coins on each side.
We also see that 3 coins will appear 3 times, 6 coins will apear twice and 3 coins will appear only once.
Knowing all that takes only a minute to construct a solution.
#1: Divide into 3 bins, A, B, C. Compare A and B.
IF[ 4A == 4B ] #1
{
A and B are Good, 8G
Take 3 from each G and C
IF[ 3G == 3C ] #2
{
Take remaining C
IF[ G < C ] C is Heavy #3
ELSE C is Light
}
ELSE IF[ 3G < 3C ] #2
{
Take 1 EACH from C
IF[ C1 == C2 ] C3 is Heavy #3
ELSE IF[ C1 < C2 ] C2 is Heavy
ELSE C1 is Heavy
}
ELSE IF[ 3G > 3C ] #2
{
Take 1 EACH from C
IF[ C1 == C2 ] C3 is Light #3
ELSE IF[ C1 < C2 ] C2 is Light
ELSE C1 is Light
}
}
IF[ 4A < 4B ] #1
{
Rest 4 are Good, 4G
IF[ A1 + B2 + G < A2 + A3 + B1 ] #2
{
IF[ A1 < G ] A1 is Light #3
ELSE B1 is Heavy #3
}
ELSE IF[ A1 + B2 + G == A2 + A3 + B1 ] #2
{
IF[ B3 == B4 ] A4 is Light #3
ELSE IF[ B3 < B4 ] B4 is Heavy
ELSE B3 is Heavy
}
ELSE IF[ A1 + B2 + G > A2 + A3 + B1 ] #2
{
IF[ A2 == A3 ] B2 is Heavy #3
ELSE IF [ A2 < A3 ] A2 is Light
ELSE A3 is Light
}
}
IF[ 4A > 4B ] #1 same as less than condition
Your solution doesn't meet the constraint of the puzzle ("the real kicker") that you should do your three weightings first and deduce later.
I'm not sure if there is a solution, though. In theory three weightings provide 27 possible outcomes and the solution space has 24 elements, so there is a chance it's possible but I'm pessimistic.
@arrogantpiyush - is part of the puzzle potentially proving there is no solution?
3 chances are needed, Split 12 coins to 3 groups , a,b,c;
weigh a & b
{
if(a==b)----->first chance
then split c in 2 coins per side, ---->2nd chance
now if(right side weighs more, take those 2 coins out and place any 2 coins from a or b(because they weigh same))
if (they weigh same)
then the counterfeit coin weighs more than all other coins
then place the 2 coins which we took previously from the end of 2nd chance---->3rd chance
now which ever weighs more that coin is the counterfeit coin that weighs more
}
Note:
If the counterfeit coin weighs lesser then the 2nd round's result wud be different.
The above steps are one possible way of the outcome, but whatever way you do, this algorithm will work fine I guess :)
Sequence of weights...
weight1 : 1,2,3 <compare> 4,5,6
weight2 : 7,8,9 <compare> 10,11,12
weight3 : 2,4,7,11 <compare> 1,5,10,8
Example 1:
1,2,3 <compare> 4,5,6 --> equal
7,8,9 <compare> 10,11,12 --> left tilt
2,4,7,11 <compare> 1,5,10,8 --> equal
Ans: 9 is the heaviest (Because out of 7,8,9 only 9 did not participate in 3rd comparison)
Example 2:
1,2,3 <compare> 4,5,6 --> left tilt
7,8,9 <compare> 10,11,12 --> equal
2,4,7,11 <compare> 1,5,10,8 --> left tilt
Ans: coin 5 is the lightest (Beacause only 5 is the common number in first and third comparison's tilt side)
Divide them into three groups of 4 each
Round1: Weigh 4 of them. If left tilt====> counterfiet is there in this 8 balls
Round2: Divide the remaining 8 as 3,3,2 and put 3,3 in the pan. If left tilt===> the counterfiet group of 3 balls is found.
Round 3: Out of 3 balls, put 2 balls in the pan with 3rd one being outside. If left tilt, the defective ball is found. If the pan is balanced, the defective one is outside.
Answer will come in 4 passes. Here we don't know counterfeit coin has less or more weight.
Divide the total coin in three sets.
A-4, B-4 and C-4
First weight Set A and B
If A and B are having weight equal then the counterfeit coin in set C
otherwise the counterfeit coin in set A Or B.
so in this case B will be either up or down on the weighing machine.
Now weigh A and C, so possibility is either they are equal only or C will be either up or down like B.
If weight of set A and C are equal, then B will have counterfeit coin
otherwise set A will have the counterfeit coin
Similarly for rest other sets.........
The correct frame of reference to evaluate this problem is the entropy. See
slidesha.re/LsdTDf
, starting around slide 16. Such problems should be solved when they are laid out, not iteratively step-by-step. In this case the coins aren't divided into three piles of four, but rather four piles of three that are then sifted in changing groups of four onto the the two sides of the scale. At each step you learn something about each of the four piles and by the end the three trials add up to a solution of whichever coin it was.
- Anonymous August 29, 2009