Interview Questions: How can the prisoners tell, with certainty, that all 100 of them have visited the central living room with the light bulb?
The facts of the question: There are 100 prisoners are in solitary cells, unable to see, speak or communicate in any way from those solitary cells with each other. There’s a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his own cell. Everyday, the warden picks a prisoner at random, and that prisoner goes to the central living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven’t been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.
Before the random picking begins, the prisoners are allowed to get together to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?
Strategy and Approach to Answering a Problem Solving (aka Microsoft / Google) Interview Question
If you get asked a problem solving question in an interview, remember that they are NOT looking for the RIGHT answer. They are evaluating the approach you use to think out and solve the problem. A strong candidate demonstrates the following:
- Evaluates and understand the scope of the problem
- Communicates assumptions
- Demonstrates quantitative analytical skills
- Answers the question that has been asked. You’d be surprised how many candidates get lost in the analysis and solve for a different question than what was asked.
How to Answer this Question
In evaluation of the problem, there is no limit on the number of times that a prisoner can go into the cell, however the prisoners need a way to communicate with each other on who when into the cell. Therefore one person is chosen as the counter. If the light switch is on, no prisoner will touch it. If it is off, and a prisoner who has never flicked the switch enters, then he flicks the switch on. It stays like that until the counter returns. The counter never flicks it up, only flicks it down. Once he notices that it’s been flicked up 99 times, he says that 100 prisoners have visited, and they go free.
Note: For this problem solving job interview question, there is an actual logical answer, however the interviewer will want to evaluate your thinking process. In answering the interview question, the lead up to your answer will be just as important as the actual answer itself.
For more problem solving, brain teasers, riddles, puzzles, logic job interview questions, please check our out Problem Solving Interview Section.
List of Problem Solving (aka Microsoft / Google) Interview Questions
- 100 Prisoners and a Light Bulb Interview Question
- 5 Pirates and 100 Gold Coins Interview Question
- Birthday Problem Interview Question
- Bridge Crossing Interview Question
- Burning Rope Interview Question
- Card Game Interview Question
- Crossing the River Interview Question
- Dog Show Interview Question
- Equal Halves of Rectangular Birthday Cake Interview Question
- Estimate the market demand in gallons for skim milk consumed in the U.S. in a given year.
- How many golf balls can you fit in a school bus?
- How many street lamps are there in Manhattan?
- How many times a day does a clock’s hands overlap?
- How Many Zeros in 100 Factorial (100!)?
- How much would you charge to wash all the windows in New York City?
- In a country, in which every family wants a boy
- Rising Tide Interview Question
- The Fermi Problem – How many Piano Tuners are there in Chicago?
- The Heaviest Ball Interview Question
- The Monty Hall Interview Question
- The Race Interview Question
- Tiger and Sheep Interview Question
- Why are manhole covers round?