Google Interview Question
Software Engineer / DevelopersI think you are correct 3 rats are enough to determine the poison bottle.If no rats died at T time then 8th bottle has poison.
Use 3 rats
R1 drinks all bottles with right most bit turned on.
R2 drinks all bottles with 2nd bit turned on
R3 drinks all bottles with MSB turned on
7 1 1 1 R3, R2, R1
6 1 1 0 R3, R2,
5 1 0 1 R3, , R1
4 1 0 0 R3, ,
3 0 1 1 , R2, R1
2 0 1 0 , R2,
1 0 0 1 , , R1
0 0 0 0
Now if Bottles 1-7 contain poison, then the killing of rats combination will tell us the answer.
And If no rat gets killed, Bottle 0 has the poison.
I am assuming that we can mix up samples from bottles numbered from 1 to 8. I will simply leave 8th bottle out so if none of the rats die the 8th is poison. Rats are enumerated using letters.
a - Samples from 1,2,3,4
b - Samples from 2,3,4,5
c - Samples from 3,4,5,6
d - Samples from 4,5,6,7
If 1 is the poison only a will die. If it is 2, only a and b will die. If it is 3, a-b-c should die. If it is 4 a-b-c-d will die. If it is 5 b-c-d will die. 6 means c-d will die. And finally 7 means d will die.
So my answer is 4 rats.
Well it should actually be 3 rats.
You can identify bottles uniquely as with a set containing 3 rats you can identify each bottle using its subsets.
gotcha! power set of 3 rats:
{}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}
ignoring the first one we have 7.
if none die then bottle 8.
A different perspective:
How many bits are required to store 1:n-1 numbers?
log2(n) bits required to store n-1 elements.
thanks Rayden
//feed 4 rats with the following bottles
Rat1 1 4 6 7 8
Rat2 2 5 6 7
Rat3 3 4 5 6 8
Rat4 7 8
The sum of the rat numbers is the bottle number. For example, 6 is poison then rats 1,2,3 will die. 1+2+3 = 6
We need 4 four rats upto 10 bottles because 1+2+3+4 = 10. and we can make arrangement of numbers as above
3 Rats
Rat1 drinks 1,2,3,4
Rat2 drinks 5,6,7,8
The Rat that did not die, lets say Rat2, so poison in bottle 1,2,3,4
Rat2 drinks 1,2
Rat3 drinks 3,4
One will survive, lets say Rat3, so poison in either 1 or 2.
Rat3 drinks from 1. If he survives 2 is with poison, if not 3 is poison
Only 3 rats
Consider each rat as one bit.
So,
Represent each bottle in binary and let each rat drink whose rat number bit is set.
Rat1 Rat2 Rat3
1(001) 2(010) 4(100)
3(011) 3(011) 5(110)
5(101) 6(110) 6(110)
7(111) 7(111) 7(111)
So whichever rat is dead made the bottle number by setting the bit defined by that rat number.
So if rat 3 and rat 2 dies than set 2 and third bit as set and the bottle would be 6.
I think 3 rats & 2 turns/attempts are required to find poison bottle
Let T= time to find whether rat dies after drinking bottle
Steps:
1) We give 3 bottles to R1, and 3 different bottles to R2
Possible outcome 1:
if no one dies then it means, poison bottle is among the remaining two (T1)
we give 1st bottle to R1, 2nd bottle to R2 (if 1st bottle is poisonous R1 dies, otherwise 2nd bottle) (T2)
so 2 rats and 2 attempts required
Possible outcome 2:
Poisonous bottle is among the six given to R1 & R2
Lets say its in the 3 given to R1 and it dies (T)
So, discard the 3 given to R2 and 2 unused
Give 1 bottle to R2 and 1 bottle to R3
Poison bottle determined if either of them dies or no one dies (2T)
So, Total Rats =3, Total Attempts =2T
We need 3 Rats and 1T to find out poisonous bottle.
Prove :- We have 3 rats names R1 , R2 , R3 and 8 bottles names B1,B2,B3,B4,B5,B6,B7,B8.
Now feed
R1 => B1+B4+B5+B7
R2 => B2+B4+B6+B7
R3 => B3+B5+B6+B7
In this we have some similarities.
If only R1 dies means B1 have poison same if only R2 then B2 etc. If R1+R2 dies not R3 then we have common bottle B4 means B4 have poison.If R1+R2+R3 dies then B7 have poison and if no rates died then B8 has poison.
This theorem only works if there is surety that one bottle contain poison ... btw its given in qn. :-)
We need 3 Rats and 1T to find out poisonous bottle.
Prove :- We have 3 rats names R1 , R2 , R3 and 8 bottles names B1,B2,B3,B4,B5,B6,B7,B8.
Now feed
R1 => B1+B4+B5+B7
R2 => B2+B4+B6+B7
R3 => B3+B5+B6+B7
In this we have some similarities.
If only R1 dies means B1 have poison same if only R2 then B2 etc. If R1+R2 dies not R3 then we have common bottle B4 means B4 have poison.If R1+R2+R3 dies then B7 have poison and if no rates died then B8 has poison.
This theorem only works if there is surety that one bottle contain poison ... btw its given in qn. :-)
3 rats are required:
binary representation of 8 bottles with 3 bits:
1- 0 0 1
2- 0 1 0
3- 0 1 1
4- 1 0 0
5- 1 0 1
6- 1 1 0
7 - 1 1 1
8 - 0 0 0 (bottle 8 is out)
So:
Rat 1 : samples from 4, 5, 6, 7
Rat 2: samples from 2,3,6,7
Rat 3: samples from 1, 3, 5, 7
Then according to which rats with die, we can determine the bottle of poison.
As an example, if rat 2 survives but not rat 1 and rat 3 -> (1 0 1) -> bottle 5 is poison!
3 rats are required yea. An intuitive way to look at it is to use a Venn Diagram. With 3 circles, one representing each rat, we see that there are 8 sections, each of which can contain a bottle number (including the set outside all 3 circles). That is, one bottle in circle 1 only, one in circle 1 intersection circle 2, one in the intersection of the 3 circles, etc. The information you get at time T (one rat dead, two rats dead, three rats dead, or no rats dead) will tell you which bottle contained the poison.
well , I seemed to read this kind of a puzzle once, and liked the solution which they gave...
- Abhik November 30, 2010representation in binary numbers
1-0001
2-0010
3-0011
4-0100
5-0101
6-0110
7-0111
8-1000
so , now if we take 4 rats , and suppose 0 represents that the rat does not drink from that bottle and 1 means the rat drinks from that bottle.
so solution 1 is fed to the 4th rat only , solutin 2 is fed only to the 3rd rat , soln 3 is fed to the 3rd and 4th rat .. so on , at the end , we can make out which one has poison , seeing which rat dies/rats die .....