Maximize outfits with distinct colors

Q: Maximize outfits with distinct colors

This is a Coding & Algorithms interview question from Point72 for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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)].

Maximize outfits with distinct colors

Comments (0)