Home » Interview coding problems/challenges

Prisoners and the poison

Prisoners and the poison: This is puzzle problem asked in many interviews and was recently featured in Samsung face to face interview round. Submitted by Radib Kar, on April 01, 2019

Problem statement

There was a brutal emperor in SamLand who was very fond of wine. Due to his brutality and arrogant nature, none of his troops even liked him. They eventually wanted to get rid of the emperor's autonomy. Thus they unanimously decided to kill the emperor. They planned to mix poison in all the 15 bottles of wine the emperor recently ordered. 5 of the troops were assigned that risky task to kill the emperor.

However, the queen loved the emperor a lot and she always supervised everything without letting others knew anything. She actually got the news of secret planning of murdering the emperor. She at once went there and caught all the 5 who were there to mix the poison.

All of the 5troopers were prisoned. Emperor got to know that only one of those 15 bottles is already poisoned. Now emperor thought that as a punishment he will use those 5 prisoners to taste those wines out of the bottle to figure out the poisoned bottle(if someone drinks the poisoned wine, dies at once). So that He can enjoy the other 14 bottles of wine with his queen.

But, the prisoners planned that they all 5 will not die all along. Rather they will come out with a plan so that the maximum of those 5 survives.

But the emperor forced all of them to taste the wines. So, all have to taste wines from bottles.

N.B: prisoners also don't have any idea which bottle is poisoned as they were there to mix randomly.

Solution

So our task is to maximize the number of survival or minimum number of killing

Let's order the bottles 1 to 15 and write their equivalent binary representation up to 5 bits

    1-	00001
    2-	00010
    3-	00011
    4-	00100
    5-	00101
    6-	00110
    7-	00111
    8-	01000
    9-	01001
    10-	01010
    11-	01011
    12-	01100
    13-	01101
    14-	01110
    15-	01111

And number our five prisoners 5 4 3 2 1
The prisoner drinks a bottle if the corresponding bit is one.
Like bottle 1 - 00001 thus it's tasted by one prisoner 1
bottle 2 - 00010 thus it;s tasted by one prisoner 2
bottle 14- 01110 thus it's tasted by prisoner 2, 3, 4

So all have different patterns and we can figure out seeing which prisoners die after tasting,
Like if only prisoner no. 1 dies, then bottle 1 is poisoned.
If prisoner no. 1, 2 dies, then bottle 3 is poisoned.
So on...
Thus what can be the case when maximum dies?
That is for bottle 15
1,2,3,4 dies
5 survives
So, maximum 1 out of the 5 survives.

Now the problem can be extended for any number of bottles, prisoners or there may be other modifications, but the basic idea still is the same.