K49
Token Bucket Hız Sınırlayıcı
Teknik Tanım & Görev
Bir API Gateway için Token Bucket (Jeton Kovası) hız sınırlayıcı algoritmasını simüle ediniz. Kova başlangıçta tam dolu (kapasite adet jeton) başlar. İki istek arasındaki süreye göre saniyede 'dolum_hizi' kadar jeton kovaya eklenir (asla kapasiteyi aşamaz). Her istek [zaman, maliyet] formatındadır. Kovada maliyet kadar jeton varsa istek kabul edilir (True) ve jetonlar harcanır; aksi halde istek reddedilir (False) ve kova jeton kaybetmez.
Fonksiyon İmzası (Python)
token_bucket_sinirlayici(kapasite: int, dolum_hizi: int, istekler: list) -> list[bool]Girdi ve Çıktı Sözleşmesi
Çıktı Kuralı:Her istek için kabul/ret (True/False) sonucu listesi.
Sistem Kısıtları (Constraints)
1 <= kapasite <= 10^6
1 <= dolum_hizi <= 10^6
0 <= zaman <= 10^8
1 <= maliyet <= kapasite
İstek zamanları monoton artandırÖrnek Yürütme Analizi
kapasite = 5, dolum_hizi = 1, istekler = [[0, 3], [0, 3], [2, 3]]
0. sn: 5 token var. İstek 3 token -> Kabul, kalan 2 token.
0. sn: 2 token var. İstek 3 token -> Ret, kalan 2 token.
2. sn: 2 sn geçti, +2 token -> 4 token var. İstek 3 token -> Kabul, kalan 1 token.
Cevap: [True, False, True]Örnek Test Senaryoları (3)
Örnek 1: Temel Kova
Girdi:
[5,1,[[0,3],[0,3],[2,3]]]Beklenen Çıktı:
[true,false,true]Örnek 2: Kapasite Tüketimi
Girdi:
[10,2,[[1,5],[1,5],[1,1]]]Beklenen Çıktı:
[true,true,false]Örnek 3: Tam Dolum
Girdi:
[3,5,[[0,2],[10,3]]]Beklenen Çıktı:
[true,true]