CareerCup

7.

If you only had 30 minutes, you could only go through once, and than you would be using binary coding to solve it like many people describe.

But since you have 2 rounds, you could use ternary coding, because you can play with 3 states: pig dies after 1st round, pig dies after 2nd round, pig lives. With the first pig checking buckets 1-4-7-etc (10, 11, 12) the first round and 2-5-8 (20, 21, 22) the second round, the second pig checking 3-4-5-10-11-12-etc (010, 110, 210, 011, 111, 211) the first round and 6-7-8-13-14-15 the second round.

3^6 states is 729, not quite enough to rule out all the water, while 3^7 is 2187

And we have Quora.

quora.com/You-have-1000-wine-bottles-one-of-which-is-poisoned-You-want-to-determine-which-bottle-is-poisoned-by-feeding-the-wines-to-the-rats-The-poisoned-wine-takes-one-hour-to-work-How-many-rats-are-necessary-to-find-the-poisoned-bottle-in-one-hour

Correct answer is actually 9 and not 10, because you get 2 rounds in which to test for poison, 2 30-min intervals. It is enough to decide 500 buckets at a time, which can be done with 9 pigs.

simple. answer is 10. you need 10 bits to represent 1000 in binary and so that gives you the answer.

lets take an example of total of 10 bottles or buckets for ease of understanding. 10 is 1010 in binary. If 10th is the one with poison, then animals 1 and 3 will die. If 7th(0111) is poison, then animals 2,3 and 4 will die. Enlarge this to 1000 and you will find that you need 10 animals to find the correct bucket/bottle with poison.

Actually this is a pretty standard question, so I disagree with the disclaimer. The exact same question (worded differently) can even be found in Gayle's Cracking The Coding Interview book.
Answer is 10, every pig will represent a bit, and you need 10 bits to represent 1000 numbers.

The problem is not very well worded because it says "limitless number of pigs". Then you use 1000 pigs, one pig per bucket, feeding all into the same time. Only one dies so you know which bucket was poisoned.

Yes, the binary representation was the answer I arrived at in the interview. However, the interviewer was looking for the answer 9. He extends the binary-based answer to an n-dimensional matrix, by which you need 9 vectors of intersection to identify buckets by a unique combination of numbered pigs. At least that was how he was visualizing the problem.

He told me the time element was not relevant, but I think the answer 9 only works if you implement the test twice in your 1 hour time period. You can either identify the poisoned bucket or rule out 512 buckets by checking roughly half of the buckets each round.

7

7

yes the answer is 9, but the reason oxymoronic2012 wrote in the last paragraph isnt correct - note that you cant measure time, so after half an hour, if no pig is dead - you wouldnt know how much time pass and cant actually do the same trial again.

about what your intrewviewr said: of course time matters, but only that hour > half hour. which means, you use 9 pigs on the first attempt, while each one eat from several buckets - i.e each pig is represented by vector of 1s and 0s.
after a SECOND - you do it again, but now give every pig other buckets - i.e every pig now is represented by another binary vector.
the point is that for a specific bucket: the group of pigs that ate from it in the first round, will be different than the group of pigs that ate from it in the second round.

I am not clear with any answer how we representing with bits, plz can any one elaborate in generic

There is a definite answer to this question. Because in the worst case it needs 1000 pigs to find out the poisonous bucket and the best case is 1. Therefore instead of looking of a definite answer this question is to find out the minimum of expectation of how many pigs needed to find the poisonous bucket.

A solution is proposed on this, cpluspluslearning-petert.blogspot.co.uk/2016/12/identify-posionous-bucket-with-minimux.html.

And further discuss the general cases and a solution is provided - the total number of buckets and how many attempts are allowed.

Actually there are 1000 buckets one of them poisoning. Lets take a 50 pig at first round ,let eat each of them 20 buckets.
1pig=20bucket(only taste not eat full hunger)
50pig=1000buckets at first 30 minutes ,one of them pig will die due to poison.At second 30 minutes Lets take 20 pig again and which pig died after eating 20 buckets again assign each buckets to each pigs at this time one pig must eat only one buckets and died after next 30 minutes.So this way I can find the poisoned buckets within one hours .so there are 70 pigs needed.
This statement is true only if one pig can taste more than 1 pig almost 20 buckets

So ya'all got some mighty impressive math skills there. Yup ya sure do. But speaking as a simple man, perhaps gifted with just a smidgen of common sense but clearly lack'n in that there higher college learn'n that the rest of ya'all are obviously so eager to flaunt. Perhaps ya could take pity on an old duffer and run through the following with me so's I can make sure I has the understanding of this problem correct like.

