7 ms·
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 wi
by web_chops 15y ago
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 :)
- ImprovedSilence 15y agoI 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?
- web_chops 15y agoanswer can be found at http://madhurtanwani.blogspot.in/2009/09/find-poisoned-wine-barrel.html http://madhurtanwani.blogspot.in/2009/09/find-poisoned-wine-...
- nitrogen 15y agoI'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.
- Munksgaard 15y agoSPOILER: 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?
- nitrogen 15y agoThat 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 https://news.ycombinator.com/item?id=3804350
- pooriaazimi 15y agoI 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.
- web_chops 15y agoYa, that's correct :) It doesn't make much sense otherwise I guess...
- samlittlewood 15y agoOr your allow a cocktail to be made from the contents of several barrels.
- sbov 15y agoYou also need to specify that you need to know by 30 days. Without both restrictions a simple binary search works.
- deleted 15y ago[deleted]
- deleted 15y ago[deleted]