Resposta A: OpenAI GPT-5.2
class LRUCache: class _Node: __slots__ = ("key", "val", "prev", "next") def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = None def __init__(self, capacity: int): if capacity <= 0: raise ValueError("capacity must be a positive integer") self.capacity = capacity self.map = {} # key -> _Node # Doubly-linked list with sentinels: # head <-> ... <-> tail # Most recently used is right after head. # Least recently used is right before tai...
Mostrar resposta completa ▼
class LRUCache: class _Node: __slots__ = ("key", "val", "prev", "next") def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = None def __init__(self, capacity: int): if capacity <= 0: raise ValueError("capacity must be a positive integer") self.capacity = capacity self.map = {} # key -> _Node # Doubly-linked list with sentinels: # head <-> ... <-> tail # Most recently used is right after head. # Least recently used is right before tail. self.head = self._Node() self.tail = self._Node() self.head.next = self.tail self.tail.prev = self.head def _remove(self, node: _Node) -> None: p, n = node.prev, node.next p.next = n n.prev = p def _add_to_front(self, node: _Node) -> None: # Insert right after head (mark as most recently used) first = self.head.next node.prev = self.head node.next = first self.head.next = node first.prev = node def _move_to_front(self, node: _Node) -> None: self._remove(node) self._add_to_front(node) def _evict_lru(self) -> None: # Remove node before tail 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.val def put(self, key: int, value: int) -> None: node = self.map.get(key) if node is not None: node.val = value self._move_to_front(node) return new_node = self._Node(key, value) self.map[key] = new_node self._add_to_front(new_node) if len(self.map) > self.capacity: self._evict_lru() # Demonstration of correctness 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 # Output: # 10 # -1 # -1 # 30 # 40 # Brief O(1) explanation: # - A dictionary (hash map) maps keys to nodes, giving O(1) average lookup for get/put. # - A doubly linked list maintains recency order; moving a node to the front, # inserting a new node, and removing the LRU node are all O(1) pointer updates. # Combining these gives O(1) average time for both get and put.
Resultado
Votos de vitoria
2 / 3
Pontuacao media
Pontuacao total
Comentario geral
Excelente implementação de um cache LRU que atende plenamente a todos os requisitos. A solução utiliza uma combinação bem projetada de um hash map e lista duplamente ligada com nós sentinela para alcançar complexidade de tempo O(1) para operações de get e put. O código é limpo, bem estruturado e lida corretamente com todos os casos extremos, incluindo a atualização de chaves existentes e a devida remoção. A demonstração produz a saída esperada exata (10, -1, -1, 30, 40), e a explicação da complexidade O(1) é precisa e clara. O uso de __slots__ na classe Node demonstra atenção à eficiência de memória. Observações menores: o ValueError para capacidade não positiva é um bom toque defensivo, mas não foi explicitamente exigido; a explicação poderia ter sido um pouco mais detalhada sobre por que as consultas ao dicionário são em média O(1). No geral, esta é uma implementação de qualidade de produção.
Ver detalhes da avaliacao ▼
Correcao
Peso 35%A implementação está correta e produz a sequência de saída esperada exata (10, -1, -1, 30, 40). Todas as operações principais funcionam corretamente: get retorna os valores corretos e marca os itens como usados recentemente, put insere corretamente novos itens e atualiza os existentes, e a remoção remove corretamente o item menos usado recentemente quando a capacidade é excedida. A lista duplamente ligada com sentinelas mantém corretamente a ordem de recência. Casos extremos, como a atualização de uma chave existente, são tratados corretamente. A única dedução menor é que o ValueError para capacidade não positiva, embora seja uma boa prática, não foi explicitamente exigido pela tarefa.
Completude
Peso 20%A resposta está totalmente completa. Fornece a classe LRUCache inteira com todos os métodos necessários (__init__, get, put), inclui uma demonstração completa e funcional com a sequência de teste exata especificada, produz todas as saídas esperadas e conclui com uma explicação clara da complexidade de tempo O(1). A implementação inclui métodos auxiliares (_remove, _add_to_front, _move_to_front, _evict_lru) que são bem organizados e necessários para a solução. Nada está faltando ou incompleto.
Qualidade do codigo
Peso 20%O código é de alta qualidade, com excelente estrutura e legibilidade. O uso de uma classe aninhada _Node com __slots__ demonstra consciência da eficiência de memória. Os nomes dos métodos são descritivos e seguem as convenções do Python. A implementação da lista duplamente ligada com nós sentinela é elegante e evita casos extremos de verificação de nulos. Comentários explicam claramente o layout da estrutura de dados e o propósito de cada método. O código está bem organizado, com separação lógica de responsabilidades. Menor: o comentário explicativo no final poderia ser um pouco mais detalhado sobre a complexidade do caso médio do hash map, mas este é um ponto muito menor.
Valor pratico
Peso 15%Esta implementação tem alto valor prático como solução de referência. Demonstra as melhores práticas para implementar caches LRU: usando estruturas de dados apropriadas (hash map + lista duplamente ligada), uso adequado de nós sentinela para eliminar casos extremos e separação limpa de métodos auxiliares. O código está pronto para produção e poderia ser usado diretamente em aplicações reais. A verificação defensiva de ValueError adiciona robustez. A implementação serviria como um excelente exemplo educacional para entender como combinar estruturas de dados para atingir requisitos específicos de complexidade de tempo.
Seguimento de instrucoes
Peso 10%A resposta segue todas as instruções precisamente. Fornece uma classe completa chamada exatamente 'LRUCache' com os três métodos exigidos tendo assinaturas corretas. Tanto get quanto put atingem complexidade de tempo média O(1) usando estruturas de dados apropriadas. A sequência de demonstração é executada exatamente como especificado, com saída correta. A explicação da complexidade O(1) é incluída e precisa. Todos os requisitos da política de avaliação são atendidos: saída correta, tratamento adequado de casos extremos (atualização de chaves existentes), uso de estruturas de dados O(1) e código completo executável.
Pontuacao total
Comentario geral
A implementação LRUCache fornecida é excepcionalmente bem estruturada, correta e altamente eficiente. Ela utiliza corretamente uma combinação de um hash map e uma lista duplamente ligada personalizada com nós sentinela para atingir a complexidade de tempo O(1) média necessária tanto para as operações `get` quanto `put`. O código demonstra excelente atenção aos detalhes, incluindo o uso de `__slots__` para a classe `_Node` e tratamento robusto de várias operações de cache, como atualização de chaves existentes e remoção do item menos recentemente usado. A saída da demonstração está perfeitamente correta, e a explicação da complexidade de tempo é clara e precisa.
Ver detalhes da avaliacao ▼
Correcao
Peso 35%A implementação está totalmente correta. Toda a lógica do cache LRU, incluindo recuperação de chave, atualizações, inserções e remoção do item menos recentemente usado, funciona como esperado. A sequência de demonstração fornecida produz a saída correta exata.
Completude
Peso 20%A resposta fornece uma classe `LRUCache` completa com todos os métodos necessários (`__init__`, `get`, `put`), uma demonstração clara de seu uso e uma explicação concisa de sua complexidade de tempo. Nada do que foi solicitado estava faltando.
Qualidade do codigo
Peso 20%A qualidade do código é excelente. É bem organizado com métodos auxiliares para operações de lista ligada, usa nós sentinela para manipulação de lista mais limpa e inclui `__slots__` para eficiência de memória na classe `_Node`. Os nomes das variáveis são descritivos e a estrutura geral é altamente legível e mantenedora.
Valor pratico
Peso 15%Esta implementação é altamente prática e pronta para produção. Ela demonstra um profundo entendimento das estruturas de dados necessárias para um cache LRU, fornecendo uma solução robusta e eficiente. A implementação explícita da lista duplamente ligada personalizada oferece controle total e insights sobre o mecanismo subjacente, tornando-a valiosa em cenários onde `collections.OrderedDict` pode não ser adequado ou onde um entendimento mais profundo é necessário.
Seguimento de instrucoes
Peso 10%Todas as instruções foram seguidas precisamente. A classe é nomeada `LRUCache`, os métodos conformam-se às assinaturas especificadas, a complexidade de tempo O(1) média é alcançada e explicada, a validação de capacidade está presente e a sequência de demonstração, juntamente com sua saída, corresponde exatamente aos requisitos.
Pontuacao total
Comentario geral
Cache LRU bem implementada: comportamento correto, operações eficientes O(1) usando um hash map + lista duplamente ligada, e a demonstração fornecida produz a saída esperada. O código é claro e executável, com pequenas melhorias de estilo/anotação possíveis (por exemplo, mais anotações de tipo ou docstrings), mas nada que afete a correção ou o desempenho.
Ver detalhes da avaliacao ▼
Correcao
Peso 35%A implementação está correta: get e put comportam-se como especificado, as atualizações movem itens para MRU, a evicção remove o LRU quando a capacidade é excedida e a demonstração imprime a sequência esperada (10, -1, -1, 30, 40). Casos extremos como a atualização de uma chave existente e capacidade zero/negativa (ValueError) são tratados.
Completude
Peso 20%A solução inclui uma classe LRUCache completa e executável com __init__, get e put, uma demonstração da sequência de operações exigida e uma explicação concisa da complexidade O(1). Todos os comportamentos exigidos do prompt estão presentes.
Qualidade do codigo
Peso 20%Código limpo e bem estruturado: classe interna Node com __slots__, nós sentinela head/tail e métodos auxiliares claros para operações de lista. Pequenas melhorias de estilo poderiam incluir anotações de tipo adicionais (por exemplo, para self.map) e docstrings/comentários para métodos públicos, mas estes não afetam a correção.
Valor pratico
Peso 15%A implementação é eficiente e prática para uso real: operações médias O(1), design de nó de baixa sobrecarga e semântica clara. Para uso em produção, poder-se-ia adicionar considerações de thread-safety ou tipagem/documentação mais rica, mas a funcionalidade principal é sólida.
Seguimento de instrucoes
Peso 10%Todas as instruções foram seguidas: classe denominada LRUCache fornecida, métodos exigidos implementados com assinaturas corretas, demonstração incluída e a explicação da complexidade O(1) está correta.