Famous Prisoners Puzzles | Amazon , Microsoft Interview
Prisoners & Light Bulb———————-
There is a prison with 100 prisoners, each in separate cells, which are sealed off, soundproof and windowless. There is a lobby in the prison with a lightbulb in it. Each day, the warden will pick one of the prisoners at random (even if they have been picked before) and take them out to the lobby. The prisoner will have the choice to flip the lightbulb switch if they want. The lightbulb starts in the “off” position.
When a prisoner is brought out to the lobby, he also has the option of saying “Every other prisoner has been brought out to the lobby.” If a prisoner chooses to say this and it is true, all the prisoners will go free. However, if a prisoner chooses to say this and it’s wrong, all the prisoners will be executed. So a prisoner should only say this if he knows it is true for sure.
Before the first day of this process begins, all the prisoners are allowed to get together to discuss a strategy to eventually save themselves.
What strategy could they use to ensure their eventual salvation?
Prisoners & Boxes—————————
You are the janitor at a prison with 100 prisoners locked in separate, soundproof and windowless cells.
You watch one day as the warden brings the prisoners out to a central room where there are 100 boxes laid out, labeled 1 through 100. He hands each prisoner a slip of paper and a pen, and asks everyone to write their name on their slip and hand it back to him. All the prisoner’s have different names.
The warden then makes a proposition to the prisoners. He will put them back in their cells and will put each of the 100 slips of paper into a different box. The prisoners will then be brought out one by one in a random order. When a prisoner comes out, he will get to open 50 boxes. He doesn’t need to preselect which boxes he’ll open; he can choose as he goes along. He is also not allowed to rearrange the boxes or the names as he does this.
If any of the 50 boxes he opens contains the slip with that prisoner’s name on it, then that prisoner “passes” the test. He will be sent back to his cell, all of the boxes will be closed, and the next prisoner will be brought out. However, if any prisoner opens 50 boxes and none of them contain his name, then all 100 prisoners will be executed. Note that prisoners have no way of passing information on to any of the prisoners who go after them.
If all of the prisoners are able to “pass” the test, then they will all be set free, and you’ll receive a big promotion.
Luckily for the prisoners, the warden is going to let you help them in the following way. After he’s put all of the names in the boxes, he will bring you into the room, let you look at all the names in all the boxes, and then, if you choose to, switch two names with each other. For example, you could switch the names in boxes 35 and 77. You are only allowed to make one switch.
After you help with this task, you will be sent out of the prison and will not be able to communicate with the prisoners.
Before this strange game begins, you get to meet with the prisoners to discuss a strategy. This strategy must have two parts:
- How do you decide which names to switch, if any at all?
- How does each prisoner decide which 50 boxes he will open?
What plan do you come up with to ensure that the prisoners will all go free?
Make one of the prisoners the "lead" prisoner. This prisoner is the ONLY one who is allowed to turn the light off. Each time any of the other prisoners goes into the lobby, if the light is off, they will turn the light on, but only if they've never turned it on before. This means that each prisoner will only ever turn the light on once. Meanwhile, every time the lead prisoner goes into the lobby, he will turn the light off if it's on. He will keep track of the number of times he has turned the light off. Once the lead prisoner turns off the light for the 99th time, he knows that every other prisoner has turned the light on once (and thus has been in the lobby). At this point, he may say that all the prisoners have been to the lobby, and they will all go free.