Interview Question for Trading Analyst at Accuen:

Jul 13, 2011

There are 1000 buckets, one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within in 30 mins. What is the minimum amount of pigs you need to figure out which bucket contains the poison. 

Tags:

analytical

Add Tags [?]

See more for this Accuen Trading Analyst Interview

 Helpful Question?   

 Yes | No  Inappropriate?

Sponsored Jobs

• Business Analyst with Trading
  Modern Ballistic Solutions Pvt Ltd –Gurgaon
• Senior Analyst - Trade Finance,global Delivery Centre of MNC
  HR Folks Consulting Pvt Ltd – Mumbai

 Answers & Comments (12)

1 person found this helpful

Aug 17, 2011

by dave:

you just need one pig - it drinks a bucket, wait 30 mins, if it doesnt die, it drinks another, repeat until it dies

 Helpful Answer?   

 Yes | No  Inappropriate?

Sep 27, 2011

by Bill:

I think the question is missing "within one hour?" at the end. If that's the case then you only get two tests / trials. Start with 33 pigs each drinking from 30 buckets, then wait 30 min. If none die, then it's the leftover bucket, if one dies then get another 30 pigs to drink from the buckets that the dead pig drank from.

 Helpful Answer?   

 Yes | No  Inappropriate?

4 people found this helpful

Sep 28, 2011

by Matt:

I make it 10.

The first pig drinks from every other bucket. The second pig drinks from the first two buckets, then skips two, and so forth. The tenth pig drinks from the first 512 buckets. Wait 30 minutes. You can determine which bucket is poisoned uniquely from the pattern of porcine mortality - if all the pigs die then then first bucket is poisoned. If none of the pigs die then the last bucket is poisoned (it's a binary encoding).

You have 30 minutes to spare. You might think it possible to divide the problem up between these two halves, but since the experiment might kill all your pigs the worst case would be needing 9+9 = 18 pigs, so worse than doing it all in one shot.

 Helpful Answer?   

 Yes | No  Inappropriate?

2 people found this helpful

Oct 2, 2011

by Karoly:

Matt has the right idea with the encoding, but 1 hour gives you time for two passes. So first you divide the 1000 buckets into groups of 32 buckets each. You'll have 32 groups (the last one with only 8 buckets). The 32 groups you can binary encode with 5 digits, so 5 pigs will tell you after 30 mins which _group_ of buckets contains the poisoned one. So for the the second 30 mins you binary encode that group of 32 buckets the way Matt described.
This way you're using no more than 5 pigs at any given time. You might still kill a total of 10 in the worst case, but this approach takes advantage of the extra time to reduce the number of pigs used simultaneously. Slightly more efficient.

 Helpful Answer?   

 Yes | No  Inappropriate?

Oct 3, 2011

by Vitaly:

Matt, thank you!)
To others wondering:
third pig drinks from the first 4 buckets, skips 4 etc;
fourth one drinks from first 8, skips 8 etc;

this way if you draw a table with buckets on top and pigs on the left, and populate it with 1 for drank bucket and 0 for untouched one, each column will contain unique set of values (binary rep of 1023 to 0), as 1-1-1-1-1-1-1-1-1-1 for first one and 0-0-0-0-0-0-0-0-0-0 for last one.

Just took me a while to figure, though I'm a programmer myself).
These days you can program without even knowing binary system, let alone converting drinking swine problem to this rep.

p.s. Though 32 pigs will allow you to sacrifice 2 at max :).

 Helpful Answer?   

 Yes | No  Inappropriate?

Apr 12, 2012

by Barry:

9 pigs.

use 9 pigs to test half the buckets using Matt's binary encoding - 30 minutes.
if no pig dies (poor pigs), use the pigs again for the remaining buckets - 30 minutes.

 Helpful Answer?   

 Yes | No  Inappropriate?

Apr 13, 2012

by Ricardo:

The previous answers consider as an optimum solution using less pigs, no matter how many of them will sacrifice their lives. I will consider I can use infinite pigs so the optimum criteria is saving pigs lives.

In the solutions bellow, at most, 1 pig dies, but it is possible to get the answer without killing any of them, as I will always exclude 1 bucket.

