Google Interview Question: KoKo Eating Bananas

This is a famous interview question that is asked multiple times in product-based companies like Google, Amazon, and Microsoft.

Photo by Erik Karits on Unsplash

Problem Description :

Koko loves to eat bananas. There are n piles of bananas, and the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Let me explain the above example to you →

If k = 3, i.e. per hour eating speed of Koko.

1st Pile(3) : 3
2nd Pile(6) : 3 + 3
3nd Pile(7) : 3 + 3 + 1
4th Pile(11) : 3 + 3 + 3 + 2

Total Hours Spent = 1+2+3+4 = 10 hour

But the total time given is 8 hours, so Koko would not be able to finish the piles with speed = 3 bananas per hour

If k = 4

1st Pile : 3
2nd Pile : 4 + 2
3nd Pile : 4 + 3
4th Pile : 4 + 4 + 3

Total Hours spent = 1 + 2 + 2 + 3 = 8 hours

Total time given = time spent, so the answer is k = 4.

Intuition

The first thing that comes to my mind here is to do a hit and trial with different k(eating speed per hour) values and check if Koko is able to eat all bananas or not.

This is kind of a rough idea, that k’s value would be varying from a min point to a max point. It is a monotonous sequence where we need to minimize the k’s value.

What we can use here? Try to think once :)

Approach

Yes, correct, Binary search would be used here.

Algorithm :

a). Create a method/function for checking if Koko is able to eat piles of bananas for the given k value or not.

b). Apply binary search on min k value to max k value and check if, for the kth speed, Koko is able to eat banana or not.

1) If Koko is able to eat a banana: Go to the left side of the binary search, for minimizing the kth value.

2). If Koko is not able to eat a banana: Go to the right side of the binary search.

Complexity

• Time complexity: O(n * log m), where m = maxPile — minPile, n = length of piles array.
• Space complexity: O(1)

Code

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        long minPile = piles[0];
        long maxPile = piles[0];
        long sum = 0;
        if(piles.length == 1){
            if(piles[0] % h != 0){
                return piles[0] / h + 1;
            }
            return piles[0] / h;
        }
        for(int pile : piles){
            sum += pile;
            maxPile = Math.max(maxPile,pile);
        }
        minPile = sum / h;
        return (int)getMinEatingSpeed(piles,minPile,maxPile,h);
    }

    private long getMinEatingSpeed(int[] piles , long left , long right , int h ){
        long mid = 0;
        while(left < right){
            mid = (left + right) / 2;
            if(canEatBananas(piles,mid,h)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canEatBananas(int[] piles , long k , int h){
        int hSpend = 0;
        for(int pile : piles){
            hSpend += pile / k;
            if(pile % k != 0){
                hSpend += 1;
            }
        }
        return hSpend <= h;
    }

}