Count Distinct Hat Assignments and Maximize Hat Points
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Each person lists the hats they are willing to wear. Assign one acceptable hat to every person, using each hat at most once. Every hat also has a point value. Return both the total number of valid assignments and the maximum total points among valid assignments.
Implement `hat_assignments(preferences: int[][], points: int[]) -> int[]`, returning `[number_of_assignments, maximum_points]`.
### Constraints & Assumptions
- Hat IDs are `1` through `H`, where `H == len(points)` and `points[h-1]` is hat `h`'s point value.
- `1 <= H <= 12`; there are 0 through 8 people. These small practice bounds allow an exact count without a modulus and keep results within signed 32-bit integers.
- Each preference list contains distinct valid hat IDs and may be empty.
- Hat points are nonnegative integers at most 1,000,000. An assignment's score is the sum of points of its assigned hats, counted once per used hat.
- People are distinct, so exchanging two acceptable hats between people creates a different assignment even if the total points stay equal.
- If no complete assignment exists, return `[0, -1]`. With no people, the one empty assignment has score zero, so return `[1, 0]`.
- Do not count partial assignments or require every available hat to be used.
### Examples
```text
preferences = [[1,2],[2,3]]
points = [5,2,9]
result = [3,14]
```
The assignments are `(1,2)`, `(1,3)`, and `(2,3)`. Their scores are 7, 14, and 11.
```text
preferences = [[1],[1]]
points = [8]
result = [0,-1]
```
Explain how the counting state and maximum-score state are combined without counting an assignment twice. Compare bounded backtracking with a bitmask dynamic program under the stated small sizes.
```hint Separate ways from best score
Two partial assignments may reach the same availability state. Their counts should be added, while their best achievable scores require a maximum rather than addition.
```
Overview: Count valid one-hat-per-person assignments and maximize assigned-hat points with exact counts, unique hat use, and bitmask or backtracking reasoning.
Read the full Roblox Software Engineer interview experience this question came from
Each person lists the hats they are willing to wear. Assign one acceptable hat to every person, using each hat at most once. Every hat also has a point value. Return both the total number of valid assignments and the maximum total points among valid assignments.
Implement `hat_assignments(preferences: int[][], points: int[]) -> int[]`, returning `[number_of_assignments, maximum_points]`.
### Constraints & Assumptions
- Hat IDs are `1` through `H`, where `H == len(points)` and `points[h-1]` is hat `h`'s point value.
- `1 <= H <= 12`; there are 0 through 8 people. These small practice bounds allow an exact count without a modulus and keep results within signed 32-bit integers.
- Each preference list contains distinct valid hat IDs and may be empty.
- Hat points are nonnegative integers at most 1,000,000. An assignment's score is the sum of points of its assigned hats, counted once per used hat.
- People are distinct, so exchanging two acceptable hats between people creates a different assignment even if the total points stay equal.
- If no complete assignment exists, return `[0, -1]`. With no people, the one empty assignment has score zero, so return `[1, 0]`.
- Do not count partial assignments or require every available hat to be used.
### Examples
```text
preferences = [[1,2],[2,3]]
points = [5,2,9]
result = [3,14]
```
The assignments are `(1,2)`, `(1,3)`, and `(2,3)`. Their scores are 7, 14, and 11.
```text
preferences = [[1],[1]]
points = [8]
result = [0,-1]
```
Explain how the counting state and maximum-score state are combined without counting an assignment twice. Compare bounded backtracking with a bitmask dynamic program under the stated small sizes.
```hint Separate ways from best score
Two partial assignments may reach the same availability state. Their counts should be added, while their best achievable scores require a maximum rather than addition.
```
Constraints
- Points defines 1 through 12 hats with IDs 1 through H; there are 0 through 8 people.
- Each preference list has distinct valid hat IDs and may be empty.
- Hat values are nonnegative integers at most 1000000; complete assignments use one acceptable hat per person and each hat at most once.
- People are distinct and unused hats are allowed. Count all complete assignments exactly, without a modulus.
- Return [count,maximumPoints], [0,-1] if impossible, and [1,0] for no people.
Examples
Input: ([[1, 2], [2, 3]], [5, 2, 9])
Expected Output: [3, 14]
Explanation: The source assignments have three choices and best score fourteen.
Input: ([[1], [1]], [8])
Expected Output: [0, -1]
Explanation: Two people cannot share their only acceptable hat.