Parece que su navegador no es compatible con nuestra aplicación.

Explicación de la solución

Complejidad del tiempo de ejecución

get (hashset): O(1) en el caso medio, O(n) en el peor caso

set (hashset): Constante, O(1)

borrado en la cabeza al añadir un nuevo elemento (lista enlazada): Constante, O(1)

búsqueda para borrar y añadir a la cola (lista enlazada): O(n)

Complejidad: O(n)

Complejidad de la memoria

Lineal, O(n) donde n es el tamaño de la caché.

Desglose de la solución

La caché es una técnica para almacenar datos en un almacenamiento más rápido (normalmente la RAM) para servir futuras peticiones más rápidamente. A continuación se presentan algunos ejemplos comunes en los que se utiliza la caché:

• Una caché del procesador se utiliza para leer los datos más rápido de la memoria principal (RAM).
• La caché en la RAM se puede utilizar para almacenar parte de los datos del disco en la RAM y servir a las futuras solicitudes más rápido.
• Las respuestas de la red se pueden almacenar en la memoria RAM para evitar demasiadas llamadas a la red.

Sin embargo, el almacenamiento de la caché no suele ser lo suficientemente grande como para almacenar el conjunto de datos completo. Así que necesitamos desalojar los datos de la caché cada vez que se llena. Hay una serie de algoritmos de caché para implementar una política de desalojo de la caché. LRU es un algoritmo muy simple y comúnmente utilizado. El concepto central del algoritmo LRU es desalojar los datos más antiguos de la caché para acomodar más datos.

Para implementar una caché LRU utilizamos dos estructuras de datos: un hashmap y una lista doblemente enlazada. Una lista doblemente enlazada ayuda a mantener el orden de desalojo y un hashmap ayuda con la búsqueda O(1) de las claves de la caché. Aquí va el algoritmo para la caché LRU.

If the element exists in hashmapmove the accessed element to the tail of the linked listOtherwise,if eviction is needed i.e. cache is already fullRemove the head element from doubly linked list and delete its hashmap entryAdd the new element at the tail of linked list and in hashmapGet from Cache and Return

Nótese que la lista doblemente enlazada se utiliza para mantener la pista de los elementos accedidos más recientemente. El elemento en la cola de la lista doblemente enlazada es el elemento más recientemente accedido. Todos los elementos recién insertados (en put) van a la cola de la lista. Del mismo modo, cualquier elemento accedido (en la operación get) va a la cola de la lista.