## Yahoo Interview Question

Software Engineer / Developers**Country:**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

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.