Coding - Number of Ways to Wear Different Hats to Each Other

Here is the full interview question "Coding - Number of Ways to Wear Different Hats to Each Other" asked at Uber:

Problem Statement: Lily has a collection of hats. Each hat is labeled with a number of colors it has. She wants to give some of her friends hats such that each friend i gets exactly c[i] colored hats. No person is allowed to receive multiple hats of the same color. (i.e., if a person receives a hat with color A, no other hat given to them can have color A). Determine if it's possible for Lily to distribute the hats to her friends.

Examples:

1. Input: hats = [[1,1],[2,2],[2,3]], c = [3,2,3] Output: 1

2. Input: hats = [[1,1],[2,2],[2,3]], c = [3,1,2] Output: 0

3. Input: hats = [[1,1],[1,2],[2,3]], c = [1,1,2] Output: 1

Constraints:

• 1 <= hats.length <= 100
• 1 <= hats[i].length <= 100
• 1 <= sum(hats[i]) <= 400
• 1 <= c.length <= 100
• 1 <= c[i] <= 100

Hints:

1. Sort the hats by the number of colors they have.
2. Use a greedy approach to assign hats to friends.

Solution: `python from collections import defaultdict

def numberWays(hats, c): n = len(c) hat_colors = defaultdict(int) for hat in hats: for color in hat: hat_colors[color] += 1

sorted_hats = sorted([c for c in hat_colors.values()], reverse=True)
sorted_c = sorted(c, reverse=True)

i, j = 0, 0
while i < len(sorted_hats) and j < n:
    if sorted_hats[i] >= sorted_c[j]:
        sorted_hats[i] -= sorted_c[j]
        sorted_c[j] = 0
        j += 1
    else:
        sorted_c[j] -= sorted_hats[i]
        sorted_hats[i] = 0
        i += 1

for count in sorted_c:
    if count > 0:
        return 0

return 1

`

This solution uses a greedy approach to assign hats to friends. It sorts the hats by the number of colors they have and the friends by the number of hats they want to receive. Then, it iterates through the sorted lists and assigns hats to friends until all friends have received the desired number of hats or there are no more hats left. If any friend still needs hats after iterating through all the hats, it returns 0. Otherwise, it returns 1.

I found this problem on LeetCode: https://leetcode.com/problems/number-of-ways-to-wear-different-hats-to-each-other/