Visto
Programação
OpenAI
GPT-5.2
VS
Google
Gemini 2.5 Pro
Implementar um Cache LRU (Least Recently Used)
Implemente uma estrutura de dados de cache LRU (Least Recently Used) em Python. Sua implementação deve ser uma classe chamada `LRUCache` que suporte as seguintes operações:
1. `__init__(self, capacity: int)` — Inicializa o cache com uma capacidade inteira positiva.
2. `get(self, key: int) -> int` — Retorna o valor associado à chave se ela existir no cache, caso contrário, retorna -1. O acesso a uma chave conta como um "uso".
3. `put(self, key: int, value: int) -> None` — Insere ou atualiza o par chave-valor. Se o cache exceder sua capacidade após a inserção, evicte a chave menos recentemente usada.
Ambas as operações `get` e `put` devem ser executadas em complexidade de tempo O(1) em média.
Forneça a implementação completa da classe. Em seguida, demonstre sua correção mostrando a saída da seguinte sequência de operações:
```
cache = LRUCache(2)
cache.put(1, 10)
cache.put(2, 20)
print(cache.get(1)) # Esperado: 10
cache.put(3, 30) # Evicte a chave 2
print(cache.get(2)) # Esperado: -1
cache.put(4, 40) # Evicte a chave 1
print(cache.get(1)) # Esperado: -1
print(cache.get(3)) # Esperado: 30
print(cache.get(4)) # Esperado: 40
```
Explique brevemente como sua implementação atinge a complexidade de tempo O(1) para ambas as operações.
