Reto: LRU Caché

Problema y carateristicas:

• Algoritmo real usando para almacenar en memoria los datos.

Diseñar una estructura de datos que siga las restricciones de una caché de uso menos reciente (LRU)

Inicializa la clase cache LRU con una capacidad de tamaño positivo.

int get(int key) Devuelve el valor de la llave si esta existe, en caso contrario devuelve -1.

void put(int key, int value) Actualiza el valor de la llave si esta existe. En caso contrario, añade el par llave-valor al caché. Si el número de llaves supera la capacidad del caché, elimina la pareja llave-valor menos utilizada recientemente.

---

Características:

• Como entrada en la clase constructor un tamaño, que indica la cantidad que podemos almacenar.
• Guardamos solo los más recientes si superamos la capacidad que nos pasan por parámetro, eliminamos los datos menos utilizados.
• Complejidad temporal debe ser O(1)
• la primera function get return un entero, la cual recibe una llave que también es un entero. Esta devuelve el valor de la llave si esta existe en mis datos almacenados y si no return -1
• put() no return nada. Tenemos dos entradas, la llave y el valor, si la llave ya existe actualicemos el valor, de lo contrario creamos en nuestra cache, la llave y el valor.
• cada vez que actualicemos o agreguemos un valor, es decir, cada vez que llamemos put() el valor actualizado o cambiante, o creado es el valor utilizado más recientemente
• si el numero de llaves supera la capacidad del cache debemos eliminar la pareja llave valor, menos utilizada.

Con una lista doblemente enlazada y hash map se puede muy bien, comparto código en typescript: ``` class DoublyLinkedListNode { key: number; value: number; prev: DoublyLinkedListNode | null; next: DoublyLinkedListNode | null; constructor(key: number, value: number) { this.key = key; this.value = value; this.prev = null; this.next = null; }} class LRUCache { private capacity: number; private cache: Map\<number, DoublyLinkedListNode>; private head: DoublyLinkedListNode; private tail: DoublyLinkedListNode; constructor(capacity: number) { this.capacity = capacity; this.cache = new Map(); this.head = new DoublyLinkedListNode(0, 0); this.tail = new DoublyLinkedListNode(0, 0); this.head.next = this.tail; this.tail.prev = this.head; } get(key: number): number { if (!this.cache.has(key)) { return -1; } const node = this.cache.get(key)!; this.removeNode(node); this.addToFront(node); return node.value; } put(key: number, value: number): void { if (this.cache.has(key)) { const node = this.cache.get(key)!; this.removeNode(node); node.value = value; this.addToFront(node); } else { if (this.cache.size >= this.capacity) { const leastUsed = this.tail.prev!; this.removeNode(leastUsed); this.cache.delete(leastUsed.key); } const newNode = new DoublyLinkedListNode(key, value); this.addToFront(newNode); this.cache.set(key, newNode); } } private removeNode(node: DoublyLinkedListNode): void { const prevNode = node.prev!; const nextNode = node.next!; prevNode.next = nextNode; nextNode.prev = prevNode; } private addToFront(node: DoublyLinkedListNode): void { node.prev = this.head; node.next = this.head.next; this.head.next!.prev = node; this.head.next = node; }} ```