Question: 100 prisoners are stuck in the prison in solitary cells. The warden of the prison got bored one day and offered them a challenge. He will put one prisoner per day, selected at random (a prisoner can be selected more than once), into a special room with a light bulb and a switch which controls the bulb. No other prisoners can see or control the light bulb. The prisoner in the special room can either turn on the bulb, turn off the bulb or do nothing. On any day, the prisoners can stop this process and say “Every prisoner has been in the special room at least once”. If that happens to be true, all the prisoners will be set free. If it is false, then all the prisoners will be executed. The prisoners are given some time to discuss and figure out a solution. How do they ensure they all go free?
Answer: Since this is the only way they will EVER get out of that prison, they decide to work together and make a plan. They select one prisoner (Bob, easier to refer) as the counter.
Every time any prisoner is selected other than Bob, they follow these steps. If they have never turned on the light bulb before and the light bulb is off, they turn it on. If not, they don’t do anything (simple as that). Now if Bob is selected and the light bulb is already on, he adds one to his count and turns off the bulb. If the bulb is off, he just sits there meditates or whatever he wants to. The day his count reaches 99, he calls the warden and tells him “Every prisoner has been in the special room at least once”.
So how does this solution work? Every time a prisoner enters the room first, he turns on the bulb if it is off. This way every prisoner turns on the bulb only once. When Bob enters and sees the bulb on, he knows that one new prisoner has entered the room so he adds one to his count. So when his counter reaches 99, he knows the rest of them have all been in the special room and obviously, he has been in the special room.
Do they really as these questions in a software interview? They do so better be prepared. Oh wait how can you prepare for such questions? The only thing you can do is practice.
If you have any questions, please feel free to send me an email at [email protected]. If you have any interview questions which you feel would benefit others, I would love to hear about it.
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
Why can’t they write their names on the wall of the room after entering for the first time?
Answer – lets assume bulb is off.
Bob and other prisoner decided that , the person goes first time will turn ON the bulb,if that person goes again and finds bulb is ON then he had to turn it OFF and if it is OFF then do nothing. And bob has to ask every single person about the status of bulb while leaving that room including himself and adding 1 to his count only if he gets reply ‘the bulb is ON ‘ until it reaches to 100.
Great info. I love all the posts, I really enjoyed
Solution (or problem) is wrong. Suppose Bob is taken first and then the other 99. And then the warden choses only the others 99 ad infinitum (never Bob again). Even though everybody has visited the room they will not have a chance to ever get out. They will not be free until Bob visits the cell at least 99 times. But this may never happen. even though everybody has visited the room.
How random is random?
Assuming a uniform random distribution (actually random). let the prisoners be chosen INDEPENDENTLY. Calculate the P( everyone selected ) < epsilon.
chance of being chosen within 100 days.
.67 =1-BINOMDIST(0, 100, 0.01, 1)
when is
1-BINOMDIST(0, n, 0.01, 1) = .99
solve for n:
.99 =1-BINOMDIST(0, 465, 0.01, 1)
0.9991196888 = =1-BINOMDIST(0, 700, 0.01, 1)
Being safe, I would tell everyone to call it in 700 days to have a 99.93% chance of being set free. Depending how impatient we are, 465 days with a 99.00% chance.
I don’t think this answer is correct.
The initial state and mainly the importance of having Bob go in after every prisoner makes this solution a broken one.
Why can’t they ask each 99 of them, “have you ever been to the room”, or if day-to-day basis, just let the prisoner report his name. when the names r all ticked, its done. it is a random variable on which you have no control. but u can monitor and filter out duplicate entries. thats how you solve it..
The longest time for their release is just 27 years.Nothing big.
As Vineet pointed out the initial state of the bulb is not known, which means Bob could undercount by one.
The solution to that is to count each prisoner twice. When Bob reaches a count of 198 each prisoner is guaranteed to have visited the room at least once.
If the initial state of the bulb was on, one prisoner only visited the cell once. If the initial state was off, each prisoner visited the cell twice.
Regardless Bob can be certain that each prisoner has visited the cell at least once.
Each prisoner must turn on the bulb at least once – there is no loss of counts, because if prisoner B enters for the first time and finds the bulb off, he turns it on. If prisoner C – also a first-timer – comes in and sees the light already on, he doesn’t touch it, and Bob will only count B’s first time. HOWEVER prisoner C has NEVER turned the light bulb on – so if he gets picked again, and the bulb is off, he will turn it on, and get counted in this way.
Them prisoners better be patient!
The solution to the problem is fine. There is no restriction on how long this takes. It is true that it could potentially take very long for them to figure out when all prisoners have gone through, but using the method described, it is 100% fail safe (i.e. they won’t call it wrong). However, I do see how it could be interpreted as above. A better explanation would be:
When a prisoner enters the room and he has NEVER turn the light bulb on AND the light bulb is currently off, he flicks on the switch. Thus, all prisoners will flick on the light bulb exactly once and the probability of calling it wrong is 0%. Of course, we won’t be able to tell exactly how long it will take for Bob finish the count (which wasn’t required).
there’s another solution, although not very good..
everyone counts the number of days so that they know the beggining of each 100 day cycle. On the first day of the cycle the person turns on the light, and if during the cycle someone enters more than once they turn the light off. If someone enters on the final day of the cycle and the light is on, everyone has been in during that cycle. The chances of this are small though so they will probly all die before they get out anyway.
well done ….boss
really a nice answer
The solution to the question is not right as it demands bob to go in every night after a prisoner who has never been there goes in – and if bob happens to miss a particular prisoner’s first time in chance then, all of them are screwed forever!
If the initial state of the bulb is not known??
What if the bulb is ON in the beginning, and Bob is the first one to enter in the room.
Isn’t there a risk of Bob loosing counts, i.e. if two new prisoners go in, the light only goes on once. Bob doesn’t know how many new prisoners have been in since his last visit. Another way to put it, if all 99 go in before Bob, but increments his count just by 1. When the others subsequentially go in they will never turn the light on, hence Bob will never increment his count and never get to 100 and they will all be executed.
If bob is not allowed more than once, then it is impossible to say “Every prisoner has been in the special room at least once”. Do you have any suggestions if that is the case?
what if bob is not allowed more then once ,even if every other persons enterd more than 1000 times
The second time Sam goes in, he doesn’t do anything. So picking them at alternating frequencies will not change the outcome. Bob will only count it once.
So does BOB has to enter 99 times ?
You need to mention that if a prisoner has been in the room before, he should turn off the bulb. Otherwise there is the probability that a prisoner Sam is chosen, who turns on the light and then Bob is chosen so Bob increments his count.
Now if Sam and Bob are chosen at alternating frequencies 100 times in a row, Bob will increment the count to 100 since the light is on every time, though only him and Sam have been in the room.
Tough Question. Thanks for the post!