Microsoft Interview Question


Country: United States




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

Suppose we have only 3 balls, 1 of them is heavier. This is 3-ball problem.
Then, we take 2 balls, leave 1 ball alone. Weight 2 chosen balls by a balance scale. We can easily identify which ball is heavier: one of the two chosen balls (if the scale is not balanced) or the one that left alone (if the scale is balanced).

So for 3 balls we can solve using 1 operation.

Now instead one ball, we put 3 balls into a bag. Thus, we have 3 bags, one of them is heavier. It becomes 3-bag problem. Using 1 operation we can identify which bag is heavier.
Then it reduces problem to the 3-ball problem above.

Totally, 2 operations are enough to find the heavier ball.

- ninhnnsoc February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great Solution

- liangsiyang18 February 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

seperate 9 balls to 3 groupe, each groupe contains 3 balls -> compare two groupe-> the heavier groupe contains the heaviest ball; if same weigh, third groupe contains this ball -> take two balls from the heaviest group found above, compare weigh-> same weigh than third one is the heaviest one, if not, the heavier one is the heaviest ball. VoilĂ  xD

- Kai February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

It is clear that we can find the heavier ball amongst 3 balls with only one operation(comparison).
Here is my solution:
START:Divide 9 balls to three groups of 3 randomly.
weigh two randomly selected groups against each other:
IF they are equal, THEN weigh two members of third group against each other to find the heavier one.
ELSE IF they are not equal, THEN select the heavier group and run the comparison test on it.
So the total comparison of TWO is enough.

- Meri February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

explain...

- Rao April 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

That can't be a MS interview Question!

1. Weight 3 balls against 3 balls: either one of these groups weight more or the heavy ball is in the 3rd group.
2. Out of the heavier ball group, Weight 1 ball against another: other one of them is heavier or the heavy ball is the one you didn't touch

- avico81 February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

They ask anything man.

- Anonymous March 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

with 3 operations it is simple

compare first 4 balls, next 4 balls, if weight is equal, then 9th ball is having more weight.
else , take the set of 4 balls with max weight and divide into set of 2 and compare again, take set with maximum weight, compare those 2 balls in that set, take the ball with the highest weight and return.

- abhinav neela February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is clear that we can find the heavier ball amongst 3 balls with only one operation(comparison).
Here is my solution:
START:Divide 9 balls to three groups of 3 randomly.
weigh two randomly selected groups against each other:
IF they are equal, THEN weigh two members of third group against each other to find the heavier one.
ELSE IF they are not equal, THEN select the heavier group and run the comparison test on it.

So the total comparison of TWO is enough.

- Mehrnaz February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

At best it would take 1 comparison and we have the heavier ball. At worst it would be 4 as we weigh balls against balls and either find it in the 4th one or conclude that there is one last one we did not weigh that must be the heaviest.

- Shoone March 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Pick them all up at once and feel which one is heavier.

- River March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Make a slope and leave all balls simultaneously as we do in horse racing the heaviest will r cross large distance than the rest

- suraj chothave April 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1st steo: 3 3 3
2nd step: [1 1, 1] [1 1, 1] [1 1 ,1]

- anik2137 April 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is straight from cracking the coding interview people. I hope all of you have seen that book :)

- legolas April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I will weigh 3 balls with other 3 balls & keep the rest 3 aside. If those 3 balls are equal to the other 3 balls then the heavier ball is among the rest of 3. Then I will take 2 balls from the rest of 3 and weigh them. If these 2 are equal then the remaining one is heavier or any one of them are heavier found in balancing.

- asghar khan May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

throw the balls from sufficient height,with calm wind ,heavier will reach first on the ground

- Anonymous May 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is right just like 3 bolls for first consideration.
Suppose we have 3 bolls in bag and we pick 2 boll from bag and compare their weight scale.
If weight scale is same means boll inside the bag is more weighted than other two.
3--->1--->operation
9--->3----->3---->3
3 will take rest into bag and pair 3 bolls will be outside for compare.
Therefore 2--->max operation.

- Anonymous September 03, 2015 | 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