Latest Comments
« What it is like inside Apple | Main | Dividend Yield - An investment factor? »

Firing Squad

A lunch buddy shared an interview question that he had heard from another tech company. It is a thinly veiled CS question, which sort of threw me off my tracks, and made me slightly embarassed it took me a few minutes to get it.

N (where N > 1) prisoners are being lined up to be shot by a firing squad. Each prisoner is given a helmet that is colored either red or green. The prisoners are lined up facing one direction - so the last prisoner can see the helmets of every other prisoner except his own, the second last prisoner can see everyone's helmet except for his and the last prisoner's helmet.

In a strange twist, the crazzzzy chief prison warden decides the firing squard will spare the life of any prisoner if he or she can correctly name the color of his helmet. The firing squad will start from the last prisoner and move sequentially to the first prisoner.

Before the firing squad begins, all the prisoners are placed in a holding cell and they make use of the opportunity to discuss a strategy to maximize the number of prisoners saved.

What is that strategy?

Reader Comments

There are no comments for this journal entry. To create a new comment, use the form below.

PostPost a New Comment

Enter your information below to add a new comment.

My response is on my own website »
Author Email (optional):
Author URL (optional):
Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>