Saltar al contenido

Tasa de aciertos de caché de un feed

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

La misión

Problema

Un servicio de feed de noticias guarda las publicaciones vistas recientemente en una caché LRU delante de su base de datos. Dada la secuencia de ids de publicaciones que piden los lectores y la capacidad de la caché en publicaciones, reproduce las solicitudes: una solicitud de una publicación que está en caché es un acierto y la convierte en la usada más recientemente; un fallo carga la publicación en la caché y desaloja la publicación usada menos recientemente si la caché supera su capacidad. Devuelve la tasa de aciertos como porcentaje redondeado a 1 decimal. Llama a la función con varias capacidades para ver cuánto aporta cada slot extra. Hay hasta un millón de solicitudes.

Ejemplos

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é: el tercer slot es el que más aporta, porque alcanza para mantener las dos publicaciones populares, p1 y p2
Input:  feed = ["a", "b", "c", "a", "b", "c"], capacity = 2
Output: 0.0
Por qué: un ciclo una publicación más largo que la caché desaloja cada publicación justo antes de que se vuelva a necesitar
Input:  feed = ["x", "x", "x"], capacity = 1
Output: 66.7
Por qué: caso límite: solo la primera solicitud de una publicación puede fallar

Pistas

0 / 3

Tiempo objetivo
O(n)
Espacio objetivo
O(c)

Restricciones

  • at most 10⁶ requests

¿Lo que te frena es la idea y no el código? Diseña una caché distribuida lo explica.

Python 3Ctrl+Enter ejecuta