I.) The primary goal of the problem is to determine the minimum number of pigs that can possibly be used over the course of a test run which has to fall within the following parameters:
A.) must be completed within the space of exactly one hour
B.) will provide a definite answer as to which single bucket out of a group of one thousand other similar buckets is the specific one which has been imbued with some sort of mysterious swine toxin or whose contents have been
II.) The problem offers the following assists
A.) we have been given the knowledge that after a pig has been "Exposed" to the toxin it will die thirty minutes later.
B.) we have an unlimited number of pigs (test subjects) to work with
C.) we have been given some means of assigning a numeric value to each bucket and to each pig which I'm assuming will persist throughout the length of the test.
III.) The problem offers the following constraints
A.) there is no way to tell what the current time is or to tell how much time has elapsed from any given moment to any other given moment or apparently to even estimate its passing, presumably from the exact moment that the test starts and up to and until the entire hour has passed and the test run has been completed
B.) we have not been given any knowledge or information of either the nature or the potency of this mysterious poison. Therefore there is no way of knowing what exactly "Exposure" to the toxin entails, for instance
1.) it may be the bucket which has somehow been imbued with this mysterious swine poison which
a.) may exist in the form of a gas or particulate so powerful that mere proximity to the container is enough to end the life of any unfortunate piggy that gets within it's range or
i.) perhaps the poison requires some unknown amount of time, greater then say one second but less than or equal the amount of time it takes for the average swine to devour the entire portion of food contained within the bucket, assuming of course that the buckets are of course all the same size and contain the same amount of food
ii.) in order for deadly exposure to occur, food or water must be stored within the bucket for an amount of time allowing the supposed toxin to leach into the its contents, providing the exposure required for death only after some unknown amount of the serving each bucket contains has been ingested by the subject.
2.) or it may be the food that is contaminated with the mystery poison, but since we have no information about the toxin in question we still have to consider that it remains possible that on the one hand deadly exposure may occur either almost instantly upon close enough proximity to it or only after some unknown amount has been ingested by the test subject.

Now provid'n that ya'all read through my attempt to restate the problem and the parameters that ya'all are supposed to work within, can ya'll tell me if I got's the understanding of this problem correct in this old noodle of mine?

If I do then ya'all might want to take another look at the answers ya've been putt'n out there for the world to see, cuz to my way of think'n it seems to me that there's a few little variables that ain't nobody been take'n into consideration. Important one's too, the kind that when they ain't considered and accounted for can give a person the wrong answer even when all the math they're do'n say's otherwise. I think somebody told me once that them kind of errors are what they call "errors in logic" as apposed to say a syntax error or forget'n a step in one of them fancy algorithms.

Consider for instance that unless that mystery poison reaches lethel toxicity within the pig extreamly quickly or on contact you will not actually have two equal thirty minute segments to work with. For instance if the each of pigs has to actually ingest the the entire contents of the bucket before you can safely consider all of the test subjects to have been "exposed" to a leathal dose of the toxin then you must account for the time it takes for each and every one of them to consume the portion of food that the buckets contain.

The pig is not going to be healthy for 30 minutes and then suddenly die.

So without a computer I'll pick a random bucket and feed 1 pig See if it worsens over time and if it doesn't I'll feed the other 999 pigs from the other buckets.

Now on a computer without a timer, I guess you take the bit representation because there's only 1 of 2 outcomes, thus 10 as I won't bargain on making the 1 hour limit with 2 batches..

I think 30 is the correct ans.
since no time measuring capability is given.same pigs can't be used for different test cases hoping the time of their death will differentiate the test case.
each test cases could contain 10 pigs and 100 buckets
first test case for 10 (1-10)pigs[001-100,101-200,...,901-1000]
second test case for another 10 (11-20)pigs[001-010 101-110 ... 901-910,11-20 111-120... 911-920,...,91-100 191-200 ... 991-1000]
3rd test case for another 10 (21-30)pigs[001 011 021 031 ... 091 101 111 121 ... 191...981 991,002 022 032 ...092 102 112 122 ... 192...982 992,...,010 020 030 .. 100 110 120 ..200... 990 1000]
each test case could act as a dimension
The 3 pigs that dies could give us the bucket in common which is the answer.
example. if pig 3 14 and 25 died, the common bucket is:235

Use 1000 pigs, each one eats out of one bucket. Only 1 pig dies, you know which bucket is poisoned.