It’s Friday, and time again for a new Fragment: my weekly programming-related puzzle.
This Week’s Fragment
This week’s fragment follows the same line as last week; that is, it’s a simple puzzle sometimes given as an interview question for programming and engineering jobs. I once worked at a company that used this one. Such puzzles are usually very poor predictors of job performance, but they’re interesting nonetheless. So here goes…
You have eight balls; seven weigh the same, but one is lighter than the others. Using a balance, how can you find the “oddball” in only two weighings?
If you want to “play along”, post the solution as a comment or send it via email. To avoid “spoilers”, simply don’t expand comments for this post. It should be a ball.
Last Week’s Fragment – Solution
Last week’s fragment was borrowed from a recent Car Talk episode. A listener there wrote how he didn’t get a programming job partly because he failed to solve the following interview puzzle within the allotted five minutes:
You have a four ounce glass, a nine ounce glass and an unlimited supply of water, which can be poured and dumped as much as needed. Can you measure exactly six ounces of water in as few steps as possible?
Kudos to both Spencer and Luke for solving this one quickly (within the five minutes) by just talking through it. It can be done in eight steps, and the key is recognizing that the six ounces clearly must end up in the nine-ounce glass. So you have to work toward pouring exactly three ounces out of that glass. Get one ounce in the four-ounce glass and you have your three-ounce destination. Here are the steps.
- Fill the nine-ounce glass.
- Fill the four-ounce glass from the nine-ounce glass. That leaves five ounces in the niner.
- Dump the four-ounce glass.
- Fill the four-ounce glass again from the nine-ounce glass. That leaves one ounce in the nine-ounce glass.
- Again dump the four-ounce glass.
- Pour that one ounce from the nine-ounce glass into the four-ounce glass.
- Fill the nine-ounce glass again.
- Fill the four-ounce glass from the nine-ounce glass. You will have poured off three ounces leaving six ounces. Voila!
Weigh three balls against another three balls. If they weigh the same, you simply weigh the other two to find the lighter one. If one set of three balls was lighter than the other though, weigh two of the balls in the lighter set of three against each other. If one is lighter, that’s it, else it’s the third one you didn’t weigh the second time.
Wow, I was the only commenter? I suspect that means you have some very smart readers who respond only to the harder problems…