Z28
LFU Cache Tasarımı
Teknik Tanım & Görev
En Az Sıklıkla Kullanılan (LFU) önbellek veri yapısını simüle ediniz. ['put', anahtar, değer] ve ['get', anahtar] işlemlerini işleyiniz. Kapasite dolduğunda, kullanım sayacı EN DÜŞÜK olan eleman atılır. Sayaçları eşit birden fazla eleman varsa, aralarında EN UZUN SÜREDİR ERİŞİLMEYEN (LRU kuralı) tahliye edilir. 'get' işlemleri bulunursa değeri, yoksa -1 döndürür. Tüm get sonuçlarını liste halinde döndürün.
put kuralları:
• Yeni anahtar kullanım sayacı 1 ile eklenir.
• Var olan anahtara put, değeri günceller VE sayacı 1 artırır; kayıt, kendi frekans grubunda en yeni erişilen olur.
• get, bulunan anahtarın sayacını 1 artırır ve aynı şekilde grubun en yenisi yapar.
• Kapasite doluyken yeni anahtar eklenmeden önce, en düşük sayaçlı grupta en uzun süredir erişilmeyen anahtar çıkar.
• kapasite 0 ise put saklamaz, get -1 döner.
Fonksiyon İmzası (Python)
lfu_cache_islemleri(kapasite: int, islemler: list) -> list[int]Girdi ve Çıktı Sözleşmesi
Çıktı Kuralı:Get işlemlerinin tam sayı sonuçları listesi.
Sistem Kısıtları (Constraints)
0 <= kapasite <= 10^4
1 <= islemler.length <= 10^5
anahtarlar, değerler tam sayıÖrnek Yürütme Analizi
kapasite = 2
put(1, 1), put(2, 2), get(1)->1, put(3, 3) (2 atılır, çünkü 1'in frekansı 2, 2'nin 1), get(2)->-1, get(3)->3
cevap: [1, -1, 3]Örnek Test Senaryoları (3)
Örnek 1
Girdi:
[2,[["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["get",3]]]Beklenen Çıktı:
[1,-1,3]Örnek 2: Kapasite 0
Girdi:
[0,[["put",0,0],["get",0]]]Beklenen Çıktı:
[-1]Örnek 3: Tek Eleman
Girdi:
[2,[["put",1,10],["get",1]]]Beklenen Çıktı:
[10]