Google Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
5
of 7 vote

well , I seemed to read this kind of a puzzle once, and liked the solution which they gave...
representation 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 .....

- Abhik November 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

well this can also be modified to 3 rats if the counting goes from 0 to 7 .....

- abhik November 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nandakarsan December 01, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

gr8 result. but yeah only 3 rats will suffice...

- Anonymous June 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- mytestaccount2 July 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

youtube com/watch?v=PqbcO-PijCc

- rasmiranjanbabu February 16, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Rayden November 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Rayden November 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hmm. how?

- blueskin.neo November 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Assign a bottle to each subset.

- Rayden November 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- blueskin.neo November 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Rayden and blueskin: Probably you didn't notice, we need to do this in N time

- Sem April 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- blueskin.neo November 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

.......

- blueskin.neo November 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ritz November 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

My Bad..did not see that we have to do it in Time T! This will not work!

- Ritz November 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- nitin November 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Asrar December 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Meenal Devpura December 28, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes, but the question is to solve it in time T, not 2T. So you need 7 rats.

- mikmik December 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

its 7 ....

- prasthsarath December 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Meenal Devpura December 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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!

- Maryam January 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about the time T constraint?

- mal January 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think if we can mix the samples from different bottles we can achieve the result in time T with the solution given by Maryam.

- ankit February 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- CH February 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

enuff of rat killings.:P

3 rats.

- PETA March 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

0 rat - use other animal

- rainth November 25, 2011 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book on 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