A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor
There is a palace, a King, and a Queen.
An event is scheduled after 35 days in the palace.
The King orders 1000 bottles of wine for the event.
The Queen wants to kill the King.
Queen sends an assassin to mix poison in ONE of the 1000 bottles.
The assassin does the same.
The effect of the poison is such that the person who took it, will die after 7 days.
Also, the King has 10 prisoners on whom he can use the wine to test, whether its poisonous.
Now, somehow the King happened to know about the conspiracy, and want to know about the poisonous bottle.
So, the question is this,
How the King is going to find out the poisonous bottle within 35 days.
Label the bottles from one to one thousand using binary representation. Label the prisoners from one to ten. Then have each prisoner drink something from the bottle(s) having a one in the corresponding binary equivalent position to his number. For example, bottle 47 is represented by 0000010111, so prisoners one, two, three, and five get some from that bottle. Wait seven days, see which prisoner(s) die(s), decode the corresponding binary number, and that's your bottle.
"How many prisoners are required to find two bottles? Take as many days as you need."
Assuming that if you drink poison from one bottle on one day and drink poison from another bottle the next day you still die in seven days from your first poisoning, then you need only 2 prisoners and potentially a lot of days (I think up to 1005 days, but check me for an off by one error). Prisoner A drinks starting at bottle 1 and when he dies, you know bottle <day - 7> is poisoned. Prisoner B starts drinking from bottle 1000 down and similar math determines his poison bottle.
The worst case scenario (in terms of # of days) is bottles 1 and 2 (or similar for bottles 1000 and 999) are poisoned. Prisoner A drinks poison from bottle 1 and dies seven days later. If seven days after drinking from bottle 3 (which happens on day 998) Prisoner B is still alive, then you know that bottle 2 was poisoned (and presumably Prisoner B will die the next day, because you want to be 100% sure on this kind of test).
Sunday, October 05, 2008
1 tasting is sufficient, and I think you'll have an excess of pirates left over.
Label the bottles 1 through 1,000.
Pirate A drinks 1 - 512, Pirate B drinks the remainder. If A dies and B lives, we know that both poisonous bottles are 512 or less. If A dies and B lives, we know that both poisonous bottles are 512 or more. If both die, we know that there is one bottle on each side of the dividing line.
Now, divide the bottles into 512 groups ([1,513],[2,514]...[512,null]). Observe this is now a separate, independent problem with only 512 groups which we can use two pirates to partition in the same way as above. By observing which live and which die, we can see whether it came from a group above or below the dividing line.
We can continue this "group up the bottles" process as follows, using the same numbering convention.
2 pirates to test 1000 bottles
2 pirates to test 512 groups of 2
2 pirates to test 256 groups of 4
2 pirates to test 128 groups of 8
2 pirates to test 64 groups of 16
2 pirates to test 32 groups of 32
2 pirates to test 16 groups of 64
2 pirates to test 8 groups of 128
2 pirates to test 4 groups of 256
2 pirates to test 2 groups of 512
Now you work backwards to figure out which combination of dead pirates implicates what bottles.
There is the important "OK, so thats how you do it, prove to me it actually works now" step. Yeah, I'll get to it later.
Monday, October 06, 2008
Divide wines in groups of 90. So we'll have 10 groups of 90 and one last group of 100 bottles. Have each of the prisoner drink wine from one of the 90 bottle group i.e. have him drink from all of those 90 bottles. After a week either one of the prisoner would die or nobody dies. If a prisoner dies, that group of 90 bottles has the poisoned bottle otherwise the last group of 100 bottles has the poisoned bottle. Now divide that group further into individual groups of 9 bottles each. If a prisoner has already died we'll have 9 prisoners tasting 9 bottles each and we'll be left with 9 bottles otherwise we'll be left with 10 bottles. Again depending on which prisoner died, that group can further be split into a group of 1 bottle each with 8 prisoners left.
Monday, October 06, 2008
The queen does not actually want to poison the king. She is just tired of these drunken bashes and figures that by seeing that flat wine is served, the king will get a reputation for not being the best host for such a bash.
She is thinking outside the bottle.
I simulated my pirate-poisoning algorithm in Ruby and contrary to my expectations it completely failed. Drats. Working on something better -- I'm almost positive 40 pirates lets you find 2 bottles in one swig but can't demonstrate it yet.
Patrick McKenzie (Bingo Card Creator)
Tuesday, October 07, 2008
I've found two solutions:
1) Have the king drink all 1000 bottles, so he can die of alcohol poisoning before the poison kicks in. If his wife's trying to kill him, she's not going to stop if her first plan fails. Hell, make her drink the wine if you know she's trying to kill you.
2) Pour out the wine, drink scotch. Or water. Or scotch and water. Kill queen. Marry comely lass.
Tuesday, October 07, 2008
Mr. Doggett, are you a consultant? In your solution #2, you have the king getting married again. That is a setup for repeat business. (<http://demotivators.com/consulting.html>)
No, not a consultant, but it's nice to know I have something to fall back on.
If you absolutely must solve the problem and don't want to pay me on a recurring basis, just run this on my earlier solution.
Thursday, October 09, 2008
Friday, November 07, 2008
This topic is archived. No further replies will be accepted.Other recent topics
Powered by FogBugz