You have a dataset which contains examples labeled with different classes (single-label, multiple classes); for example, an animal image classification dataset containing different types of animals, one animal per image.
You want to randomly sample an n-element subset from this dataset in such a way that the classes are as balanced as possible, i.e., the difference between the number of examples sampled from each class should be as small as possible.
Write a function which, given n and the number of examples in each class, computes how many examples should be sampled from each class.
This problem asks for a balanced allocation of a fixed sample size across classes, while respecting each class’s available count. The key idea is to distribute samples as evenly as possible, then use any leftover quota to fill classes that still have capacity, keeping the final per-class counts with minimal difference. A simple greedy distribution over the class counts is typically enough, making this an interview-style array allocation problem.
