Fruits Into Baskets II

Fruits Into Baskets II

What is this problem about?

The Fruits Into Baskets II interview question involves assigning baskets of fruit to a series of children. You have an array fruits representing the quantity of fruit in each basket, and an array baskets representing the capacity of each child's basket. You iterate through the fruits array in order. For each fruit basket, you must give it to the first child (lowest index) whose basket has enough capacity to hold it. Once a child's basket is used, it cannot be used again. If no child has enough capacity, the fruit is discarded. You need to return the number of unplaced fruit baskets.

Why is this asked in interviews?

Companies like Microsoft and Amazon ask the Fruits Into Baskets II coding problem to test a candidate's ability to optimize a linear search. A naive approach would be to iterate through all children for every fruit, resulting in $O(N^2)$ time complexity. It evaluates whether you can use advanced data structures like a Segment Tree to find the "first valid element" in $O(\log N)$ time, demonstrating a deep understanding of range queries.

Algorithmic pattern used

The optimal approach is a Segment Tree.

1. Build a Segment Tree over the baskets array, where each node stores the maximum capacity in its range.
2. For each fruit quantity q in fruits:
   • Query the Segment Tree: If the maximum capacity of the entire tree is less than q, the fruit cannot be placed.
   • Otherwise, traverse the tree to find the first leaf node (child) with capacity $\ge q$.
   • Once found, update that leaf node's capacity to 0 (since it's used) and update the tree.
3. Count the fruits that couldn't be placed.

Example explanation

fruits = [4, 2, 5], baskets = [3, 5, 4]

1. Fruit 4: Needs capacity 4.
   • Child 0 (cap 3) < 4.
   • Child 1 (cap 5) $\ge$ 4. Child 1 takes it. Capacity becomes [3, 0, 4].
2. Fruit 2: Needs capacity 2.
   • Child 0 (cap 3) $\ge$ 2. Child 0 takes it. Capacity becomes [0, 0, 4].
3. Fruit 5: Needs capacity 5.
   • No child has capacity $\ge 5$. Fruit 5 is discarded. Result: 1 unplaced fruit.

Common mistakes candidates make

• Brute Force: Using a nested loop, which will cause a Time Limit Exceeded (TLE) error for large inputs.
• Wrong Data Structure: Using a Binary Search Tree (BST) or standard Binary Search on a sorted array, which doesn't work because you need the first available basket by original index, not the one with the closest capacity.
• Segment Tree State: Not updating the Segment Tree correctly after a basket is used.

Interview preparation tip

Practice the "find first element $\ge X$" query on a Segment Tree. This is a common variation where you use the max value of the left child to decide whether to search left or right.