MAQ Interview Question
AssociatesCountry: India
Interview Type: Phone Interview
If there is no bound on time then one person is sufficient for identifying the poisonous bottle.
However if you need to determine the answer in exactly 60 minutes then a minimum of 2 persons are required. Label bottles as below.
Bottle1: 00
Bottle2: 01
Bottle3: 10
Bottle4: 11
No one drinks from 1st bottle. Person2 drinks from 2nd bottle. Person1 drinks from 3rd bottle. Both of them drink from 4th one.
If no one died then bottle1 is poisonous. If both died then 4th one is poisonous. If 1st died then 3rd one is poisonous. If 2nd died then 2nd bottle is poisonous.
after drinking poison bottle he will wait for 60 min to check its reaction , 2 people are required. 2 bottles person 1 will drink and person 2 will wait for reaction.... for both bottles , (binary search). if he dead in any of two , it means person 2 have to drink either first bottle or second.... in that way first half we can find... if person 1 crossed the first half, he will drink second hald ( bottle 3 or 4) , hence we can verify with 2 people.
this is same as 1000 bottles of poison puzzle
folj.com/puzzles/very-difficult-analytical-puzzles.htm
The link you posted has no leeway in terms of time, so the answer is log_2 (1000) => rounded up 10 humans needed. (Many ways to reason this)
The problem this fellow posted has degree of freedom in terms of time, so we can compress all the secret information onto one human and let the information seep out sequentially and visibly on the other side of 60 min.
This problem is not concern with minimizing the time to find the poisonous bottles but the number of casualty. This number varies between 1 and 2 persons, depending on how the result of the first round may turn out.
two persons:
1. Divide the bottles into groups of twos i.e., {1,2} and {3,4}.
2. Person one drinks from bottles 1 & 2. If he dies then we don't need to examine bottles 3 & 4.
3. Person two drinks from 1 or 2. If he dies the bottle of his choice the poisonous bottle.
Case 2: Do steps 1 and 2 above. Now, if this person doesn't die, then the poisonous is among bottles 3 and 4. So, choose either of these two to find the poisonous bottle.
On a side note, this is an example of geometric distribution. That is how many Bernoouli trials before a success which in case is nothing but finding the poisonous bottle. Therefore, the expected number of people i.e., trials is E[X]=1/p where p=1/n with n=number of bottles.
Why not shrink your idea to 1 person who takes the bottles in some predefined order at time intervals of 10 min. (or any < 15 min.) ?
- Urik's twin Cookie Monster (dead now) October 31, 2013