Yahoo Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Well the binary approach is best to solve such kind of problems. Suppose you have 1000 wine bottles so you require 10 rats to test these bottles for poison (as 2^10 = 1024, with 10 rats you can check as many as 1023 bottles) and voila we are given exactly 10 rats. So just in 1 trial we can detect all the poisonous bottles. The trick is assign each rat a position. For example rat 1 will be at position 0, rat 2 will be at position 1 and so on....Let us take a shorter case in which number of bottles are only 3 since 2^1 < 3 < 2^2, we require at least 2 rats to check which of the bottles are poisonous...
Start moving from bottle 1. 1 can be represented in binary as 1 only so the rat at position 0 will take a sip from that bottle. Now 2 is represented as 10 in binary, so the rat at the position 1 will take a sip from that bottle. Now 3 is represented as 11 in binary so rats at position 0 as well as position 1 will take a sip from that bottle. Now if rat at position 1 dies it means bottle 2 was poisonous, if rat at position 0 dies it means bottle 1 was poisonous and if both rat dies it means bottle 3 was poisonous.
There is a easy solution for this. Mix wine from 100 bottles to 1. So, there will be 10 bottles. If one rate die from any of the 10 bottles, the poison is in that 100 bottles. Then make another 10 bottles of win from 100 bottles. That means each bottle contains sample from 10 bottles. Now, one rat should die. Then you know which 10 bottle contains the poison one. Next step is make 5 bottles each contains 2 sample. Next step is easy. So, at most 4 rat will die to find out which one is poisoned.
Construct a tree binary tree considering of 1024 bottles... at lowest level we have 1 bottles.. now if we need to find only a single bottle that is poisoned we can do it in 10 tries i.e height of tree. drinks 512th bottle...256th bottle.. and so on.. just like divide and conquer... so it will min 10 chances...
I thinks its like standard coupon collector problem / balls n bins problem.
How many tosses one should to so that all n bins contains one ball each?
= n log n
Ball - Wine bottles
Bins - Rats
Event - Ball falls in bin - Rat Dies.
So Answer = 10 log 10
The above puzzle of 1000 wine battles with 10 poisoned cannot be solved with just 10 rats. It requires a minimum of 2 rats and a maximum of 30 rats to figure out which of the bottles are poisoned. Using Towhid's answer as the base, let us split the 1000 bottles into 10 sets of 100 bottles. Assign 1 rat for each of the sets and make it taste a mixture of the 100 bottles of its set.
Scenario 1: Best case scenario - Only 1 rat dies showing that all the 10 bottles are in the same set. Now split these 100 bottles into sets of 10. again follow the drill of assign 1 rat per set and testing. Best case scenario only 1 rat dies meaning all 10 bottles of that set are poisoned. Thus the result. Worst case senario in this will be that all 10 rats die. meaning there is exactly one bottle in each of the sets that is poisoned. find the individual bottles that are poisoned by giving each rat 1 bottle's sip. For each of the set of 10, only 1 rat will die, the remaining will survive. Which means a total of 10 rats will die again. Leading the death toll of rats to 21.
Scenario 2.0: Worst case scenario: all the 10 rats die. Meaning that each of the sets of 100 have exactly one poisoned bottle. Now the same analysis as in the above steps follows. Leading to a maximum of 20 more rats dying ( 1 for each set of 10 within a set of 100. and then 1 for a bottle in the set of 10) which makes the total number of dead rats= 30.
All the other scenarios fall between these two scenarios.
Hence, the least number of rats that will die= 2 (given at least 11 rats) and the maximum number of rats that will die= 30 ( given 30 rats).
Please let me know if there is any flaw in this solution. ( except the change in the number of rats in the question instead of the number of poisoned bottles :p ).
Its quite simple if i get the right question:
As 2^10=1000(nearly)
So consider the combination in form of 0 and 1.
Let me explain u in better way.
Consider there are 8 wine bottles out of which 3 are poisoned and there are 3 rats there.Each rat dies after drinking wine from one botlle after 24 hour and exactly 24 later party starts at your home.
so :
R1 R2 R3
w0 0 0 0
w1 0 0 1
w2 0 1 0
ans so on.. til 7 that is binary combination of first 8 digits.
and here 0 means that rat does not drink and 1 means that it drinks.. so R1,R2,R3 are rats w1,w2,w3,....w7 are wine bottles..... After 24 hours u can see which rat dies and thus can recognize.. lets say r2 died so poison is in w2,w3,w6,w7 and r3 do not die so poison is w2 and w6,now if r1 dies poison is in w6 else in w2.Bottle w0 is considered always poisonous as not drank by any rat.Similarly u can do with this 1000 one.:)
@Hector consider a case when all three rats will die...
case w3 and w4 is poisonous....
And how can u decide upon w0???
I think this is similar to binary representation of an integer. 3 rats can be 3 digits, which can represent 0-8. However, this solution can only be used when there is only one bottle that is poisoned because 3 rats can only exclusively represent 1 integer.
Asked to me by a recruiter for ADOBE,1 and 1/2year earlier,now that guy is in yahoo.
I think the same guy took ur interview.
Divide 1000 into 2 sections. 500 and 500 bottles. Mix a drop of wine from all the wines from each section. 1st rat drink one section. If it dies then the poison will be in that section and if it doesnt die it will be in the other section. Repeat the same till u reach 2 bottles. It will be 9 tries till to reach there.
Best case scenario is 1 where all 10 rats drinks poisoned wine and die.
- Avijeet May 29, 2012But the worst case scenario will be when 9 rats die because of drinking first 10 wine bottles of stack and now we are left of only 1 rat to check next 990 wine bottles. So it'll take 989[worst case] tries, which makes worst scenario as 990 tries.