Distribute Candies

Distribute Candies

What is this problem about?

In the Distribute Candies interview question, you are given an array of integers where each integer represents a candy's type. You need to distribute these candies equally between a brother and a sister. However, the goal is to find the maximum number of unique types of candies the sister can receive. For example, if there are 6 candies of types [1, 1, 2, 2, 3, 3], the sister gets 3 candies, and the maximum unique types she can get is 3.

Why is this asked in interviews?

This "Easy" difficulty problem is popular at Meta, Google, and Bloomberg because it tests basic data structure knowledge and logical reasoning. It evaluation your understanding of Hash Tables or Sets and your ability to apply a simple mathematical constraint. It’s a "warm-up" problem that checks if you can identify that the sister's variety is limited by both the total number of unique types available and the total number of candies she is allowed to have.

Algorithmic pattern used

This problem uses the Hash Set interview pattern.

1. First, count how many unique types of candies exist using a Set.
2. Calculate how many candies the sister is allowed to have, which is n / 2.
3. The answer is the minimum of (number of unique types) and (total candies allowed for the sister). This ensures that if there are more unique types than she can carry, she only gets her maximum allowance. If there are fewer unique types than her allowance, she can get one of each.

Example explanation

Candies: [1, 1, 2, 3] ($n=4$)

1. Unique Types: {1, 2, 3}. Count = 3.
2. Sister's Allowance: $4 / 2 = 2$.
3. Result: $\min(3, 2) = 2$. The sister can take one type '1' and one type '2', or any other combination of two different types.

Common mistakes candidates make

• Over-complicating the Distribution: Trying to actually simulate the distribution to both siblings instead of just applying the mathematical limit.
• Sorting: Using sorting ($O(n \log n)$) to find unique types when a Hash Set ($O(n)$) is more efficient.
• Off-by-one errors: Miscalculating the allowance for the sister.

Interview preparation tip

Whenever a problem asks for the "number of unique elements," your first thought should be a Hash Set. In many "Easy" problems, the solution is just a clever combination of a Set's size and a basic mathematical constraint.