Amazon Interview Question Software Engineer / Developers
mix water from 6 buckets and leave one bucket alone. put 1 fly in any one of the mixed 6 buckets. If it it dies then send the 7th bucket else send any of the first 6 buckets.
can anybody pls explain the question itself i cant even understand the question leave aside the solution
try this way:
Day 1: fly in bucket 1
Day 2: take the fly from bucket 1 to bucket 2
Day 3: take the fly from bucket 2 to bucket 3
...
Day 7: keep the fly there
if the fly die, then we know bucket 1 is poisoned, we can give any other buckets to your friend. Otherwise, send the bucket 1, since it is non-poisoned. Then you wait for the Day 8 to see if fly dies, then you will see the bucket 2 ... and on and on....
I guess I understand what hary said.
1. Number the 7 buckets as 1, 2, 3... 7.
2. Write each number in binary, 001, 010, ..., 111
3. Need 3 additional buckets, each corresponds to one bit in step2.
4. For each of the 7 buckets, put its water in the each of the 3 additional buckets if its corresponding bit is 1.
5. Put one fly to each of the 3 additional bucket
6. After 1 week, for each bucket, write down '1' if its fly is dead, write down '0' ow. Together, you know which one in the 7 buckets is positioned.
You don't need extra buckets.
Label each bucket 001 to 111 in binary.
Assign each of three flies a bit position (0, 1, 2).
Dip each fly in every bucket where his bit is set (e.g. fly-0 goes in every odd bucket).
Using dead flies as 1 and live flies as 0, write a binary number.
That's the poisoned bucket.
how many flies does ur approach take?
We need to reduce flies! twinba's soln. is the best!
J's solution is the right one. You do not need extra buckets. His approach uses 3 flies.
fly 1 - bit position 0
fly 2 - bit position 1
fly 3 - bit position 2
You have a fly for each position.
Buckets are numbered from 1-7, or 001-111.
Bucket 1 - dip fly 1 (bit position 0 set)
Bucket 2 - dip fly 2 (bit position 1 set)
Bucket 3 - dip flies 1 and 2 (bit positions 0 and 1 set)
...and so on
At the end of 7 days, check all three flies.
Only one will be dead, set that fly's bit position as 1.
The binary number formed gives the bucket number.
the key in this problem is that a fly does not have to remain in a poisoned bucket for 7 days to die. You only have to dip it once for it to die.
@all BTW IF WE JUST NEED TO SEND "ONE" BUCKET TO A FRIEND..AND JUST "ONE" IS POISONED WHY TO CARE FOR THE POISONED BUCKET??
jUST PUT IN ANY ONE BUCKET....IF THE FLY DIES SEND ANY OF THE OTHER TO THE FRIEND ELSE SEND THAT ONE... :)
it depends.
if the original question does not allow you to send a polluted (by a fly) bucket to your friend, then you cannot use this approach.
I think the question is wrong! Perhaps they would have said only one of them is non-poisonous and rest of them are poisoned. In such case, this 3 bucket solution works fine.
If they Q is only one poisonous bucket, then we can solve this with one additional bucket. This is to avoid sending a polluted bucket to fried :)
Take one additional bucket, and keep a drop of water from any of 7 buckets. Keep a fly in this new bucket and if the fly dies in 7 days - send any of the 6 other buckets. If the fly doesn't die, send the bucket from which the water drop is taken from.
That would allow you to send your buddy a clean bucket, but the problem was to find the poisoned one AND send your buddy a clean bucket.
Yes, J. By utscool's solution you can find a clean bucket in the first week and then send it out. And then in the following weeks to figure out which bucket is poisoned using the same fly.
I still think this one is the best answer cause it satisfy the requirement the most: find the poisoned one in 7 days and use least # of fly. ; )
Its same as "The Emperor " Problem
+folj.
+com
+ /puzzles/very-difficult-analytical-puzzles
+.htm
1 The Emperor
You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned.
The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison.
You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned.
You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed.
What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?
Its same as "The Emperor " Problem
+folj.
+com
+ /puzzles/very-difficult-analytical-puzzles
+.htm
1 The Emperor
You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned.
The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison.
You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned.
You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed.
What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?
If the goal is simply to send a non-poisoned bucked of water, then you can solve this with just 2 flies. How? Just separate the 7 buckets on 2 groups: one has 6 buckets and another just 1 bucket (presumably if you mix poisoned water with fresh water then all the water will be poisoned). You can select the buckets for each group randomly.
Then just mix the water from the 6 buckets and use a fly for each group (1 fly for the 6 bucket water and 1 fly for the solo bucket). Only one of the flies will die so you can send the water from the other group to your friend.
1 fly.
Dump out one bucket. Pour 1/3 from 3 different buckets into your empty bucket. Put the fly in there.
If the fly dies, you know the three full buckets are good.
If the fly lives, you know your three 2/3-full buckets are good. Split one of the buckets between the other two. Now you have two full buckets - one for you and one for your friend.
First, i dont know how one can make the fly die before seven days so - min days would still be 7
but yes "hw will u find out the poisoned bucket in least no of flies? " i guess the general solution is well known to everyone. (3 would be the no of flies used in normal case)
Correct me if i am missing something
hint: no your buckets using bits (one would require 3 bits in this case) and also the flies (a bit position set per fly)
I guess I understand what hary said.
- Anonymous March 11, 20101. Number the 7 buckets as 1, 2, 3... 7.
2. Write each number in binary, 001, 010, ..., 111
3. Need 3 additional buckets, each corresponds to one bit in step2.
4. For each of the 7 buckets, put its water in the each of the 3 additional buckets if its corresponding bit is 1.
5. Put one fly to each of the 3 additional bucket
6. After 1 week, for each bucket, write down '1' if its fly is dead, write down '0' ow. Together, you know which one in the 7 buckets is positioned.