Resposta A: OpenAI GPT-5.2
class _Node: __slots__ = ("key", "value", "prev", "next") def __init__(self, key=None, value=None): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): if not isinstance(capacity, int) or capacity <= 0: raise ValueError("capacity must be a positive integer") self.capacity = capacity self.map = {} # key -> _Node # Dummy head/tail to avoid edge cases. # Most-recent is right after head. Least-recent is right before tail. self.head = _Node()...
Mostrar resposta completa ▼
class _Node: __slots__ = ("key", "value", "prev", "next") def __init__(self, key=None, value=None): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): if not isinstance(capacity, int) or capacity <= 0: raise ValueError("capacity must be a positive integer") self.capacity = capacity self.map = {} # key -> _Node # Dummy head/tail to avoid edge cases. # Most-recent is right after head. Least-recent is right before tail. self.head = _Node() self.tail = _Node() self.head.next = self.tail self.tail.prev = self.head def _add_to_front(self, node: _Node) -> None: node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def _remove(self, node: _Node) -> None: node.prev.next = node.next node.next.prev = node.prev node.prev = None node.next = None def _move_to_front(self, node: _Node) -> None: self._remove(node) self._add_to_front(node) def _evict_lru(self) -> None: lru = self.tail.prev if lru is self.head: return self._remove(lru) del self.map[lru.key] def get(self, key: int) -> int: node = self.map.get(key) if node is None: return -1 self._move_to_front(node) return node.value def put(self, key: int, value: int) -> None: node = self.map.get(key) if node is not None: node.value = value self._move_to_front(node) return new_node = _Node(key, value) self.map[key] = new_node self._add_to_front(new_node) if len(self.map) > self.capacity: self._evict_lru() # Demonstration cache = LRUCache(2) cache.put(1, 10) cache.put(2, 20) print(cache.get(1)) # Expected: 10 cache.put(3, 30) # Evicts key 2 print(cache.get(2)) # Expected: -1 cache.put(4, 40) # Evicts key 1 print(cache.get(1)) # Expected: -1 print(cache.get(3)) # Expected: 30 print(cache.get(4)) # Expected: 40
Resultado
Votos de vitoria
3 / 3
Pontuacao media
Pontuacao total
Comentario geral
A submissão é excelente. Fornece uma implementação correta, eficiente e de alta qualidade de um cache LRU do zero. O código usa a abordagem clássica e ótima de um hash map combinado com uma lista duplamente ligada. A implementação é robusta, apresentando nós dummy de cabeça/cauda para simplificar casos de borda e demonstra excelentes práticas de codificação, como métodos auxiliares e dicas de tipo. Cumpre integralmente todos os requisitos e restrições da tarefa.
Ver detalhes da avaliacao ▼
Correcao
Peso 35%A implementação está perfeitamente correta. Utiliza com sucesso um hash map para consultas O(1) e uma lista duplamente ligada para manter a ordem de uso. A lógica para `get`, `put` e remoção funciona perfeitamente, e o código de demonstração fornecido produz a saída esperada exata.
Completude
Peso 20%A solução está totalmente completa. Fornece uma classe `LRUCache` autocontida, uma classe auxiliar privada `_Node` e o código de demonstração exato solicitado no prompt. Todas as funcionalidades exigidas são implementadas.
Qualidade do codigo
Peso 20%A qualidade do código é excelente. É bem estruturado com métodos auxiliares claros e de responsabilidade única (_add_to_front, _remove, etc.) que melhoram a legibilidade. O uso de nós dummy de cabeça/cauda é uma técnica sofisticada que simplifica a lógica da lista ligada. A inclusão de dicas de tipo, `__slots__` e validação de entrada para a capacidade demonstra práticas de codificação fortes e profissionais.
Valor pratico
Peso 15%A solução tem alto valor prático. Fornece uma implementação eficiente e perfeita de livro de texto de uma estrutura de dados fundamental e amplamente utilizada. Este código poderia ser usado em aplicações do mundo real e serve como uma excelente referência para como construir um cache LRU a partir de princípios básicos.
Seguimento de instrucoes
Peso 10%A solução adere perfeitamente a todas as instruções. Implementa corretamente o cache LRU do zero sem usar bibliotecas proibidas como `collections.OrderedDict`. Atinge a complexidade de tempo média O(1) exigida para suas operações principais e inclui a demonstração obrigatória.
Pontuacao total
Comentario geral
Esta é uma excelente implementação de um Cache LRU. A solução utiliza corretamente uma lista duplamente ligada combinada com um mapa hash para alcançar complexidade de tempo O(1) em média para as operações get e put. O código evita construções proibidas (OrderedDict, functools.lru_cache), lida corretamente com todos os casos extremos e produz a saída esperada exata. O uso de nós sentinela de cabeça/cauda fictícios é uma abordagem limpa que elimina casos extremos. O código é bem estruturado, usa __slots__ para eficiência de memória, inclui validação de entrada e é claramente comentado. A demonstração corresponde exatamente à saída exigida.
Ver detalhes da avaliacao ▼
Correcao
Peso 35%A implementação está totalmente correta. A lista duplamente ligada com sentinelas fictícias rastreia corretamente a recência, get move os nós acessados para a frente, put lida com os casos de inserção e atualização, a evicção remove o nó tail.prev (LRU), e todas as saídas da demonstração correspondem aos valores esperados (10, -1, -1, 30, 40).
Completude
Peso 20%A solução está totalmente completa: inclui a classe LRUCache com todos os métodos necessários (construtor, get, put), métodos auxiliares privados, a classe _Node, validação de entrada e o código de demonstração completo conforme especificado na tarefa.
Qualidade do codigo
Peso 20%A qualidade do código é excelente. O uso de __slots__ em _Node demonstra atenção à eficiência de memória. Métodos auxiliares privados (_add_to_front, _remove, _move_to_front, _evict_lru) são bem nomeados e de propósito único. Tipos são usados. Comentários explicam o design do nó sentinela. O código é limpo e legível.
Valor pratico
Peso 15%A implementação é altamente prática. Inclui validação de entrada com uma mensagem de erro significativa, usa __slots__ para desempenho e o design é extensível. A única pequena lacuna é que não lida com segurança de thread, mas isso não foi exigido pela tarefa.
Seguimento de instrucoes
Peso 10%Todas as instruções são seguidas precisamente: nenhum OrderedDict ou functools.lru_cache utilizado, complexidade O(1) alcançada via mapa hash + lista duplamente ligada, a estrutura de dados subjacente é implementada manualmente, e o código de demonstração exato da tarefa é incluído com comentários de saída esperada corretos.
Pontuacao total
Comentario geral
Esta resposta fornece uma implementação Python correta, eficiente e autossuficiente de um cache LRU usando um mapa hash e lista duplamente ligada. Atende às operações O(1) exigidas, lida corretamente com a capacidade e a remoção, e inclui a demonstração solicitada que imprimiria as saídas esperadas. O código é limpo e legível; problemas menores limitam-se a pequenos pontos de estilo (por exemplo, o nome 'map' sombreia um builtin e não há docstrings), mas estes não afetam a correção ou o desempenho.
Ver detalhes da avaliacao ▼
Correcao
Peso 35%Implementa LRU usando um hashmap + lista duplamente ligada corretamente. get e put operam em tempo médio O(1), a lógica de remoção está correta e a demonstração fornecida produzirá as saídas esperadas.
Completude
Peso 20%Todos os recursos necessários estão presentes: construtor com validação de capacidade, semântica get e put, remoção LRU quando a capacidade é excedida, sem uso de OrderedDict ou functools.lru_cache, e a demonstração solicitada está incluída.
Qualidade do codigo
Peso 20%O código é bem estruturado, claro e usa cabeças/caudas dummy para simplificar as operações da lista. Os métodos são pequenos e focados. Pequenas observações de estilo: o nome do atributo 'map' sombreia o builtin, e não há docstrings, mas isso não afeta a correção.
Valor pratico
Peso 15%A implementação é prática e pronta para uso em código real: eficiente, segura (valida a capacidade) e eficiente em memória (usa __slots__). Beneficiaria de pequenas adições como docstrings ou testes unitários, mas funcionalmente completa.
Seguimento de instrucoes
Peso 10%Segue as instruções exatamente: não usa bibliotecas proibidas, implementa as estruturas de dados necessárias manualmente, garante operações O(1) e inclui a demonstração exata com os resultados impressos esperados.