Bloomberg L.P. Interview Question: Given 10 cups to locate the b... | Glassdoor

## Interview Question

Financial Software Developer Interview New York, NY

# Given 10 cups to locate the bottle poisoned wine from a

batch of normal ones, you can make any mixture of them and test your mixtures by mouses. However the density of poison in the mixture, the testing mouse will certainly die. And you must give all the mixtures of the 10 cups before the test. There is only one poisoned bottle. How many bottles of wine you can test at most?
Tags:
brain teaser, data structure

6

2^10
You judge from the result of test. There is 2^10 kinds of possible conditions and each of them leads to a different result. So you can tell from 2^10 bottles.
1. label all the 2^10 bottle from 0-1023 in binary numbers.
2. for each numbers, if any of the figures is 1, then mix this bottle into the corresponding cup. Like bottle 0000100101(2) =37(10) , figures in place 6, 3 and 1 are "1", so mix this bottle of wine into cup 1, 3, & 6.

If and only if the mouses of cup 1, 3 and 6 die, the poisoned bottle will be 37.

Interview Candidate on Dec 8, 2012
4

I solved it a different way, but got the same answer -> 2^10. Start with base cases and work up.

1. If you have one glass, can have at most two bottles
one poison, one not (if mouse dies, the bottle is poisoned. if mouse doesn't die, it's not poisoned and the untested one is)

2. Two glasses, four bottles
one bottle untouched, one bottle in glass 1, one bottle in glass 2, one bottle in glasses 1 & 2. (similar idea: if no mice die, first bottle is poisoned. if mouse 1 dies, second bottle is poisoned. if mouse 2 dies, third bottle is poisoned. if both mice die, fourth bottle is poisoned)

3. 3 glasses, 8 bottles distributed as follows:
- 1 bottle untouched
- 1 bottle in glass 1
- 1 bottle in glass 2
- 1 bottle in glass 3
- 1 bottle in glasses 1 & 2
- 1 bottle in glasses 2 & 3
- 1 bottle in glasses 1 & 3
- 1 bottle in glasses 1, 2, & 3

4....

All the way up to 10 glasses

Candidate on Dec 11, 2012
3

seems a bit garbled.

just put wine from one bottle in one cup, and give it to the mouse. if he dies, you are done. if he lives, add wine from a second bottle and give it to the mouse. repeat until the mouse is dead. the last bottle you opened is the poisoned one.

hard to believe the question was actually worded that way.

blair on Dec 11, 2012
0

I also came with the same answer in a different way.

if n bottles, then make mixture of n/2 bottles and test, you would know which half the poisoned bottle belongs to.
Next take n/4 and n/8 and so on.

so log2(n) = 10 , n = 2^10

sashi on Oct 15, 2013
1

Notice that "you must give all the mixtures of the 10 cups before the test.", so you cannot test them one bottle by one bottle or half of bottles in one time

wubi on Jan 7, 2014