Koko Eating Bananas

Koko Eating Bananas

1. What is this problem about?

The Koko Eating Bananas interview question is a resource-optimization problem. Koko loves bananas. There are several piles of bananas, and Koko has $H$ hours to eat all of them. Each hour, she chooses a pile and eats $K$ bananas from it. If the pile has fewer than $K$, she finishes the pile and stops for that hour. Your task is to find the minimum integer speed $K$ such that she can finish all piles within $H$ hours.

2. Why is this asked in interviews?

This is a high-frequency question at companies like Uber, Amazon, and Netflix. It tests your ability to apply Binary Search on the answer space. It evaluations whether you can recognize a monotonic relationship: as the eating speed $K$ increases, the total hours required decreases. This is a core Binary Search interview pattern.

3. Algorithmic pattern used

This problem follows the Binary Search on Value pattern.

1. Define Range: The minimum speed is 1, and the maximum speed is the largest pile size (any faster speed won't reduce the hours further).
2. Feasibility Function: Write a canFinish(speed) function that calculates the total hours needed: sum(ceil(pile / speed)).
3. Binary Search:
   • If canFinish(mid) <= H, then mid is a valid speed. Try smaller: ans = mid, right = mid - 1.
   • If canFinish(mid) > H, the speed is too slow. Try larger: left = mid + 1.

4. Example explanation

Piles: [3, 6, 7, 11], $H = 8$.

• Try speed $K=4$:
  • Pile 3: 1 hr. Pile 6: 2 hrs. Pile 7: 2 hrs. Pile 11: 3 hrs. Total = 8.
  • $8 \leq 8$. Valid! Try smaller.
• Try speed $K=3$:
  • Pile 3: 1 hr. Pile 6: 2 hrs. Pile 7: 3 hrs. Pile 11: 4 hrs. Total = 10.
  • $10 > 8$. Too slow. Smallest valid speed is 4.

5. Common mistakes candidates make

• Linear Search: Checking speeds from 1 up to max, which is $O(\max(P) \cdot N)$ and will time out.
• Ceiling Math: Using round() or standard division instead of ceil(). The integer trick for ceil(a/b) is (a + b - 1) / b.
• Search Range: Setting the upper bound too low (e.g., to $H$ instead of the largest pile).

6. Interview preparation tip

"Minimize the maximum" or "Find the minimum rate to satisfy a condition" are the "Bat-Signals" for Binary Search on the answer. Master this pattern as it appears in dozens of hard array problems.