## Microsoft Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````1 2 3 4 | 5 6 7 8   1 2 3 5 | 4 9 10 11   1 4 6 9 | 2 7 10 12
-----------------   -------------------   -------------------

RRR -> 1 L   LEL -> 7 L
LLL -> 1 H   RER -> 7 H
RRL -> 2 L   LEE -> 8 L
LLR -> 2 H   REE -> 8 H
RRE -> 3 L   ELR -> 9 L
LLE -> 3 H   ERL -> 9 H
RLR -> 4 L   ELL ->10 L
LRL -> 4 H   ERR ->10 H
LRE -> 5 L   ELE ->11 L
RLE -> 5 H   ERE ->11 H
LER -> 6 L   EEL ->12 L
REL -> 6 H   EER ->12 H

RRR -> 1 L means the right side of the scale down three times determining that coin
1 is lighter.``````

Comment hidden because of low score. Click to expand.
0

How did you reach at this solution? Trial n error?

Comment hidden because of low score. Click to expand.
0

sexy soln and logic...

Comment hidden because of low score. Click to expand.
0

Beautiful

Comment hidden because of low score. Click to expand.
1
of 1 vote

Trial 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.

Comment hidden because of low score. Click to expand.
0

can sm1 pls elaborate on the soln.,its not self explanatory

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

There is a solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 :)

Comment hidden because of low score. Click to expand.
0

Nope, in the first weigh if a>b or a<b it would need more than 3 weighs to determine.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

Nope.

Try: left, equal, equal. Either 3 is heavier or 6 is lighter. Similar for: right, equal, equal.

Every time you weigh you have to use 4 coins on each side, otherwise you'll lose some information that you need to cover every possible outcome.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

No, not the solution. Question didn't tell counterfit ball wighs more. It could weight less and solution need also to find if counterfit weighs more or less.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1, 4, 6, 10 vs 5, 7, 9, 12
2, 4, 5, 11 vs 6, 7, 8, 10
3, 5, 6, 12 vs 4, 8, 9, 11

Comment hidden because of low score. Click to expand.
0
of 0 vote

Since these are 3 possible states during weighing ( L,R,E) ...think in terms of base 3....there are 12 coins...and counterfeited coin can be heavy or light....so we need to distinguish between 24 states and we have 3*3*3=27 states.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.........

Comment hidden because of low score. Click to expand.
0
of 0 vote

mathsisfun.com/pool_balls_solution.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

mathsisfun.com/pool_balls_solution.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````please check below for explanation
mathsisfun.com/pool_balls_solution.html``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.