Cache com política Least Recently Used - remove o item menos recentemente usado quando cheio. Operações get e put em O(1).
LRU Cache é uma estrutura que combina duas ideias: Hash Table: para acesso O(1) por chave Doubly Linked List: para manter ordem de uso e remoção O(1) A lista mantém items ordenados por uso recente: mais recente na frente, menos recente no final. O hash mapeia chaves diretamente para nós da lista. Operações: - get(key): busca no hash, se existe move para frente e retorna valor - put(key, value): se existe atualiza e move para frente; senão cria nó, adiciona na frente, e se exceder capacidade remove o último (LRU) O truque dos nós sentinela (dummy head e tail) elimina casos especiais de lista vazia ou um elemento, simplificando muito o código.
“A combinação de hash table + doubly linked list permite tanto acesso por chave quanto manutenção de ordem em O(1). Nenhuma estrutura sozinha consegue isso.”
Todas operações são O(1) - hash lookup e manipulação de ponteiros.
Hash table dá acesso O(1) ao nó, lista duplamente encadeada permite remoção e inserção O(1).
Armazena no máximo capacity items no hash e na lista.
Sempre O(1) independente do estado do cache.
Mesmo com eviction, operações são O(1).
| Algoritmo | Tempo | Espaco | Melhor Para |
|---|---|---|---|
| LRU Cache(atual) | O(1) get/put | O(capacity) | Cache de acesso frequente, memória limitada |
| LFU Cache | O(1) get/put | O(capacity) | Quando frequência importa mais que recência |
| FIFO Cache | O(1) get/put | O(capacity) | Simplicidade, ordem de chegada |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1class Node:Nó da Lista2 def __init__(self, key=0, val=0):Nó da Lista3 self.key = keyNó da Lista4 self.val = valNó da Lista5 self.prev = NoneNó da Lista6 self.next = NoneNó da Lista7 8 9class LRUCache:Estrutura do Cache10 def __init__(self, capacity):Inicialização11 self.cap = capacityInicialização12 self.cache = {} # key -> nodeBusca no Hash13 # Sentinelas para simplificar operacoes14 self.head = Node()Inicialização15 self.tail = Node()Inicialização16 self.head.next = self.tailInicialização17 self.tail.prev = self.headInicialização18 19 def _remove(self, node):Remover Nó20 node.prev.next = node.nextRemover Nó21 node.next.prev = node.prevRemover Nó22 23 def _add_front(self, node):Adicionar na Frente24 node.next = self.head.nextAdicionar na Frente25 node.prev = self.headAdicionar na Frente26 self.head.next.prev = nodeAdicionar na Frente27 self.head.next = nodeAdicionar na Frente28 29 def get(self, key):Operação Get30 if key not in self.cache:Busca no Hash31 return -1Operação Get32 node = self.cache[key]Busca no Hash33 self._remove(node)Mover para Frente34 self._add_front(node)Mover para Frente35 return node.valOperação Get36 37 def put(self, key, value):Operação Put38 if key in self.cache:Busca no Hash39 self._remove(self.cache[key])Remover Nó40 node = Node(key, value)Nó da Lista41 self.cache[key] = nodeBusca no Hash42 self._add_front(node)Adicionar na Frente43 if len(self.cache) > self.cap:Remover LRU44 lru = self.tail.prevRemover LRU45 self._remove(lru)Remover LRU46 del self.cache[lru.key]Remover LRU47