Respuesta 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 respuesta 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 ganadores
2 / 3
Puntuacion media
Puntuacion total
Comentario general
Excelente implementación de una caché LRU que cumple plenamente con todos los requisitos. La solución utiliza una combinación bien diseñada de un mapa hash y una lista doblemente enlazada con nodos centinela para lograr una complejidad de tiempo O(1) tanto para las operaciones get como put. El código es limpio, está bien estructurado y maneja correctamente todos los casos extremos, incluida la actualización de claves existentes y la expulsión adecuada. La demostración produce la salida esperada exacta (10, -1, -1, 30, 40), y la explicación de la complejidad O(1) es precisa y clara. El uso de __slots__ en la clase Node demuestra atención a la eficiencia de la memoria. Observaciones menores: el ValueError para una capacidad no positiva es un buen toque defensivo pero no se requería explícitamente; la explicación podría haber sido un poco más detallada sobre por qué las búsquedas en el diccionario son O(1) en promedio. En general, esta es una implementación de calidad de producción.
Ver detalle de evaluacion ▼
Correccion
Peso 35%La implementación es correcta y produce la secuencia de salida esperada exacta (10, -1, -1, 30, 40). Todas las operaciones principales funcionan correctamente: get devuelve los valores correctos y marca los elementos como usados recientemente, put inserta correctamente nuevos elementos y actualiza los existentes, y la expulsión elimina correctamente el elemento menos usado recientemente cuando se excede la capacidad. La lista doblemente enlazada con centinelas mantiene correctamente el orden de recentidad. Se manejan correctamente casos extremos como la actualización de una clave existente. La única deducción menor es que el ValueError para una capacidad no positiva, aunque es una buena práctica, no fue explícitamente requerido por la tarea.
Integridad
Peso 20%La respuesta está completamente completa. Proporciona la clase LRUCache completa con todos los métodos requeridos (__init__, get, put), incluye una demostración completa y funcional con la secuencia de prueba exacta especificada, produce todas las salidas esperadas y concluye con una explicación clara de la complejidad de tiempo O(1). La implementación incluye métodos auxiliares (_remove, _add_to_front, _move_to_front, _evict_lru) que están bien organizados y son necesarios para la solución. Nada falta o está incompleto.
Calidad del codigo
Peso 20%El código es de alta calidad con excelente estructura y legibilidad. El uso de una clase anidada _Node con __slots__ demuestra conciencia de la eficiencia de la memoria. Los nombres de los métodos son descriptivos y siguen las convenciones de Python. La implementación de la lista doblemente enlazada con nodos centinela es elegante y evita casos extremos de comprobación de nulos. Los comentarios explican claramente la disposición de la estructura de datos y el propósito de cada método. El código está bien organizado con una separación lógica de responsabilidades. Menor: el comentario explicativo al final podría ser un poco más detallado sobre la complejidad del caso promedio del mapa hash, pero este es un punto muy menor.
Valor practico
Peso 15%Esta implementación tiene un alto valor práctico como solución de referencia. Demuestra las mejores prácticas para implementar cachés LRU: usar estructuras de datos apropiadas (mapa hash + lista doblemente enlazada), uso adecuado de nodos centinela para eliminar casos extremos y una separación limpia de métodos auxiliares. El código está listo para producción y podría usarse directamente en aplicaciones reales. La comprobación defensiva de ValueError añade robustez. La implementación serviría como un excelente ejemplo educativo para comprender cómo combinar estructuras de datos para lograr requisitos específicos de complejidad de tiempo.
Seguimiento de instrucciones
Peso 10%La respuesta sigue todas las instrucciones con precisión. Proporciona una clase completa llamada exactamente 'LRUCache' con los tres métodos requeridos que tienen las firmas correctas. Tanto get como put logran una complejidad de tiempo promedio O(1) utilizando estructuras de datos apropiadas. La secuencia de demostración se ejecuta exactamente como se especifica con la salida correcta. Se incluye la explicación de la complejidad O(1) y es precisa. Se cumplen todos los requisitos de la política de evaluación: salida correcta, manejo adecuado de casos extremos (actualización de claves existentes), uso de estructuras de datos O(1) y código completo y ejecutable.
Puntuacion total
Comentario general
La implementación de LRUCache proporcionada está excepcionalmente bien estructurada, es correcta y altamente eficiente. Utiliza correctamente una combinación de un mapa hash y una lista doblemente enlazada personalizada con nodos centinela para lograr la complejidad de tiempo promedio O(1) requerida tanto para las operaciones `get` como `put`. El código demuestra una excelente atención al detalle, incluido el uso de `__slots__` para la clase nodo y un manejo robusto de varias operaciones de caché como la actualización de claves existentes y la eliminación del elemento menos utilizado recientemente. La salida de la demostración es perfectamente correcta y la explicación de la complejidad temporal es clara y precisa.
Ver detalle de evaluacion ▼
Correccion
Peso 35%La implementación es completamente correcta. Toda la lógica de la caché LRU, incluida la recuperación de claves, las actualizaciones, las inserciones y la eliminación del elemento menos utilizado recientemente, funciona como se espera. La secuencia de demostración proporcionada produce la salida correcta exacta.
Integridad
Peso 20%La respuesta proporciona una clase `LRUCache` completa con todos los métodos requeridos (`__init__`, `get`, `put`), una demostración clara de su uso y una explicación concisa de su complejidad temporal. No faltaba nada de lo solicitado.
Calidad del codigo
Peso 20%La calidad del código es excelente. Está bien organizado con métodos auxiliares para operaciones de lista enlazada, utiliza nodos centinela para una manipulación de lista más limpia e incluye `__slots__` para la eficiencia de memoria en la clase `_Node`. Los nombres de las variables son descriptivos y la estructura general es muy legible y mantenible.
Valor practico
Peso 15%Esta implementación es muy práctica y está lista para producción. Demuestra una profunda comprensión de las estructuras de datos necesarias para una caché LRU, proporcionando una solución robusta y eficiente. La implementación explícita de una lista doblemente enlazada personalizada ofrece control total y conocimiento del mecanismo subyacente, lo que la hace valiosa en escenarios donde `collections.OrderedDict` podría no ser adecuado o se necesita una comprensión más profunda.
Seguimiento de instrucciones
Peso 10%Se siguieron todas las instrucciones al pie de la letra. La clase se llama `LRUCache`, los métodos se ajustan a las firmas especificadas, se logra y explica la complejidad de tiempo promedio O(1), está presente la validación de capacidad y la secuencia de demostración, junto con su salida, coincide exactamente con los requisitos.
Puntuacion total
Comentario general
Caché LRU bien implementada: comportamiento correcto, operaciones eficientes O(1) usando un mapa hash + lista doblemente enlazada, y la demostración proporcionada produce la salida esperada. El código es claro y ejecutable, con pequeñas mejoras de estilo/anotación posibles (ej. más anotaciones de tipo o docstrings) pero nada que afecte la corrección o el rendimiento.
Ver detalle de evaluacion ▼
Correccion
Peso 35%La implementación es correcta: get y put se comportan como se especifica, las actualizaciones mueven los elementos a MRU, la expulsión elimina el LRU cuando se excede la capacidad, y la demostración imprime la secuencia esperada (10, -1, -1, 30, 40). Se manejan casos extremos como la actualización de una clave existente y la capacidad cero/negativa (ValueError).
Integridad
Peso 20%La solución incluye una clase LRUCache completa y ejecutable con __init__, get y put, una demostración de la secuencia de operaciones requerida y una explicación concisa de la complejidad O(1). Todos los comportamientos requeridos del prompt están presentes.
Calidad del codigo
Peso 20%El código es limpio y está bien estructurado: clase Node interna con __slots__, nodos centinela head/tail y métodos auxiliares claros para operaciones de lista. Las mejoras menores de estilo podrían incluir anotaciones de tipo adicionales (ej. para self.map) y docstrings/comentarios para métodos públicos, pero estos no afectan la corrección.
Valor practico
Peso 15%La implementación es eficiente y práctica para uso real: operaciones promedio O(1), diseño de nodo de baja sobrecarga y semántica clara. Para uso en producción, se podrían agregar consideraciones de seguridad de hilos o tipos/documentos más ricos, pero la funcionalidad principal es sólida.
Seguimiento de instrucciones
Peso 10%Se siguieron todas las instrucciones: se proporcionó la clase llamada LRUCache, se implementaron los métodos requeridos con las firmas correctas, se incluyó la demostración y la explicación de la complejidad O(1) es precisa.