Respuesta A: OpenAI GPT-5 mini
# Implementación de caché LRU usando un mapa hash + lista doblemente enlazada # - El mapa hash (dict) proporciona acceso O(1) desde la clave -> nodo # - La lista doblemente enlazada mantiene el orden de uso: el más recientemente usado en head, el menos recientemente usado en tail # - Cuando se accede o actualiza una clave, movemos su nodo a head # - Cuando se excede la capacidad, eliminamos el nodo tail (LRU) y borramos su clave del mapa class _Node: """Nodo de lista doblemente enlazada para contener clave y valor.""" def __init__(self, key=None, value=None): self.key = key self.value = v...
Mostrar respuesta completa ▼
# Implementación de caché LRU usando un mapa hash + lista doblemente enlazada # - El mapa hash (dict) proporciona acceso O(1) desde la clave -> nodo # - La lista doblemente enlazada mantiene el orden de uso: el más recientemente usado en head, el menos recientemente usado en tail # - Cuando se accede o actualiza una clave, movemos su nodo a head # - Cuando se excede la capacidad, eliminamos el nodo tail (LRU) y borramos su clave del mapa class _Node: """Nodo de lista doblemente enlazada para contener clave y 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 con la capacidad dada. Maneja capacidad <= 0 haciendo que la caché sea efectivamente inutilizable (get devuelve -1, put no hace nada). """ self.capacity = max(0, int(capacity)) self.cache = {} # clave -> _Node # Nodos centinela para head y tail para evitar comprobaciones de borde self.head = _Node() # Lo más recientemente usado viene justo después de head self.tail = _Node() # Lo menos recientemente usado está justo antes de tail self.head.next = self.tail self.tail.prev = self.head self.size = 0 # Auxiliar interno: agregar nodo justo después de head (marcar como usado recientemente) 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: eliminar un nodo existente de la lista enlazada 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 un nodo existente a head (más recientemente usado) def _move_to_head(self, node: _Node) -> None: self._remove_node(node) self._add_node(node) # Auxiliar interno: sacar el nodo menos recientemente usado (justo antes de 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: """Devuelve el valor asociado con la clave si está presente; de lo contrario -1. El acceso marca la clave como usada recientemente. Tiempo promedio O(1). """ if self.capacity == 0: return -1 node = self.cache.get(key) if not node: return -1 # Mover el nodo accedido a head (usado recientemente) self._move_to_head(node) return node.value def put(self, key: int, value: int) -> None: """Inserta o actualiza la clave con el valor. Evicta LRU si se excede la capacidad. Tiempo promedio O(1). """ if self.capacity == 0: return node = self.cache.get(key) if node: # Actualizar y marcar como usado recientemente node.value = value self._move_to_head(node) else: # Insertar nuevo nodo new_node = _Node(key, value) self.cache[key] = new_node self._add_node(new_node) self.size += 1 if self.size > self.capacity: # Eliminar el nodo menos recientemente usado tail_node = self._pop_tail() if tail_node: del self.cache[tail_node.key] self.size -= 1 # Demostración de la implementación con la secuencia de prueba dada if __name__ == "__main__": cache = LRUCache(2) cache.put(1, 10) cache.put(2, 20) print(cache.get(1)) # Esperado: 10 cache.put(3, 30) # Elimina la clave 2 print(cache.get(2)) # Esperado: -1 cache.put(4, 40) # Elimina la clave 1 print(cache.get(1)) # Esperado: -1 print(cache.get(3)) # Esperado: 30 print(cache.get(4)) # Esperado: 40
Resultado
Votos ganadores
3 / 3
Puntuacion media
Puntuacion total
Comentario general
Esta es una implementación sólida y bien estructurada de una caché LRU usando un mapa hash y una lista doblemente enlazada. El código produce correctamente todos los resultados esperados (10, -1, -1, 30, 40), maneja casos límite como capacidad 0, utiliza nodos centinela para simplificar las operaciones de la lista e incluye comentarios claros en todo el código. La implementación es limpia, sigue las convenciones de Python y logra tiempo promedio O(1) tanto para get como para put. Nota menor: el método get usa 'if not node' que teóricamente podría ser problemático si node fuera un valor falsy, pero dado que los nodos son objetos esto está bien en la práctica. El caso límite capacity=1 se maneja de forma implícita y correcta. En general, una respuesta de alta calidad con solo consideraciones estilísticas muy menores.
Ver detalle de evaluacion ▼
Correccion
Peso 35%La implementación produce correctamente las cinco salidas esperadas (10, -1, -1, 30, 40). Las operaciones sobre la lista doblemente enlazada son correctas, los nodos centinela evitan errores en casos límite y la lógica de expulsión es sólida. Tanto get como put tienen tiempo promedio O(1). Se maneja el caso límite capacity=0. La comprobación 'if not node' en get es técnicamente correcta dado que los nodos son objetos, pero usar 'if node is None' sería más explícito.
Integridad
Peso 20%Todos los componentes requeridos están presentes: la clase _Node, la clase LRUCache con get y put, auxiliares internos para la manipulación de la lista, nodos centinela, manejo de casos límite para capacidad 0 y 1, la secuencia completa de pruebas con comentarios de salida esperada y un main guard. No falta nada significativo.
Calidad del codigo
Peso 20%El código está limpio, bien organizado y sigue las convenciones de Python. Los comentarios explican el enfoque general y cada método. Los nodos centinela son una buena elección de diseño. Los métodos auxiliares tienen nombres adecuados y están orientados a una sola responsabilidad. Se usan anotaciones de tipo. Nota menor: 'if not node' es algo menos explícito que 'if node is None', y las comprobaciones nulas en _remove_node para prev/nxt son innecesarias dado que los nodos centinela siempre existen, pero son cuestiones muy menores.
Valor practico
Peso 15%La implementación es directamente usable en escenarios reales. Maneja la capacidad 0 con gracia, usa una interfaz limpia y el diseño con nodos centinela la hace robusta. El código es autocontenido y ejecutable. Podría extenderse fácilmente (por ejemplo, seguridad de hilos, TTL). La demostración muestra claramente el comportamiento esperado.
Seguimiento de instrucciones
Peso 10%Se siguen todas las instrucciones: no se usa OrderedDict ni functools.lru_cache, se implementa mapa hash + lista doblemente enlazada, la clase se llama LRUCache con la interfaz correcta, se incluye la secuencia de pruebas con comentarios de salida esperada, se manejan los casos límite y los comentarios explican el enfoque. El código está completo y es ejecutable.
Puntuacion total
Comentario general
Proporciona una implementación correcta y ejecutable de LRUCache usando un dict más una lista doblemente enlazada con nodos centinela, logrando operaciones get/put promedio en O(1) y produciendo las salidas esperadas para la prueba dada. Incluye comentarios claros y maneja la capacidad 0 de forma elegante. Problemas menores: _pop_tail está anotado para devolver _Node pero puede devolver None; algunas comprobaciones defensivas en _remove_node son innecesarias dado el uso de centinelas, pero no son perjudiciales.
Ver detalle de evaluacion ▼
Correccion
Peso 35%Comportamiento LRU correcto: get desplaza nodos a la posición MRU, put actualiza/mueve claves existentes y expulsa el LRU al desbordarse. La secuencia de prueba proporcionada producirá 10, -1, -1, 30, 40 como se espera. La capacidad 0 se maneja con get=-1 y put sin efecto.
Integridad
Peso 20%Incluye la implementación completa de la clase, ayudantes internos y la secuencia de prueba exacta solicitada. Los comentarios explican el enfoque y las operaciones clave. Los casos límite para capacidad 0 se manejan explícitamente; la capacidad 1 funciona de forma natural mediante la lógica de expulsión.
Calidad del codigo
Peso 20%El código está limpio, legible y bien estructurado con nodos centinela para simplificar las operaciones en la lista. Detalles menores de calidad: la anotación de retorno de _pop_tail no coincide con la posible devolución de None, y algunas comprobaciones en _remove_node son redundantes con la invariante de los centinelas.
Valor practico
Peso 15%Una implementación de referencia práctica: operaciones O(1), evita bibliotecas prohibidas y es fácil de adaptar. El código de demostración es ejecutable tal cual.
Seguimiento de instrucciones
Peso 10%Sigue todas las instrucciones: no utiliza OrderedDict/functools, usa tabla hash + lista doblemente enlazada, incluye comentarios explicativos, maneja casos límite (notablemente la capacidad 0) y proporciona código ejecutable completo con la prueba especificada.
Puntuacion total
Comentario general
Esta es una respuesta excepcional que proporciona una implementación de caché LRU de calidad de libro de texto. El código es correcto, eficiente y extraordinariamente bien estructurado, utilizando la técnica sofisticada de nodos centinela para simplificar la lógica de la lista doblemente enlazada. Cumple perfectamente con todas las restricciones, incluye comentarios excelentes, maneja los casos límite con elegancia y proporciona el caso de prueba ejecutable requerido. Sirve como una respuesta modelo para esta tarea.
Ver detalle de evaluacion ▼
Correccion
Peso 35%La implementación es perfectamente correcta. La lógica tanto para las operaciones `get` como `put` mantiene correctamente el orden de menos recientemente usado y respeta la restricción de capacidad. La secuencia de prueba proporcionada produce la salida exacta esperada. La complejidad temporal promedio O(1) para ambas operaciones se consigue con éxito mediante la combinación de un mapa hash y una lista doblemente enlazada. Los casos límite, como una capacidad de 0, se manejan correctamente.
Integridad
Peso 20%La entrega está completamente completa. Incluye la clase `LRUCache`, la clase auxiliar privada `_Node`, y el bloque de demostración completo y ejecutable (`if __name__ == "__main__":`) según lo solicitado. Se han entregado todos los componentes requeridos por el enunciado.
Calidad del codigo
Peso 20%La calidad del código es excepcional. El uso de métodos auxiliares privados para la manipulación de nodos (`_add_node`, `_remove_node`, etc.) hace que los métodos principales `get` y `put` sean limpios y fáciles de leer. La implementación de nodos centinela head y tail es un patrón sofisticado y eficiente que elimina la necesidad de comprobaciones de casos extremos dentro de la lógica de manipulación de la lista. Los comentarios son claros, concisos y explican tanto el qué como el porqué de la implementación. Es una solución de nivel profesional.
Valor practico
Peso 15%La respuesta tiene un alto valor práctico y educativo. Es una implementación clásica, desde cero, de un algoritmo de caché fundamental y ampliamente usado en diseño de sistemas. Este código sirve como una referencia excelente para quien necesite entender o implementar una caché LRU y es una solución canónica para un problema de entrevista de ingeniería de software muy común.
Seguimiento de instrucciones
Peso 10%La respuesta sigue meticulosamente cada instrucción del enunciado. Implementa correctamente la clase `LRUCache` usando un mapa hash y una lista doblemente enlazada personalizada, evitando explícitamente las prohibiciones sobre `collections.OrderedDict` y `functools.lru_cache`. El código es ejecutable, está comentado e incluye el caso de prueba especificado (`if __name__ == "__main__":`).