Google is known as the king of riddle recruitment and its insanely difficult puzzles often go viral online. Large companies use these recruitment puzzles to narrow down a huge graduate applicant pool to a select few. A coder googled the words “python lambda function list comprehension” and got “You’re speaking our language. Up for a challenge?” as an answer from the search engine. After the coder solved the “100 hats riddle”, he was offered a job at the tech powerhouse. 

The “100 hats riddle”

There are 100 prisoners lined up by an executioner and they wear red or blue hats upon their heads. Prisoners can only see the hats of the people lined up in front of them, but they cannot look at the hats behind them or at their own. The executioner starts at the back of the line and asks each prisoner the colour of their hat. If the prisoner answers correctly, he lives. If they get it wrong, he is killed instantly and silently. This means that the other prisoners will hear the answer, but they do not know whether or not it was correct. Before lining up, the prisoners are allowed to collectively come up with a strategy. What should they do?
Teams from the University of Oxford, Canadian Institute for Advanced Research and Google’s DeepMind solved the “100 hats riddle” using artificial intelligence. The authors of this research paper proved that it is possible to reformulate tasks, which are made to be challenging for humans, as artificial intelligence problems and that their extension of existing algorithms can successfully solve multi-agent communication problems. 
The answer requires a coordinated strategy and internal communication. The AI’s best strategy will present a situation where 99 of the prisoners can be saved with 100 percent certainty. Only the first prisoner will have a 50/50 chance of survival. He has the most information and must give an answer such that the other prisoners can give the correct answer. The prisoners must follow a communication protocol to ensure this. The first prisoner to speak will say ‘blue’ if the number of blue hats he sees in front of him is even and will say ‘red’ if the number of blue hats he sees in front of him is odd. With this information, the rest of the prisoners can figure out their own hat colour based on the hats they see in front of them and the responses they have heard behind. In this way, all prisoners except the first one will definitely answer correctly. 
If you want to work at any of America’s best companies such as Google you need to have an answer to such puzzling questions. Are you smart enough?

This article was written by Renske Zijm