Interview Question
Country: United States
Depends on how long the poison takes to act and how long you have to perform the test. Worst case, four rats, best case one rat.
If time is at least 3x the acting time of the poison, one rat.
If time is less than 2x the acting time of the poison, four rats.
Between 2x and 3x, two rats.
Latency matters.
lets assume
1 rats are to be fed once and at the same time and we know how fast the poison acts, then the following would be optimal
feed rat1 with milk1 and milk2
feed rat2 with milk2 and milk3
wait for the time the poison should act
if only rat1 dies milk1 has poison
if both rat1 and rat2 die then milk2 has poison
if only rat2 dies then milk3 has poison
if no rats die then milk4 has poison
This problem should be solved using binary representation.
- Sameer October 30, 2018Lest assume the poison takes 2 hours to affect, the solution of 1 rat is not feasible as we will have to wait to lot of time to determine which bottle is poisoned. The simple solution is by using binary representation lets assume bottle 3rd is poisoned.
Step 1) represent all the bottles using binary representations.
Bottle 1 : 0001
Bottle 2 : 0010
Bottle 3 : 0011 (Poisoned)
Bottle 4 : 0100
Step 2) Arrange all the rats in a line.
Step 3) according to the bottles binary representation git a drop of wine to the rats for digit 1.
Rat1 Rat2 Rat3 Rat4
- - - -
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
Now according to our assumption all the rats which were given a drop from bottle 3 Should die. which would be rat 3 and rat 4.
Assume the red rats to be 1's and alive rats to be 0's which comes out to (0011) which is exactly the number of our bottle.
This approach kills 2 Rats. There's no where mentioned that we should try to keep as many rats alive possible.