Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution
4.
Frequently Asked Questions
4.1.
What are interview puzzles?
4.2.
How to answer puzzle interview questions?
4.3.
What are some types of interview puzzles?
4.4.
What are some tips for preparing for a puzzle interview?
4.5.
Name some common puzzles asked in the interview.
5.
Conclusion
Last Updated: Mar 27, 2024

Wizards and the Dwarves

Author Komal Shaw
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Interview Puzzles

Introduction

In this article, we will go through the Wizards and The Dwarfs Puzzle Question.

These types of questions are often asked in Interviews. So, we will be going through the problem statement and then analyzing it to get a better understanding.

Problem Statement

There is a village of wizards and a village of N dwarves.

Once a year, the wizards go over to the village of dwarves and line all the dwarves up in increasing height order, such that each Dwarf can only see the dwarves shorter than himself.

The wizards have an infinite supply of white and black hats. They place either a white or black hat on the head of each Dwarf. Then, starting with the tallest Dwarf (in the back of the line), they ask each what color hat he is wearing. If the dwarf answers incorrectly, the wizards kill him (the other dwarves can hear his response but can't tell if he was killed or not). What is the most number of dwarves killed using this optimal strategy?

Note that the dwarves already know that the wizards will do as stated above. So, they can get together and devise an optimal strategy to minimize the people that get killed.

  • Case 1: Answer is a function of N. Output it with N with multipliers or divisor numbers following N. For example, N * 2, N / 2, N * 3 / 4.
  • Case 2: The answer is an integer. Just put the number without any decimal places if it's an integer. If the answer is Infinity, output Infinity.
  • Case 3: Floating point number. Round it off to 2 decimal places and output it as I. xx, where I is the integer part of the answer, and xx are two decimal digits after rounding off.

Solution

Let white hats = 1 and black hats = 0.

Now starting with the tallest dwarf(since the wizard starts from the tallest dwarf standing at the end of the line), who is numbered N, he adds up all the 1's and 0's represented by the color of hats in front of him. Divides that sum by 2, and calls out 'white' if the remainder is 1 and 'black' if the remainder is 0. He may survive depending on the probability which is half.

But now the second last dwarf(according to the way they stand) can know the color of his own hat by adding up the sum of 0s and 1s ahead of him and finding the remainder with 2 and comparing it with the answer given by the dwarf behind him. If the answer is the same, it means he is wearing a black hat, else he is wearing a white hat, which he calls out with full surety, and survives.

Thus in the same way, all dwarves numbered k < N - 1 onwards can find the color of their own hat by adding the colors of dwarves till N-1 behind him and till 1 ahead of him and finding the remainder with 2. If the answer is the same as the one the Nth dwarf gave, it means he is wearing a black hat, else he is wearing a white hat.

Thus by this strategy, at most 1 dwarf will be killed by the wizard but that too has a probability of half.

Check out this problem - 8 Queens Problem

Frequently Asked Questions

What are interview puzzles?

Interview puzzles are some critical thinking problems or brain teasers.

How to answer puzzle interview questions?

We need to first think about the problem, then ask for clarification, use whatever resources we have, explain our reasoning, and provide the solution.

What are some types of interview puzzles?

Riddles and questions, finding amounts, and number tricks.

What are some tips for preparing for a puzzle interview?

Practice, always keep a pen and paper with you and elaborate your approach.

Name some common puzzles asked in the interview.

Crossing the bridge, Hand Shakes at the party, Bag of coins, Clock angle puzzle, Measuring time by burning ropes, and many more.
 

Conclusion

In this article, we have extensively discussed the approach to the "Wizards and The Dwarves" Puzzle Problem. We hope that this blog has helped you understand the process. 

Logical Puzzles:


Pattern Based Puzzles:


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 Interview Puzzles, Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, 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