Taxa de acerto do cache de um feed
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
Um cache LRU precisa de duas operações rápidas: buscar um post e encontrar o usado há mais tempo para removê-lo.
O OrderedDict do Python mantém a ordem de inserção e consegue mover uma chave para o final. Trate o final como o usado mais recentemente e o começo como o próximo a ser removido.
Em um hit, conte-o e mova o post para o final. Em um miss, insira o post e, se o cache tiver passado da capacidade, retire o primeiro item. No fim, divida os hits pelo número de requisições.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(c)
Restrições
- at most 10⁶ requests
Solução
O tráfego de um feed é concentrado: poucos posts recebem a maioria das visualizações, e é essa concentração que faz valer a pena ter um cache pequeno. A simulação é um cache LRU sobre um OrderedDict: um hit move o post para a ponta dos usados mais recentemente, e um miss o insere e remove da outra ponta quando o cache transborda. Rodar a mesma sequência de requisições contra várias capacidades dá a curva de taxa de acerto sobre a qual uma resposta de entrevista deveria raciocinar: o primeiro exemplo dá um salto quando o cache consegue guardar os dois posts quentes e depois se estabiliza. O segundo exemplo é o ponto fraco conhecido do LRU, uma varredura cíclica um pouco maior que o cache, em que a taxa de acerto cai para zero. Cada requisição é O(1), então o tempo é O(n) por capacidade e o espaço é O(c) para c posts em cache.
from collections import OrderedDict
def hit_ratio(requests, capacity):
cache, hits = OrderedDict(), 0 # front = least recently used
for post in requests:
if post in cache:
hits += 1
cache.move_to_end(post) # now the most recently used
else:
cache[post] = True
if len(cache) > capacity:
cache.popitem(last=False) # evict the least recently used
return round(100 * hits / len(requests), 1)
feed = ["p1", "p2", "p1", "p3", "p1", "p2", "p4", "p1", "p5", "p2", "p1", "p3"]
print([hit_ratio(feed, c) for c in (1, 2, 3, 4)]) # -> [0.0, 16.7, 41.7, 50.0]
print(hit_ratio(["a", "b", "c", "a", "b", "c"], 2)) # -> 0.0
print(hit_ratio(["x", "x", "x"], 1)) # -> 66.7Travou na ideia, e não no código? Projetar um cache distribuído explica isso.