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.

- Anonymous August 29, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- temp October 06, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sexy soln and logic...

- Anonymous October 30, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Beautiful

- kc November 10, 2009 | Flag
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.

- espresso April 13, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- newbie June 05, 2010 | Flag
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

- Deepak Agarwal August 24, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- espresso August 26, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is a solution.

- LOLer August 27, 2009 | Flag
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 :)

- anonymous September 03, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- rana May 29, 2010 | Flag
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)

- Sudhakar September 10, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- espresso September 17, 2009 | Flag
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.

- Anonymous October 02, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- rana May 29, 2010 | Flag
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

- Jim August 03, 2010 | Flag Reply
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.

- ulquiorra September 15, 2010 | Flag Reply
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.........

- Anybody March 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

please check below for explaination
mathsisfun.com/pool_balls_solution.html

- googlybhai February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- googlybhai February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- googlybhai February 18, 2012 | Flag Reply
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.

- Rob Seaman July 05, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More