Prisoner's Dilemma With Blindfolds: a math teaser
Seven people are blindfolded and given unique colored hats at a roundtable. How should they cooperate for at least one to guess her own color?
Seven people are chatting at a party. They're told about the rules of this game while they're still chatting (which is as follows). Then they're blindfolded. Someone puts colored party hats on their heads, sits them at a round table, then undoes their blindfolds. They're now able to see each others' hats but not their own. They're not allowed to talk or share notes. They're all asked to each write their own hat color on a piece of paper and submit it. At least one of them has to get it right or none of them get to eat cake.
What strategy should they use so that they'll get to eat cake?
Assume the rules are perfectly fair. There is no social trick. They cannot communicate with each other with their hats on. They can't act as mirrors for each other.
When they're told about this game ahead of time and asked to agree on a strategy ahead of being blindfolded in the beginning, what should the strategy be?
Solve for 2 people first.
This is not a simple puzzle. It's a very sophisticated math problem. And very difficult to solve for seven participants. Try to solve for fewer participants (2, 3 then 4) first. Also be strongly advised that Microsoft, Google, Amazon and Facebook are eliminating these teaser problems in their interview process. These kinds of questions have not been highly co-related with on-the-job abilities. Instead, all major companies are adopting purely algorithms and coding questions with full force.
- You solved it for two people (25%)
- You solved it for three people (25%)
- You'd probably eat cake (25%)
- If instead of a party, this was an actual prison, you'd keep your head (25%)
Davoud Shirazi after an interview with Google
Find the odd ball among eight balls
You are given eight balls that look exactly the same, and a balance to weigh them against each other. Find the odd ball by weighing only twice?
Getting paid for seven days with a single bar of gold
An employer hires you to work for 7 days and has a gold bar with 7 segments to pay you with. How do you get them to not break it to pieces?
Extreme Recursion with Binary Tree Topologies
How many binary tree topologies are possible given n nodes?
MapReduce parallel processing of all known URLs for median length
You are given the data set of all Google crawled URLs on the Internet -- that's a very large set. Write an algorithm to find the median URL length.
- Amin Ariana
- August 2011