Pular para o conteúdo

Taxa de acerto do cache de um feed

Fácil#lru-cache#hit-ratio~15 min

A missão

Problema

Um serviço de feed de notícias mantém os posts vistos recentemente em um cache LRU na frente do banco de dados. Dadas a sequência de ids de posts que os leitores pedem e a capacidade do cache em posts, reproduza as requisições: uma requisição para um post em cache é um cache hit e o torna o usado mais recentemente; um cache miss carrega o post no cache, fazendo a eviction (remoção do cache) do post usado há mais tempo se o cache passar da capacidade. Retorne a taxa de acerto (hit ratio) como porcentagem arredondada para 1 casa decimal. Chame a função para várias capacidades para ver quanto cada vaga extra rende. Há até 1.000.000 de requisições.

Exemplos

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]
Por quê: a terceira vaga é a que mais acrescenta, porque basta para manter os dois posts quentes, p1 e p2
Input:  feed = ["a", "b", "c", "a", "b", "c"], capacity = 2
Output: 0.0
Por quê: um ciclo com um post a mais que o cache remove cada post logo antes de ele ser necessário de novo
Input:  feed = ["x", "x", "x"], capacity = 1
Output: 66.7
Por quê: edge case: só a primeiríssima requisição de um post pode ser um miss

Dicas

0 / 3

Tempo-alvo
O(n)
Espaço-alvo
O(c)

Restrições

  • at most 10⁶ requests

Travou na ideia, e não no código? Projetar um cache distribuído explica isso.

Python 3Ctrl+Enter executa