Resposta A: OpenAI GPT-5 mini
# Implementação de LRU Cache usando um hash map + lista duplamente ligada # - O mapa hash (dict) fornece acesso O(1) de key -> node # - A lista duplamente ligada mantém a ordem de uso: mais recentemente usado na head, menos recentemente usado na tail # - Quando uma chave é acessada ou atualizada, movemos seu nó para a head # - Quando a capacidade é excedida, removemos o nó da tail (LRU) e deletamos sua chave do mapa class _Node: """Nó da lista duplamente ligada para armazenar chave e valor.""" def __init__(self, key=None, value=None): self.key = key self.value = value self.prev =...
Mostrar resposta completa ▼
# Implementação de LRU Cache usando um hash map + lista duplamente ligada # - O mapa hash (dict) fornece acesso O(1) de key -> node # - A lista duplamente ligada mantém a ordem de uso: mais recentemente usado na head, menos recentemente usado na tail # - Quando uma chave é acessada ou atualizada, movemos seu nó para a head # - Quando a capacidade é excedida, removemos o nó da tail (LRU) e deletamos sua chave do mapa class _Node: """Nó da lista duplamente ligada para armazenar chave e valor.""" 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): """Inicializa LRUCache com a capacidade fornecida. Trata capacidades <= 0 tornando o cache efetivamente inutilizável (get retorna -1, put não faz nada). """ self.capacity = max(0, int(capacity)) self.cache = {} # key -> _Node # Nós sentinela para head e tail para evitar checagens de borda self.head = _Node() # O mais recentemente usado vem logo após a head self.tail = _Node() # O menos recentemente usado fica logo antes da tail self.head.next = self.tail self.tail.prev = self.head self.size = 0 # Auxiliar interno: adicionar nó logo após a head (marcar como recentemente usado) def _add_node(self, node: _Node) -> None: node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node # Auxiliar interno: remover um nó existente da lista ligada def _remove_node(self, node: _Node) -> None: prev = node.prev nxt = node.next if prev: prev.next = nxt if nxt: nxt.prev = prev node.prev = node.next = None # Auxiliar interno: mover um nó existente para a head (mais recentemente usado) def _move_to_head(self, node: _Node) -> None: self._remove_node(node) self._add_node(node) # Auxiliar interno: remover (pop) o nó menos recentemente usado (logo antes da tail) def _pop_tail(self) -> _Node: node = self.tail.prev if node is self.head: return None self._remove_node(node) return node def get(self, key: int) -> int: """Retorna o valor associado à chave se presente; caso contrário -1. O acesso marca a chave como recentemente usada. Tempo médio O(1). """ if self.capacity == 0: return -1 node = self.cache.get(key) if not node: return -1 # Move o nó acessado para a head (recentemente usado) self._move_to_head(node) return node.value def put(self, key: int, value: int) -> None: """Insere ou atualiza a chave com o valor. Evicta (remove) o LRU se a capacidade for excedida. Tempo médio O(1). """ if self.capacity == 0: return node = self.cache.get(key) if node: # Atualiza e marca como recentemente usado node.value = value self._move_to_head(node) else: # Insere novo nó new_node = _Node(key, value) self.cache[key] = new_node self._add_node(new_node) self.size += 1 if self.size > self.capacity: # Evicta o nó menos recentemente usado tail_node = self._pop_tail() if tail_node: del self.cache[tail_node.key] self.size -= 1 # Demonstração da implementação com a sequência de teste fornecida if __name__ == "__main__": cache = LRUCache(2) cache.put(1, 10) cache.put(2, 20) print(cache.get(1)) # Esperado: 10 cache.put(3, 30) # Remove a chave 2 print(cache.get(2)) # Esperado: -1 cache.put(4, 40) # Remove a chave 1 print(cache.get(1)) # Esperado: -1 print(cache.get(3)) # Esperado: 30 print(cache.get(4)) # Esperado: 40
Resultado
Votos de vitoria
3 / 3
Pontuacao media
Pontuacao total
Comentario geral
Esta é uma implementação forte e bem estruturada de um cache LRU usando um mapa hash e uma lista duplamente ligada. O código produz corretamente todas as saídas esperadas (10, -1, -1, 30, 40), trata casos-limite como capacidade 0, usa nós sentinela para simplificar as operações na lista e inclui comentários claros ao longo do código. A implementação é limpa, segue as convenções do Python e consegue tempo médio O(1) tanto para get quanto para put. Nota menor: o método get usa 'if not node', o que teoricamente poderia ser problemático se node fosse um valor falsy, mas como nodes são objetos isso é aceitável na prática. O caso-limite capacity=1 é tratado implicitamente e corretamente. No geral, uma resposta de alta qualidade com apenas considerações estilísticas muito menores.
Ver detalhes da avaliacao ▼
Correcao
Peso 35%A implementação produz corretamente todas as cinco saídas esperadas (10, -1, -1, 30, 40). As operações na lista duplamente ligada estão corretas, os nós sentinela previnem bugs em casos-limite e a lógica de expulsão é sólida. Tanto get quanto put têm complexidade média O(1). O caso-limite capacity=0 é tratado. A verificação 'if not node' em get é tecnicamente aceitável, já que nodes são objetos, mas usar 'if node is None' seria mais explícito.
Completude
Peso 20%Todos os componentes exigidos estão presentes: a classe _Node, a classe LRUCache com get e put, helpers internos para manipulação da lista, nós sentinela, tratamento de casos-limite para capacidade 0 e 1, a sequência completa de teste com comentários de saída esperada e um guard main. Nada significativo está faltando.
Qualidade do codigo
Peso 20%O código é limpo, bem organizado e segue as convenções do Python. Os comentários explicam a abordagem geral e cada método. Nós sentinela são uma boa escolha de design. Métodos auxiliares têm nomes claros e único propósito. Anotações de tipo são usadas. Observação pequena: 'if not node' é ligeiramente menos explícito do que 'if node is None', e as verificações de null em _remove_node para prev/nxt são desnecessárias dado que os nós sentinela sempre existem, mas são questões muito menores.
Valor pratico
Peso 15%A implementação é diretamente utilizável em cenários reais. Trata capacidade 0 de forma graciosa, usa uma interface limpa e o design com nós sentinela torna-a robusta. O código é autocontido e executável. Poderia ser estendido facilmente (por exemplo, segurança por threads, TTL). A demonstração mostra claramente o comportamento esperado.
Seguimento de instrucoes
Peso 10%Todas as instruções foram seguidas: não foi usado OrderedDict nem functools.lru_cache, foi implementado mapa hash + lista duplamente ligada, a classe chama-se LRUCache com a interface correta, a sequência de testes está incluída com comentários de saída esperada, casos-limite foram tratados e os comentários explicam a abordagem. O código está completo e executável.
Pontuacao total
Comentario geral
Fornece uma implementação correta e executável de LRUCache usando um dict mais uma lista duplamente ligada com nós sentinela, alcançando complexidade média O(1) para get/put e produzindo as saídas esperadas para o teste fornecido. Inclui comentários claros e trata a capacidade 0 de forma graciosa. Pequenos problemas: _pop_tail está anotado para retornar _Node mas pode retornar None; algumas verificações defensivas em _remove_node são desnecessárias dado o uso de sentinelas, porém não são prejudiciais.
Ver detalhes da avaliacao ▼
Correcao
Peso 35%Comportamento LRU correto: get move os nós para a posição MRU, put atualiza/move chaves existentes e remove o LRU quando ocorre overflow. A sequência de teste fornecida produzirá 10, -1, -1, 30, 40 como esperado. Capacidade 0 é tratada com get=-1 e put sem efeito.
Completude
Peso 20%Inclui a implementação completa da classe, auxiliares internos e a sequência de teste exata solicitada. Os comentários explicam a abordagem e as operações principais. Casos de borda para capacidade 0 são tratados explicitamente; capacidade 1 funciona naturalmente via lógica de evicção.
Qualidade do codigo
Peso 20%O código é limpo, legível e bem estruturado, com nós sentinela para simplificar as operações na lista. Pequenas observações de qualidade: a anotação de retorno de _pop_tail não corresponde ao possível retorno None, e algumas verificações em _remove_node são redundantes com o invariante dos sentinelas.
Valor pratico
Peso 15%Uma implementação de referência prática: operações O(1), evita bibliotecas proibidas e é fácil de adaptar. O código de demonstração é executável tal como está.
Seguimento de instrucoes
Peso 10%Segue todas as instruções: sem OrderedDict/functools, usa hashmap + lista duplamente ligada, inclui comentários explicativos, trata casos de borda (notadamente capacidade 0) e fornece código completo e executável com o teste especificado.
Pontuacao total
Comentario geral
Esta é uma resposta excepcional que fornece uma implementação de cache LRU com qualidade de livro didático. O código está correto, eficiente e excepcionalmente bem estruturado, usando a técnica sofisticada de nós sentinela para simplificar a lógica da lista duplamente ligada. Ele adere perfeitamente a todas as restrições, inclui comentários excelentes, trata os casos de borda com elegância e fornece o caso de teste executável exigido. Serve como uma resposta modelo para esta tarefa.
Ver detalhes da avaliacao ▼
Correcao
Peso 35%A implementação está perfeitamente correta. A lógica tanto para as operações `get` quanto `put` mantém corretamente a ordem de menos recentemente usado e respeita a restrição de capacidade. A sequência de teste fornecida produz a saída exatamente esperada. A complexidade média de tempo O(1) para ambas as operações é alcançada com sucesso pela combinação de um mapa hash e uma lista duplamente ligada. Casos de borda, como capacidade zero, são tratados corretamente.
Completude
Peso 20%A submissão está totalmente completa. Inclui a classe `LRUCache`, a classe auxiliar privada `_Node`, e o bloco de demonstração completo e executável (`if __name__ == "__main__":`) conforme solicitado. Todos os componentes exigidos pelo enunciado foram entregues.
Qualidade do codigo
Peso 20%A qualidade do código é excepcional. O uso de métodos auxiliares privados para manipulação de nós (`_add_node`, `_remove_node`, etc.) torna os métodos principais `get` e `put` limpos e legíveis. A implementação de nós sentinela head e tail é um padrão sofisticado e eficiente que elimina a necessidade de verificações de casos limites na lógica de manipulação da lista. Os comentários são claros, concisos e explicam tanto o quê quanto o porquê da implementação. É uma solução de nível profissional.
Valor pratico
Peso 15%A resposta tem alto valor prático e educacional. É uma implementação clássica, feita do zero, de um algoritmo de cache fundamental amplamente usado em design de sistemas. Este código serve como uma excelente referência para quem precisa entender ou implementar um cache LRU e é uma solução canônica para um problema muito comum em entrevistas de engenharia de software.
Seguimento de instrucoes
Peso 10%A resposta segue meticulosamente cada instrução do enunciado. Implementa corretamente a classe `LRUCache` usando um mapa hash e uma lista duplamente ligada personalizada, evitando explicitamente os proibidos `collections.OrderedDict` e `functools.lru_cache`. O código é executável, comentado e inclui o caso de teste especificado.