Prisoners and Light Bulb Puzzle Interview Guide
Prisoners and light bulb puzzle interview guide for shared state, counting protocols, roles, proof, variants, and common mistakes.
Candidates practicing state, counting, and protocol design.
The light bulb is shared state
The classic prisoners-and-light-bulb puzzle uses the bulb as a tiny shared memory device. The strategy must transmit enough information despite limited communication.
Assigning roles simplifies counting
A common approach chooses one counter and has others signal only under specific conditions. The details depend on whether the initial bulb state is known.
Concrete example
If each non-counter turns the bulb on only once when finding it off, the counter can count distinct signals by turning it off and incrementing a count.
Prove termination and correctness
A solution should explain why every required signal eventually reaches the counter and why the counter cannot overcount under the protocol.
Common mistakes
Candidates often give a protocol without proving it works for every prisoner. State roles, initial conditions, and what prevents duplicate signals.
Practice the pattern
Use the LeetQuidity curriculum and calibration to turn this topic into a focused practice plan.