Published on

LFU Cache

Authors

📝 Vazifa tavsifi

Tayyor LFU (Least Frequently Used) cache xotira kutubxonalarisiz ushbu kesh tizimini yarating.

Tizim quyidagi operatsiyalarni O(1) o'rtacha vaqt murakkabligida qo'llab-quvvatlashi kerak:

  • get(key): keshda kalit mavjud bo'lsa uning qiymatini qaytaradi.
  • put(key, value): agar kalit mavjud bo'lsa uni yangilaydi. Aks holda, kalit-qiymat juftini qo'shadi. Agar kesh sig'imi to'lib qolsa, eng kam ishlatilgan (eng kichik chastotaga ega) elementni o'chirib yuborishi kerak.

Agar chastotalar bir xil bo'lsa, eng eski ishlatilgan (LRU) element o'chiriladi.

Eslatma: Bu yerda funksiya test sifatida ketma-ket kesh operatsiyalari massivida bajariladi. solve funksiyasiga sig'im va test so'rovlari beriladi, u barcha get so'rovlarining natijalarini qaytaradi.

Misol:

Input: capacity = 2, queries = [["put", 1, 1], ["put", 2, 2], ["get", 1], ["put", 3, 3], ["get", 2], ["get", 3]]
Output: [1, -1, 3]
Tushuntirish:
put(1,1), put(2,2).
get(1) -> 1 qaytaradi (1 ning freq=2).
put(3,3) -> freq si eng kam bo'lgan 2 ni o'chiradi.
get(2) -> -1 qaytaradi (o'chirilgan).
get(3) -> 3 qaytaradi.

LFU Cache

Qiyin45 daqiqa30 ball

📚 Misollar

Kiruvchi: capacity = 2, ops = ["put", "put", "get", "put", "get", "get"]...
Chiquvchi: [1, -1, 3]
func solve(_ capacity: Int, _ ops: [String], _ args: [[Int]]) -> [Int] { // ops = "put" yoki "get" lardan iborat massiv // args = put uchun [key, value], get uchun [key] // get amallari qaytargan qiymatlarni massiv qilib qaytaring return [] }

Run tugmasini bosing

Buy mea coffee