Stuff in a Cup, A Logic Interview Question

Okay, so the interviewer didn't prompt me with "stuff in a cup." I'm certain it was marbles, pebbles, or maybe it was coins. Anyhoo, the question was:

What's the fastest way to determine which cup has the heavier stuff?

  • There are 9 cups
  • 8 of the cups have coins that weight exactly 1.0 grams each
  • 1 cup has coins that weight 1.1 grams each
  • Each cup has an infinite number of items
  • Using a scale to weigh an item counts as a move

The key word in this probably "fastest," as in how can we find the answer in as little moves as possible. My first, and naive, attempt was:
First survey half of the population by collecting an item from the first 4 cups. Weigh all 4 of the elements and if the sum contains (.1) then take a item from half, or 2, of the cups from this group. On the other hand, if (.1) does not exist in the set, gather items from the other half. Eventually, using a logarithm algorithm like this you'll find the answer without weighing an item from each cup.
Obviously there's a better way. I found out that you can write an algorithm to solve this in O(1), or simply a constant, move. This slightly better approach is:
Pull 1 item from the first cup. Then pull 2 items from the second cup... ...and finally pull 9 items from the ninth cup. Combine all of the items and weigh them all together. By looking at the sum you can determine which cup contained the (1.1) element because the possible sums will range from (45.1 to 45.9). If the sum is (45.6) then you can assume that the (1.1) item came from the 6th cup.
Unfortunately, there's more! What if the cups contained items that had the following weights:
cup 1: 1.3 g
cup 2: 8.2 g
cup 3: 1.9 g
cup 8: 2.2 g
cup 9: x.y g
How would you find the cup that has the weight of x.y in O(1), using a single weighing? This gets a little trickier but it's possible. The previous solution will not work because the sum would be much more dynamic. The correct way to solve this is:
Pull 10 items from cup 1
Pull 1000 items from cup 2
Pull 100000 items from cup 3
Pull 10 ^ (15) items from cup 8
Pull 10 ^ (17) items from cup 9
Pull 10 ^ (n*2 - 1) items from cup n
And weigh all of the items together in one fell swoop. The sum will be a very large number, but in a single move we'll find our answer. It might look like: xy22[...]198213

Then by looking at each pair of numbers, you can determine which cup a particular pair of numbers came from. (xy) came from the 9th and (19) came from the 3rd cup.

If the weights of the items changed from tenths to hundredths or thousandths then use 100 ^ (n*2-1) or 1000 ^ (n*21) accordingly.

  1. gravatar

    # by Anonymous - July 22, 2009 at 7:23 PM

    Were you able to come up with that solution? It seems pretty difficult to come up with on the spot.