K49

Token Bucket Hız Sınırlayıcı

Temel Seviye (Junior)
Hedef Süre: 15 - 20 Dakika
Tip: ARRAY

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]
Python Editörü Yükleniyor...
Girdi Parametreleri
[
  5,
  1,
  [
    [
      0,
      3
    ],
    [
      0,
      3
    ],
    [
      2,
      3
    ]
  ]
]
Beklenen Çıktı
[
  true,
  false,
  true
]