Maximize outfits with distinct colors
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.
Point72
Oct 13, 2025, 9:49 PM
Data Scientist
Technical Screen
Coding & Algorithms
0
0
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)].