← Bank of America Interview Insights

Bank of America·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Quant engineer screen with a classic brainteaser. One question, pretty short session, left me second-guessing whether my answer was actually rigorous enough.

Questions Asked (1)

Q1

100 prisoners stand in a line, each wearing a randomly assigned red or blue hat. Every prisoner can see the hats of everyone in front of them but not their own. They are released only if they correctly guess their own hat color. What is the maximum number of prisoners you can guarantee will go free?

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I knew this one vaguely but blanked on the clean proof.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a classic parity-based puzzle where the first prisoner sacrifices himself to encode information for the rest. Use the first prisoner's guess to convey the parity of red hats (or blue hats) seen ahead, then each subsequent prisoner deduces their own hat color by combining that parity with the hats they see and the guesses behind them. Conclude that at least 99 prisoners can be guaranteed to go free, with the first prisoner having a 50% chance.

Pro tip: Explicitly state that the first prisoner's guess is not random but a deliberate communication of parity, and that the strategy assumes perfect logical reasoning and no communication after the first guess. This shows you understand the constraints and the elegance of the solution.

1. Clarify the problem and constraints

Restate the problem to ensure understanding: prisoners are in a line, each sees hats ahead, no communication after initial planning, and they must guess simultaneously? Actually, they guess in order from back to front. Confirm that the goal is to maximize the guaranteed number of correct guesses.

2. Identify the key challenge

The main challenge is that the first prisoner (at the back) sees all hats ahead but has no information about his own hat. He must use his guess to convey information to the others without knowing his own color.

3. Devise a parity-based encoding scheme

Agree that the first prisoner will say 'red' if he sees an odd number of red hats ahead, and 'blue' if even (or vice versa). This encodes the parity of red hats among the remaining 99 prisoners.

4. Derive the deduction process for each subsequent prisoner

Each subsequent prisoner, upon hearing the previous guesses, can deduce their own hat color by comparing the parity encoded by the first prisoner with the parity of red hats they see ahead and the known colors of those behind them (from their correct guesses).

5. Conclude the guaranteed number and discuss trade-offs

The first prisoner has a 50% chance of survival, but the remaining 99 are guaranteed to go free. Thus, the maximum guaranteed number is 99. Mention that this is optimal because the first prisoner cannot guarantee his own guess without additional information.

Key Points to Mention

  • Parity (odd/even) as the encoding mechanism
  • The first prisoner sacrifices his own certainty to provide information
  • Sequential guessing order (back to front) allows information propagation
  • Each prisoner uses the parity and observed hats to deduce their own color
  • The strategy guarantees 99 prisoners go free, with the first having a 50% chance
  • Optimality: no strategy can guarantee all 100 because the first prisoner lacks information about his own hat

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