Maximize outfits with distinct colors
Company: Point72
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You're given counts of items by color; each outfit must contain exactly 3 items, all of distinct colors. You cannot reuse items. Input formats: either an array counts where counts[i] is the number of items of color i (0-indexed), or a multiset of color labels (e.g., ['red','red','blue','green',...]).
Tasks:
- Return the maximum number of outfits possible and construct one valid assignment for the first min(10, answer) outfits.
- Achieve O(C log C) time where C is the number of colors, and O(C) extra space; total items can be up to 10^6.
- Prove optimality or argue why your algorithm attains the maximum. Hint: a greedy max-heap by remaining counts is likely necessary; beware of pathological distributions (e.g., [100,1,1,...]).
- Handle edge cases: fewer than three nonzero colors; extremely skewed counts; many colors with count=1.
- Example: counts = [3,2,2,1] should yield 2 outfits; one valid schedule is [(color0,color1,color2),(color0,color1,color3)].
Overview: This question evaluates competency in combinatorial optimization and constrained resource-allocation algorithms, along with analysis of time and space complexity and robustness to skewed input distributions and edge cases.
Given color counts or color labels, greedily construct outfits where each outfit has exactly three distinct colors. Return the total count and the first ten deterministic outfits.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
Input: ([3,2,2,1],)
Expected Output: {'count': 2, 'assignments': [[0, 1, 2], [0, 1, 2]]}
Explanation: Prompt-style counts.
Input: ([100,1,1,1],)
Expected Output: {'count': 1, 'assignments': [[0, 1, 2]]}
Explanation: Skewed distribution.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.