Reponse 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...
Afficher la reponse complete ▼
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.
Resultat
Votes gagnants
2 / 3
Score moyen
Score total
Commentaire global
Excellente implémentation d'un cache LRU qui répond entièrement aux exigences. La solution utilise une combinaison bien conçue d'une table de hachage et d'une liste doublement chaînée avec des nœuds sentinelles pour atteindre une complexité temporelle O(1) pour les opérations get et put. Le code est propre, bien structuré et gère correctement tous les cas limites, y compris la mise à jour des clés existantes et l'éviction appropriée. La démonstration produit la sortie attendue exacte (10, -1, -1, 30, 40), et l'explication de la complexité O(1) est précise et claire. L'utilisation de __slots__ dans la classe Node témoigne de l'attention portée à l'efficacité de la mémoire. Observations mineures : la ValueError pour une capacité non positive est une touche défensive appréciable mais n'était pas explicitement requise ; l'explication aurait pu être légèrement plus détaillée sur la raison pour laquelle les recherches dans le dictionnaire sont en moyenne O(1). Dans l'ensemble, il s'agit d'une implémentation de qualité de production.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%L'implémentation est correcte et produit la séquence de sortie exacte attendue (10, -1, -1, 30, 40). Toutes les opérations principales fonctionnent correctement : get renvoie les valeurs correctes et marque les éléments comme récemment utilisés, put insère correctement de nouveaux éléments et met à jour ceux existants, et l'éviction supprime correctement l'élément le moins récemment utilisé lorsque la capacité est dépassée. La liste doublement chaînée avec sentinelles maintient correctement l'ordre de récence. Les cas limites tels que la mise à jour d'une clé existante sont gérés correctement. La seule déduction mineure est que la ValueError pour une capacité non positive, bien que bonne pratique, n'était pas explicitement requise par la tâche.
Completude
Poids 20%La réponse est entièrement complète. Elle fournit la classe LRUCache entière avec toutes les méthodes requises (__init__, get, put), comprend une démonstration fonctionnelle complète avec la séquence de test exacte spécifiée, produit toutes les sorties attendues et se termine par une explication claire de la complexité temporelle O(1). L'implémentation inclut des méthodes d'aide (_remove, _add_to_front, _move_to_front, _evict_lru) qui sont bien organisées et nécessaires à la solution. Rien n'est manquant ou incomplet.
Qualite du code
Poids 20%Le code est de haute qualité avec une excellente structure et lisibilité. L'utilisation d'une classe imbriquée _Node avec __slots__ démontre une conscience de l'efficacité de la mémoire. Les noms de méthodes sont descriptifs et suivent les conventions Python. L'implémentation de la liste doublement chaînée avec des nœuds sentinelles est élégante et évite les cas limites de vérification de nullité. Les commentaires expliquent clairement la disposition de la structure de données et le but de chaque méthode. Le code est bien organisé avec une séparation logique des préoccupations. Mineur : le commentaire d'explication à la fin pourrait être légèrement plus détaillé sur la complexité du cas moyen de la table de hachage, mais c'est un point très mineur.
Valeur pratique
Poids 15%Cette implémentation a une grande valeur pratique en tant que solution de référence. Elle démontre les meilleures pratiques pour implémenter des caches LRU : utilisation de structures de données appropriées (table de hachage + liste doublement chaînée), utilisation correcte des nœuds sentinelles pour éliminer les cas limites, et séparation claire des méthodes d'aide. Le code est prêt pour la production et pourrait être utilisé directement dans des applications réelles. La vérification défensive de ValueError ajoute de la robustesse. L'implémentation servirait d'excellent exemple éducatif pour comprendre comment combiner des structures de données pour atteindre des exigences de complexité temporelle spécifiques.
Respect des consignes
Poids 10%La réponse suit toutes les instructions à la lettre. Elle fournit une classe complète nommée exactement 'LRUCache' avec les trois méthodes requises ayant les signatures correctes. Les opérations get et put atteignent une complexité temporelle moyenne O(1) en utilisant des structures de données appropriées. La séquence de démonstration est exécutée exactement comme spécifié avec une sortie correcte. L'explication de la complexité O(1) est incluse et précise. Toutes les exigences de la politique de jugement sont satisfaites : sortie correcte, gestion appropriée des cas limites (mise à jour des clés existantes), utilisation de structures de données O(1) et code exécutable complet.
Score total
Commentaire global
L'implémentation de LRUCache fournie est exceptionnellement bien structurée, correcte et très efficace. Elle utilise correctement une combinaison d'une table de hachage et d'une liste doublement chaînée personnalisée avec des nœuds sentinelles pour atteindre la complexité temporelle moyenne O(1) requise pour les opérations `get` et `put`. Le code démontre une excellente attention aux détails, y compris l'utilisation de `__slots__` pour la classe de nœud et une gestion robuste des diverses opérations de cache telles que la mise à jour des clés existantes et l'éviction de l'élément le moins récemment utilisé. La sortie de démonstration est parfaitement correcte et l'explication de la complexité temporelle est claire et précise.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%L'implémentation est entièrement correcte. Toute la logique du cache LRU, y compris la récupération des clés, les mises à jour, les insertions et l'éviction de l'élément le moins récemment utilisé, fonctionne comme prévu. La séquence de démonstration fournie produit la sortie correcte exacte.
Completude
Poids 20%La réponse fournit une classe `LRUCache` complète avec toutes les méthodes requises (`__init__`, `get`, `put`), une démonstration claire de son utilisation et une explication concise de sa complexité temporelle. Rien de ce qui était demandé n'a été omis.
Qualite du code
Poids 20%La qualité du code est excellente. Il est bien organisé avec des méthodes d'assistance pour les opérations de liste chaînée, utilise des nœuds sentinelles pour une manipulation plus propre de la liste et inclut `__slots__` pour l'efficacité mémoire dans la classe `_Node`. Les noms de variables sont descriptifs et la structure globale est très lisible et maintenable.
Valeur pratique
Poids 15%Cette implémentation est très pratique et prête pour la production. Elle démontre une profonde compréhension des structures de données requises pour un cache LRU, fournissant une solution robuste et efficace. L'implémentation explicite de la liste doublement chaînée personnalisée offre un contrôle total et un aperçu du mécanisme sous-jacent, ce qui la rend précieuse dans les scénarios où `collections.OrderedDict` pourrait ne pas convenir ou lorsque une compréhension plus approfondie est nécessaire.
Respect des consignes
Poids 10%Toutes les instructions ont été suivies à la lettre. La classe est nommée `LRUCache`, les méthodes respectent les signatures spécifiées, la complexité temporelle moyenne O(1) est atteinte et expliquée, la validation de la capacité est présente, et la séquence de démonstration, ainsi que sa sortie, correspondent exactement aux exigences.
Score total
Commentaire global
Cache LRU bien implémentée : comportement correct, opérations O(1) efficaces utilisant une table de hachage + liste doublement chaînée, et la démonstration fournie produit le résultat attendu. Le code est clair et exécutable, avec des améliorations stylistiques/d'annotation mineures possibles (par exemple, plus d'annotations de type ou de docstrings) mais rien qui n'affecte la correction ou les performances.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%L'implémentation est correcte : get et put se comportent comme spécifié, les mises à jour déplacent les éléments vers MRU, l'éviction supprime le LRU lorsque la capacité est dépassée, et la démonstration imprime la séquence attendue (10, -1, -1, 30, 40). Les cas limites comme la mise à jour d'une clé existante et la capacité nulle/négative (ValueError) sont gérés.
Completude
Poids 20%La solution inclut une classe LRUCache complète et exécutable avec __init__, get et put, une démonstration de la séquence d'opérations requise, et une explication concise de la complexité O(1). Tous les comportements requis de l'énoncé sont présents.
Qualite du code
Poids 20%Code propre et bien structuré : classe Node interne avec __slots__, nœuds sentinelles head/tail, et méthodes d'aide claires pour les opérations sur la liste. Des améliorations stylistiques mineures pourraient inclure des annotations de type supplémentaires (par exemple, pour self.map) et des docstrings/commentaires pour les méthodes publiques, mais celles-ci n'affectent pas la correction.
Valeur pratique
Poids 15%L'implémentation est efficace et pratique pour une utilisation réelle : opérations O(1) en moyenne, faible surcharge de la conception des nœuds, et sémantique claire. Pour une utilisation en production, on pourrait ajouter des considérations de sécurité des threads ou une typographie/documentation plus riche, mais la fonctionnalité de base est solide.
Respect des consignes
Poids 10%Toutes les instructions ont été suivies : la classe nommée LRUCache a été fournie, les méthodes requises ont été implémentées avec des signatures correctes, une démonstration a été incluse, et l'explication de la complexité O(1) est exacte.