Z28

LFU Cache Tasarımı

Başmühendis (Staff/Lead)
Hedef Süre: 40 - 50 Dakika
Tip: ARRAY

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