O01
Depo Ön Bellek
Teknik Tanım & Görev
Bir depo yönetim sisteminde, en sık sorgulanan ürün bilgileri bellekte tutuluyor. Bellek kapasitesi SINIRLI: en fazla `kapasite` kadar ürün saklanabiliyor. Yer kalmadığında, EN UZUN SÜREDİR KULLANILMAYAN (least recently used) ürün bellekten atılıyor. Bir ürünü okumak (get) onu "kullanılmış" sayar ve yenilik sıralamasında en sona taşır.
Sırayla gelen işlemler veriliyor. Her işlem şu iki biçimden biri:
["put", anahtar, değer] -> anahtarı belleğe yaz (varsa değerini güncelle)
["get", anahtar] -> anahtarı oku
Her "get" işleminin sonucunu, işlem sırasını koruyarak bir diziye yaz ve bu diziyi döndür. Anahtar bellekte varsa DEĞERİ, yoksa -1 yazılır. "put" işlemleri çıktı dizisine HİÇBİR ŞEY YAZMAZ.
Var olan anahtara put: değeri günceller VE kaydı en son kullanılmış konuma taşır. Kullanım sırası put ile de yenilenir, yalnız get ile değil.
Kapasite doluyken yeni bir anahtar gelirse önce en uzun süredir kullanılmayan kayıt çıkar, sonra yeni kayıt eklenir. kapasite 0 ise put hiçbir anahtar saklamaz ve get her zaman -1 döner.
Fonksiyon İmzası (Python)
on_bellek_sorgulari(kapasite: int, islemler: list) -> list[int]Girdi ve Çıktı Sözleşmesi
Çıktı Kuralı:Uzunluğu işlemlerdeki 'get' sayısına eşit olan tam sayı dizisi. Hiç 'get' yoksa boş dizi [].
Sistem Kısıtları (Constraints)
1 <= kapasite <= 10^4
1 <= islemler.length <= 10^5
anahtarlar ve değerler tam sayı; -1 yalnızca 'yok' anlamına gelirÖrnek Yürütme Analizi
kapasite = 2
["put",1,10] bellek: {1:10}
["put",2,20] bellek: {1:10, 2:20} (eski -> yeni: 1, 2)
["get",1] -> 10 bulunur, 1 en yeni olur (eski -> yeni: 2, 1) -> ÇIKTI: 10
["put",3,30] kapasite dolu, EN ESKİ (2) atılır -> {1:10, 3:30}
["get",2] -> yok -> ÇIKTI: -1
["get",3] -> 30 -> ÇIKTI: 30
cevap: [10, -1, 30]Örnek Test Senaryoları (3)
Örnek 1
Girdi:
[2,[["put",1,10],["put",2,20],["get",1],["put",3,30],["get",2],["get",3]]]Beklenen Çıktı:
[10,-1,30]Örnek 2: Temel Get/Put
Girdi:
[2,[["put",1,100],["get",1],["get",2]]]Beklenen Çıktı:
[100,-1]Örnek 3: Kapasite 1 Tahliye
Girdi:
[1,[["put",10,50],["put",20,60],["get",10],["get",20]]]Beklenen Çıktı:
[-1,60]