In 30min: I need 999 pigs;
In 1h: 500 pigs (I use 500 for the 1st round; after 30min, if all of them are alive, I use 499 of them);
In 1h 30min: 333 pigs;
In 2h: 250 pigs (in the last round I only use 249 of them);
...
In 499h 30min: 1 pig.

 Helpful Answer?   

 Yes | No  Inappropriate?

Apr 16, 2012

by Bee:

The answer is one. Theoretically if the first pig finds the poisoned bucket the task is complete. Therefore the minimum number of pigs required would be one.

 Helpful Answer?   

 Yes | No  Inappropriate?

Apr 29, 2012

by Saketh:

@Ricardo: You're asked to minimize the number of pigs used, not the number of pigs that die.

@Bee: The theoretical best case for the number of pigs that die is certainly 1. However, you need a greater number of pigs to be able to complete testing within one hour.

Anyway, you can actually do this with 8 pigs if you are given one hour. First pass: split the cups into 8 groups of 125, and use 8 pigs to determine which group the target cup is in (each pig drinks from all of the cups in its assigned group).

One of these pigs will die, and you are left with a narrowed field of 125 cups. The 7 pigs you have left are sufficient to binary search on this set of cups, because 2^7 > 125. See Matt's comment above for an explanation of how the binary search works.

In the case that you are only given half an hour, I agree that 10 pigs is optimal. It's relatively easy to prove this. Each pig we use will provide us 1 bit of information. Thus, n pigs can produce 2^n different possible outcomes. Since we need to distinguish between 1000 cups, we need at least 1000 distinct outcomes. n=10 is the least value of n for which 2^n exceeds 1000. Thus, n must be at least 10.

We know that there is in fact a working strategy with 10 pigs, so we also know that our lower bound is attainable.

 Helpful Answer?   

 Yes | No  Inappropriate?

May 5, 2012

by James:

In the 1 hour case the correct answer is 7 pigs.

Saketh is extremely close in his approach, but only considers the loss of one pig in the first set of drinking pigs. For every pig you have remaining going into the second search, the number of tests you can make doubles. Therefore if you can get more than twice as many combinations by sacrificing an extra pig in the first search, then you can test more buckets with the same number of pigs.

Using 7 pigs, build every combination from the binary approach listed above that kills no more than 3 pigs. This gives a total of 64 combinations - splitting the buckets evenly amongst them, this gives a maximum of 16 buckets for each combination.

Then you have 4 pigs and 16 (2^4) buckets, which is solved as in the previous methods.

 Helpful Answer?   

 Yes | No  Inappropriate?

May 30, 2013

by Alister:

The answer is none. You don't need any pigs.
Just go round and smell the buckets. It says they all look the same, but you'd smell the poison. And before anyone says it, even an odourless poison would have a different 'nose' (or snout...) to 999 buckets of water (because water is not 100% odorless)

 Helpful Answer?   

 Yes | No  Inappropriate?

Aug 30, 2013

by nKast:

*Assuming this has to be done within an hour*

First step is to put another 24 empty buckets, or pick up pebbles, coins and pretend to be buckets. Think are made easier this way...

1) Split then into two groups, and number them from 0 to 511.
2) Get 9 pigs and put them in a row judging of their cuteness, let's say the cutest pig is on the right and the least cute pig is on the left!
2) define Dead pig =1, alive pig =0.
3) The cutest pig drinks from the last 256 buckets, the next from every second group of 128, etc. The least cute drinks from every other buckets, (1,3,5,etc remember we are counting from zero.)
4) We wait 30 minutes to see if any of the pigs died, if not we repeat with the next group. On a second though, should we wait another 1-2 minutes just in case any pig turns out to be a fighter? How can we be sure that the poison acts exactly after 30 minutes? Remember that we are at a tight timeline so we better give them to drink again exactly after 30 minutes. We can give our self a few sec window before ...

...WAAAAAIT A MINUTE...
This has nothing to do with binary coding (nor pigs)!

It's all about parallel processing and scheduling your pipelines from getting thirsty. I just need one Pig and a Timekeeper App.

 Helpful Answer?   

 Yes | No