Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Puzzle Description
3.
Solution
4.
Frequently Asked Questions
4.1.
How do you prepare a puzzle?
4.2.
What are Guesstimate Interview Questions?
4.3.
What does wild guess mean?
5.
Conclusion
Last Updated: Mar 27, 2024

Genie and Hats

Author Mehak Goel
0 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM
Interview Puzzles

Introduction 

Puzzles are a good measure of one's analytical skills and lateral thinking. Many product-based companies ask the puzzles to help them filter candidates based on their real-world problem-solving skills to approach a problem they have not seen before.

A puzzle may have multiple solutions. The interviewer is generally interested in the candidate's approach to solving the mystery and the approach to building and thinking creatively about the answer to the puzzle.

In this article, we will be discussing an interview puzzle popularly known as Genie and Hats.

Puzzle Description

A group of men and a genie are stranded on an island. The genie gathers everyone together and places a magical hat on the heads of some of the participants (which means at least one person has a hat).

The hat is magical as it can be seen by others but not by the person who is actually wearing it. Those (and only those) who have a hat must dip themselves underwater at exactly midnight to remove it. 

If there are “N” number of people and “C” number of hats, how long will it take the men to remove all the hats?

Note: 

  • Genie will not reveal how many hats he has put on.
  • The men cannot tell each other that they have a hat.
  • At least one man is having a hat on his head (Thus C > 0).
  • All the men are perfect logicians and know that each other are perfect logicians.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution

To understand the solution, let’s start by taking the example of 3 men on the island. Let’s name each of them for easy understanding as X, Y and Z.

Since there are only 3 men on the island, the genie can put on a maximum of 3 hats. So, the maximum value of C is 3 for now.

 

First Case ( when C = 1) 

In this case, the genie will put only one hat on any one of the 3 men. 

Let’s say he puts a hat on Y. Now, Y will see no other man with the hat while X and Z will see one other man (Y) with the hat. So, the Y will understand that he is the one having a hat on his head and will dip himself underwater at exactly midnight. Hence answer is 1.

 

Second Case ( when C = 2) 

In this case, the genie will put two hats on any two of the 3 men. 

Let’s say he puts the hats on X and Y. Now, X and Y will see one other man with the hat, while Z will see two other men with the hats. Now, if there were only 1 hat, this case would have been solved on the first day, but in this case, no one will dip themselves underwater at midnight. On the second day, a man who sees one that will understand that one hat must be on his head. So, both of them will go underwater on the second night. Hence, the answer is 2.

 

Third Case ( when C = 3) 

In this case, a genie will put the hat on all the 3 men.

Now, X, Y and Z will see two other men with hats. If there were 1 or 2 hats, this scenario would have been solved on the first or second day, but there are 3 hats; thus, on the third day, the man who can see two hats will understand that they all have hats on their head so they all will go and dip themselves underwater on the third night. Hence the answer is 3.

Hence after looking at all the scenarios, the answer to this puzzle of Genie and Hats is C.

Check out this problem - 8 Queens Problem

Frequently Asked Questions

How do you prepare a puzzle?

→ Start with thinking about the puzzle you are being asked.
→ Ask for more clarification.
→ Understand and explain your reasoning.
→ Take more test cases and check your logic.
→ Then finally, give your solution.

What are Guesstimate Interview Questions?

Guesstimate questions include asking candidates to guess or estimate a number based on limited information. Successfully solving guesstimate interview questions requires general knowledge, logical thinking, mental maths, and problem-solving skills.

What does wild guess mean?

Wild guess is based on taking a guess without any knowledge or information regarding the thing.

Conclusion

This article discussed an interview puzzle popularly known as Genie and Hats, which can be asked of you in your job interviews. 

For more such interview puzzles, refer to the Interview Puzzles available and take a look at  Test Series and Topic-Wise Problems for placement preparation.

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding! 

Live masterclass