Muz yeme hızı

Problem

Önünde muz yığınları duran bir maymun var; her yığındaki muz sayısı bir dizi olarak veriliyor ve toplam h saati var (h, yığın sayısından az değil). Maymun saatte k muz yeme hızı seçiyor. Her saat tek bir yığından en fazla k muz yer; yığında k'dan az muz kaldıysa onları bitirir ve o saatin kalanında başka yığına geçmez. Tüm muzları h saat içinde bitirebileceği en küçük tamsayı k nedir?

Girdi:  piles = [9, 4, 15, 7], h = 7
Çıktı:  7
        k = 7: 2 + 1 + 3 + 1 = 7 saat  (yetişir)
        k = 6: 2 + 1 + 3 + 2 = 8 saat  (yetişmez)

Girdi:  piles = [9, 4, 15, 7], h = 4
Çıktı:  15         (her yığına tam bir saat)

Netleştirme soruları

• h >= yığın sayısı garanti mi? (Değilse hiçbir hız yetmez; ne dönmeli?)
• Yığın boyutları ve h ne kadar büyük? (10⁹; hız aralığı ve taşma riski.)
• Hız tamsayı mı olmalı? (Evet.)
• Boş yığın (0 muz) olabilir mi?

İpuçları

Yaklaşım

Brute force: k = 1, 2, 3, ... diye dene, ilk yetişeni döndür. Her deneme O(n); en kötü durumda max(piles) kadar deneme: O(n × max). Değerler 10⁹ olunca imkansız.

Cevap üzerinde binary search: Bu sorunun özü, aradığımız değerin bir dizi elemanı değil, bir parametre olması. İki koşul binary search'ü mümkün kılar:

1. Arama aralığı sınırlı: En küçük anlamlı hız 1; en büyük gerekli hız max(piles), çünkü bu hızla her yığın tek saatte biter ve daha hızlı yemek hiçbir şeyi değiştirmez (h >= n olduğu için yetişir).
2. Yüklem monoton: hoursNeeded(k) artmayan bir fonksiyon. k için yetişiyorsa k+1 için de yetişir.

Böylece "yetişen en küçük k" bir lower bound problemidir. Şablon: lo < hi döngüsü, mid yetişiyorsa hi = mid (mid aday olabilir, atma), yetişmiyorsa lo = mid + 1. Döngü bittiğinde lo == hi cevaptır. Bu şablonun avantajı, "son bulunanı ayrı değişkende tut" gerektirmemesi ve sonsuz döngüye girmemesi (mid her zaman hi'den küçük).

İki taşma tuzağı:

• hoursNeeded toplamı: k = 1 iken 10⁴ yığın × 10⁹ muz = 10¹³ saat; int'e sığmaz, long gerekir. Toplam taşarsa negatif olur ve "yetişiyor" sanılır.
• Tavan bölmesi: (pile + k - 1) / k LeetCode sınırlarında sığar ama değerler int sınırına yaklaşırsa taşar. (pile - 1) / k + 1 her pozitif pile için güvenlidir.

Java çözümü

public final class KokoEatingBananas {

    public int minEatingSpeed(int[] piles, int hours) {
        int lo = 1, hi = 0;
        for (int pile : piles) {
            hi = Math.max(hi, pile);                               // bu hızla her yığın 1 saatte biter
        }
        while (lo < hi) {                                          // "yetişen en küçük hız" = lower bound
            int mid = lo + (hi - lo) / 2;
            if (hoursNeeded(piles, mid) <= hours) {
                hi = mid;                                          // mid yetiyor; daha küçüğü de olabilir
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private static long hoursNeeded(int[] piles, int speed) {
        long total = 0;                                            // speed = 1 iken toplam int'e sığmayabilir
        for (int pile : piles) {
            total += (pile - 1) / speed + 1;                       // ceil(pile / speed), taşmadan
        }
        return total;
    }
}

Karmaşıklık

• Zaman: O(n × log M); M = max(piles). Binary search ~30 adım (log₂ 10⁹), her adımda O(n) kontrol.
• Bellek: O(1).
• Alt sınırı ceil(toplam / h) ile başlatmak adım sayısını biraz azaltır ama asimptotik değişmez; toplamı hesaplarken yine long gerekir.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; 2.000 rastgele girdide (1-8 yığın, 1-30 muz, h n ile n+39 arası) k = 1'den yukarı deneyen brute force ile karşılaştırıldı.

Mülakatçı için

Bu soru, adayın "cevap üzerinde binary search" kalıbını tanıyıp tanımadığını ölçer; backend'de karşılığı kapasite planlamasıdır ("günde en az kaç sipariş işlersek 5 günde biter?"). Monotonluğu açıkça söylemek beklenir: binary search'ün sıralı dizi değil monoton yüklem gerektirdiğini anlatabilen aday kalıbı gerçekten anlamıştır.

İpucu zamanlaması: Aday hızları lineer denemeye başlarsa, kaç deneme gerekebileceğini sor (10⁹). Hâlâ bulamazsa ikinci ipucunu ver. Taşma hatasını kendisi görmezse kod bittikten sonra "k = 1 ve 10⁴ tane 10⁹'luk yığında toplam kaç?" diye sor. Lower bound döngüsünde hi = mid - 1 gibi bir sınır hatası yaparsa [9,4,15,7], 7 ile yürütmesini iste.

Takip soruları:

1. Paketler sırayla gönderilecek ve günlük kapasite en az ne olmalı ki D günde bitsin? (Beklenen: aynı kalıp, aralık max..toplam; LeetCode 1011.)
2. Diziyi m ardışık parçaya bölüp en büyük parça toplamını minimize et. (Beklenen: aynı kalıp; LeetCode 410.)
3. Bu bir batch job: n dosya, her biri farklı boyutta, h saat SLA var; worker throughput'unu (MB/saat) nasıl seçersin ve bu modelde neyi gözden kaçırıyoruz? (Beklenen: aynı binary search; ama gerçekte paralellik, dosya başına sabit maliyet ve throughput'un sabit olmaması.)

Benzer problemler

• Capacity To Ship Packages Within D Days (LeetCode 1011).
• Split Array Largest Sum (LeetCode 410).
• Minimum Number of Days to Make m Bouquets (LeetCode 1482).
• Search in Rotated Sorted Array (LeetCode 33) (bu sette: search-in-rotated-sorted-array).