Fair Distribution of Cookies

Fair Distribution of Cookies

What is this problem about?

The Fair Distribution of Cookies interview question asks you to distribute $n$ bags of cookies among $k$ children. Each bag contains a certain number of cookies, and you must give each bag to exactly one child. You want to distribute the bags such that the "unfairness" is minimized. Unfairness is defined as the maximum number of cookies received by any single child.

Why is this asked in interviews?

Companies like Microsoft and Amazon ask this Backtracking coding problem to test your ability to explore all possible distributions. It's a variation of the "Partition to K Equal Sum Subsets" or "Bin Packing" problem. It evaluates your skills in recursion, state management, and pruning. Since the number of bags is usually small (e.g., up to 8), an exponential backtracking solution is often the intended approach.

Algorithmic pattern used

This problem is solved using Backtracking.

1. State: An array of size $k$ where children[i] stores the total cookies child $i$ has received so far.
2. Recursion: For each bag of cookies:
   • Try giving it to each of the $k$ children.
   • Recurse to the next bag.
   • Backtrack (subtract the cookies) before trying the next child.
3. Pruning:
   • If the current "maximum cookies" for any child already exceeds our best answer so far, stop that branch.
   • If there are more children than bags left, and some children have 0 cookies, we can prune some redundant states.

Example explanation

Bags: [8, 15, 10, 20, 8], Children: $k = 2$.

1. Give 8 to Child 1.
2. Give 15 to Child 2.
3. Give 10 to Child 1. (Child 1 has 18, Child 2 has 15).
4. Give 20 to Child 2. (Child 1 has 18, Child 2 has 35).
5. Give 8 to Child 1. (Child 1 has 26, Child 2 has 35). Maximum is 35. The backtracking will explore other combinations (like putting 20 and 8 together) to find a lower maximum.

Common mistakes candidates make

• Greedy approach: Thinking that giving the largest bag to the child with the fewest cookies always works. (It doesn't guarantee the global minimum).
• Inefficient Recursion: Not using pruning, which makes the solution too slow even for small $n$.
• Ordering: Not sorting the bags in descending order before starting the backtracking, which is a common trick to find a "good" answer early and prune more branches.

Interview preparation tip

For distribution problems with small $n$, backtracking is the first thing to try. If the interviewer asks for an optimization, mention that this could be solved with Dynamic Programming using Bitmasking to avoid redundant calculations of the same "set of bags."