Hacker News Reader

Comment by web_chops | Hacker News Reader

Bitmaps always fascinate me. They are also the solution for one of the most common interview questions:

How do you pick a single poisoned barrel out of 1000 with 10 prisoners as your guinea pigs :)

I thought about it for 5 minutes and couldn't find an answer (I found several, but they were all half-answers). I looked at the answer below, and it turned out that you'd missed an important part: The prisoners don't die immediately after drinking from a poisoned barrel... They die after 30 days (in other words, they can drink from several barrels, and if any of those barrels were poisoned, they'd die).

But thanks anyway.

You also need to specify that you need to know by 30 days. Without both restrictions a simple binary search works.

Or your allow a cocktail to be made from the contents of several barrels.

Ya, that's correct :) It doesn't make much sense otherwise I guess...

I love problems like that. I'm going to go work that out for awhile, you have any links to the answer, or more questions like it?

answer can be found at http://madhurtanwani.blogspot.in/2009/09/find-poisoned-wine-...

I'm not the OP and I don't have a solution at hand, but I'd start by thinking about error correction and parity, then realize that 10 bits is enough to represent 1000 items completely.

SPOILER: Couldn't you just make one prisoner drink from half the barrels, and then if he dies have another prisoner drink from half of those barrels, and if not from half of the other barrels, and so forth?

That would work for the original question, but with the delayed death and quick response conditions imposed by pooriaazimi[0], it would not work. Tying the solution back to binary, you realize that each barrel has a unique 10-bit identifier (2^10=1024, so numbering the barrels in binary gives each one a unique ID). You assign each prisoner to a bit, then have them all drink from the barrels where their bit is a 1. 30 days later, you'll have a pattern of prisoner deaths exactly matching a single barrel.

Note: I have not verified this solution, and it does not match the solution that was posted elsewhere in this thread.

[0] https://news.ycombinator.com/item?id=3804350

Reply on news.ycombinator.com