Yahoo Interview Question Software Engineer / Developers


Country: India
Interview Type: In-Person


Comment hidden because of low score. Click to expand.
2
of 8 vote

Best case scenario is 1 where all 10 rats drinks poisoned wine and die.
But 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.

- Avijeet on May 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I thought of the same idea. Just that giving the details of how is 'try' defined by the question poster (or interviewer) would have given better confidence. Thanks!

- Dilbert Einstein on April 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

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.

- Spock on July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The questions says that 10 wine bottles are poisoned, all the answers being discussed are making the assumption that 1 bottle is poisoned.

- nish on August 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@jason, what 3 digits can only exclusively represent 1 integer!!!! so we have only 1 ,3digit integer- 100,110,101- they r all 3 digits and different....

- coder on July 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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...

- codemonkey on October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Towhid on February 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

awesome answer bro

- Bharath on October 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Someone on June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Explain How do u solve the problem if u know

- Coder on September 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

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 on May 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Hector consider a case when all three rats will die...
case w3 and w4 is poisonous....

And how can u decide upon w0???

- Priyesh on May 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Jason on May 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Jason, It should be 0-7 or 1-8

- Mohit on June 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Hector on May 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Hector where are u now??

- Gaurav on May 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Harsha Jayaramachar on March 17, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More