← Bank of America Interview Insights

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

Intermediate
Apr 2026

Summary

Short technical screen for a quant engineer role, basically one combinatorics/probability puzzle with a follow-up that pushed the general case. Not a lot of context to go on but the question itself was meaty enough.

Questions Asked (1)

Q1

There are people wearing hats of k different colors. Given some setup involving hat colors and guessing, how do you solve the general case with k colors instead of just 2?

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The 2-color version I could handle, but when they pushed to k colors I had to slow down and actually think about the structure.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the exact hat-guessing puzzle and the goal (e.g., maximize guaranteed correct guesses). Then, generalize the binary strategy by encoding each color as a number modulo k and using modular arithmetic to compute a checksum that each prisoner can adjust for. Finally, explain how the strategy ensures exactly one prisoner guesses correctly and the rest can deduce their own hat color.

Pro tip: Emphasize that the solution relies on the prisoners agreeing on a deterministic encoding and that the strategy is optimal because it achieves the information-theoretic lower bound of at least one correct guess.

1. Clarify the problem

Restate the puzzle to ensure you understand the setup: number of prisoners, number of colors, and the guessing protocol. Confirm that prisoners can hear previous guesses and that the goal is to guarantee at least one correct guess.

2. Encode colors as numbers

Assign each color a unique integer from 0 to k-1. This allows you to treat the hat colors as elements of the cyclic group Z_k.

3. Define a checksum

Have the prisoners agree on a target checksum, e.g., the sum of all hat colors modulo k. The first prisoner computes the sum of the hats they see and guesses the color that would make the total sum equal to the target.

4. Propagate information

Each subsequent prisoner uses the previous guesses and the hats they see to deduce their own hat color, ensuring that exactly one prisoner (the first) may be wrong, but all others guess correctly.

5. Analyze optimality

Explain that this strategy guarantees at least one correct guess, which is optimal because with k colors, the prisoners can always ensure at least one correct guess, and no strategy can guarantee more than one correct guess in the worst case.

Key Points to Mention

  • Modular arithmetic and encoding colors as numbers modulo k.
  • The concept of a checksum or parity generalization to k colors.
  • The role of the first prisoner as the information provider.
  • Inductive reasoning for subsequent prisoners to deduce their hat color.
  • Optimality: the strategy achieves the theoretical lower bound of at least one correct guess.
  • Communication protocol: prisoners must agree on the strategy beforehand and cannot communicate after hats are placed.

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