Number of Ways to Wear Different Hats to Each Other

Number of Ways to Wear Different Hats to Each Other

What is this problem about?

The Number of Ways to Wear Different Hats to Each Other problem gives you n people (up to 10) and 40 hat types. Each person has a list of hats they like. Count the number of ways to assign hats such that each person wears a different hat (no two people share a hat) and each person gets a hat they like. Return count mod 10^9+7. This hard coding problem uses bitmask DP over person assignments.

Why is this asked in interviews?

DE Shaw and Roblox ask this because with n ≤ 10 people, bitmask DP over the set of assigned people is feasible (2^10 = 1024 states). Iterating over hats (40 types) and updating assignments creates an efficient O(40 * 2^n * n) solution. The array, bitmask, bit manipulation, and dynamic programming interview pattern is fully exercised.

Algorithmic pattern used

Bitmask DP over people. For each hat h (1..40), for each bitmask of already-assigned people, for each person p who likes hat h and isn't yet in the mask: update dp[mask | (1<<p)] += dp[mask]. Initialize dp[0]=1. Answer: dp[(1<<n)-1]. Iterate over hats as the outer loop to ensure each hat is used at most once.

Example explanation

n=3, hats=[[3,5,1],[3,5],[5]]. People 0,1,2. Target mask=111 (all assigned).

• Hat 1: only person 0 likes it. dp[001] += dp[000] = 1.
• Hat 3: persons 0,1 like it. dp[001]+=dp[000]=1, dp[010]+=dp[000]=1.
• Hat 5: persons 0,1,2 like it. Update masks with bit for each. dp[111] accumulates. Final dp[111] = 4.

Common mistakes candidates make

• Iterating over people as outer loop (allows same hat to multiple people).
• Not initializing dp[0]=1.
• Off-by-one in hat indexing (hats are 1-indexed in most formulations).
• Not using the "iterate hats outer, people inner" structure to enforce uniqueness.

Interview preparation tip

Hat assignment problems with n≤10 are canonical bitmask DP problems. The critical design choice: iterating over hats in the outer loop guarantees each hat is assigned at most once. Iterating over people would allow one person to receive multiple hats. Practice similar assignment problems: "count ways to assign k items with constraints" using bitmask DP when n≤15.