D. E. Shaw & Co. - Investment Firm

  www.deshaw.com
Work in HR? Unlock Free Profile

D. E. Shaw & Co. - Investment Firm Software Developer Interview Question

I interviewed in New York, NY and was asked:
"One brain teaser that I encountered that came from Shaw was the five pirate problem. The five pirates are perfectly logical and need to divide up 100 pieces of gold with the following stipulations: i) There is a pecking order for the pirates from 1-5. ii) The head pirate divies the gold as he sees fit but obviously wants to not be killed and to maximize his share. iii) After this the captain and the crew votes on whether or not they mutiny and kill the captain. A tie means no one mutinies."
Add Tags [?]
Answer

Part of a Software Developer Interview Review - one of 73 D. E. Shaw & Co. - Investment Firm Interview Reviews

Answers & Comments

2
of 2
votes

This is a recursion problem but it's hard to see because of the silly idea of perfectly logical acting pirates. It's also a problem that you aren't necessarily supposed to get immediately but should get with a little nudging. They partly want to judge if you give up easily.

The solution is to start with 2 pirates and work to 5. With 2 pirates the captain gives himself 100 pieces, they vote and it's a tie. With 3 pirates the lowest pirate knows that if he mutinies, he will get nothing in the next round, so the captain gives him 1 piece of gold which is enough to buy his vote (99-0-1). With four pirates (99-0-1-0). Five pirates (98-0-1-0-1)

- Interview Candidate on Apr 24, 2013

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.