Find the odd ball among eight balls

Amin A.

Scene 2 of Divide and Conquer, Search and Sorting Algorithms in Core Technical Interview Questions for Software Engineers

By Amin Ariana — January 2014

You are given eight balls that look exactly the same, and a balance to weigh them against each other. Find the odd ball by weighing only twice?


Contents


  1. Problem Statement

  2. Evaluation


  3. Solution

    1. Hint 1

    2. Hint 2

    3. Hint 3



  4. References



Problem Statement

The very nice people at the awesome company interview take you to the courtroom where there are eight basketballs that look exactly identical. There's a balance there (a balance is an analog scale that tells you if two objects weight the same. See Lady Justice .)

One of the balls is odd in that it's filled with a slightly heavier gas than regular air.

Getting to an actual interview depends on passing this screening test, in which they've asked you to find the odd ball without using the balance more than twice.

Go!


Evaluation

Get it right without hints (100%)


Solution


Hint 1

If the question seems wrong, it's often because your solution is wrong.


Hint 2

How often have I said to you that when you have eliminated the impossible, whatever remains, however improbable, must be the truth?
Sherlock Holmes


Hint 3

What if there were 6 balls?


References

Microsoft recruiter screening question back in the old days

Amin A.

Written by

Amin Ariana

A software entrepreneur from San Francisco