Apple·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Apple SWE interview with a classic logic puzzle that sounds deceptively simple but has a pretty elegant solution once you see it. The parity trick is well-known in puzzle circles but I'd never actually had to work through it under pressure before.

Questions Asked (1)

A line of dwarves each wear a hat that is either black or white. Each dwarf can see all hats ahead of them but not their own or those behind. Starting from the back, each dwarf must announce their own hat color out loud, and everyone hears every previous announcement. They can agree on a strategy beforehand. What strategy guarantees the most correct guesses?

Algorithms & Data Structures

Author's notes

I knew this type of puzzle existed but blanked on the mechanics for a minute.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use parity (XOR) to encode information: the first dwarf (at the back) announces the parity of all hats ahead, sacrificing his own guess to save the rest. Each subsequent dwarf deduces their own hat by comparing the announced parity with the hats they can see and the previous announcements.

Pro tip: Emphasize that the strategy guarantees all but the first dwarf guess correctly, and clarify that the first dwarf's guess is not random but a deliberate parity signal. This shows you understand the trade-off between individual and collective success.

1. Define the encoding

Agree that the first dwarf will say 'black' if the number of black hats ahead is even, and 'white' if odd (or vice versa). This encodes the parity of the remaining hats.

2. First dwarf's announcement

The dwarf at the back counts the black hats ahead, computes parity, and announces the corresponding color. This may or may not match his own hat, but it conveys the parity to everyone.

3. Subsequent deduction

Each following dwarf hears the previous announcements, sees the hats ahead, and knows the initial parity. By tracking how many black hats have been announced (excluding the first) and how many are visible, they deduce their own hat color.

4. Iterative process

Each dwarf updates the parity based on the previous dwarf's correct guess, ensuring that the parity information remains consistent for the next dwarf.

5. Guarantee and limitations

This strategy guarantees that all dwarves except possibly the first guess correctly. The first dwarf has a 50% chance of being correct, but the overall number of correct guesses is maximized.

Key Points to Mention

Parity (even/odd) or XOR operation as the core encoding mechanism.
The first dwarf's role as the 'sacrificial' information provider.
How each dwarf uses the parity, visible hats, and previous announcements to deduce their own hat.
The guarantee that all but the first dwarf guess correctly, maximizing total correct guesses.
The strategy requires pre-agreement on the encoding (e.g., black = even, white = odd).
This is a classic information theory puzzle demonstrating the power of encoding and deduction.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.