İçeriğe geç

Haber akışı için cache hit oranı

Kolay#lru-cache#hit-ratio~15 dk

Görev tanımı

Problem

Bir haber akışı (news feed) servisi son görüntülenen gönderileri veritabanının önündeki bir LRU cache'te (önbellek) tutuyor. Okuyucuların istediği gönderi id'lerinin dizisi ve gönderi cinsinden cache kapasitesi verildiğinde istekleri yeniden oynat: cache'teki bir gönderi için istek bir hit'tir ve onu en son kullanılan yapar; bir miss gönderiyi cache'e yükler, cache kapasiteyi aşıyorsa en az yakın zamanda kullanılan gönderiyi çıkarır. Hit oranını 1 ondalığa yuvarlanmış bir yüzde olarak döndür. Her ek slot'un ne kazandırdığını görmek için birkaç kapasiteyle çağır. En fazla 1.000.000 istek var.

Örnekler

Input:  feed = ["p1", "p2", "p1", "p3", "p1", "p2", "p4", "p1", "p5", "p2", "p1", "p3"],
        capacities 1, 2, 3 and 4
Output: [0.0, 16.7, 41.7, 50.0]
Neden: en çok üçüncü slot katkı yapar, çünkü iki sıcak gönderiyi, p1 ve p2'yi tutmaya yeter
Input:  feed = ["a", "b", "c", "a", "b", "c"], capacity = 2
Output: 0.0
Neden: cache'ten bir gönderi fazla olan bir döngü, her gönderiyi tekrar gerekmesinden hemen önce çıkarır
Input:  feed = ["x", "x", "x"], capacity = 1
Output: 66.7
Neden: edge case: yalnız bir gönderi için ilk istek miss olabilir

İpuçları

0 / 3

Hedef zaman
O(n)
Hedef alan
O(c)

Kısıtlar

  • at most 10⁶ requests

Kodda değil de fikirde mi takıldın? Dağıtık cache tasarla bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır