Reponse A: OpenAI GPT-5.2
class _Node: __slots__ = ("key", "value", "prev", "next") 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): if not isinstance(capacity, int) or capacity <= 0: raise ValueError("capacity must be a positive integer") self.capacity = capacity self.map = {} # key -> _Node # Dummy head/tail to avoid edge cases. # Most-recent is right after head. Least-recent is right before tail. self.head = _Node()...
Afficher la reponse complete ▼
class _Node: __slots__ = ("key", "value", "prev", "next") 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): if not isinstance(capacity, int) or capacity <= 0: raise ValueError("capacity must be a positive integer") self.capacity = capacity self.map = {} # key -> _Node # Dummy head/tail to avoid edge cases. # Most-recent is right after head. Least-recent is right before tail. self.head = _Node() self.tail = _Node() self.head.next = self.tail self.tail.prev = self.head def _add_to_front(self, node: _Node) -> None: node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def _remove(self, node: _Node) -> None: node.prev.next = node.next node.next.prev = node.prev node.prev = None node.next = None def _move_to_front(self, node: _Node) -> None: self._remove(node) self._add_to_front(node) def _evict_lru(self) -> None: 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.value def put(self, key: int, value: int) -> None: node = self.map.get(key) if node is not None: node.value = value self._move_to_front(node) return new_node = _Node(key, value) self.map[key] = new_node self._add_to_front(new_node) if len(self.map) > self.capacity: self._evict_lru() # Demonstration 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
Resultat
Votes gagnants
3 / 3
Score moyen
Score total
Commentaire global
La soumission est exceptionnelle. Elle fournit une implémentation correcte, efficace et de haute qualité d'un cache LRU à partir de zéro. Le code utilise l'approche classique et optimale d'une table de hachage combinée à une liste doublement chaînée. L'implémentation est robuste, comportant des nœuds sentinelles de tête/queue pour simplifier les cas limites, et démontre d'excellentes pratiques de codage comme des méthodes auxiliaires et des indications de type. Elle respecte pleinement toutes les exigences et contraintes de la tâche.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%L'implémentation est parfaitement correcte. Elle utilise avec succès une table de hachage pour des recherches en O(1) et une liste doublement chaînée pour maintenir l'ordre d'utilisation. La logique pour `get`, `put`, et l'éviction fonctionne sans faille, et le code de démonstration fourni produit le résultat attendu exact.
Completude
Poids 20%La solution est entièrement complète. Elle fournit une classe `LRUCache` autonome, une classe auxiliaire privée `_Node`, et le code de démonstration exact demandé dans l'énoncé. Toutes les fonctionnalités requises sont implémentées.
Qualite du code
Poids 20%La qualité du code est excellente. Il est bien structuré avec des méthodes auxiliaires claires, à responsabilité unique (_add_to_front, _remove, etc.) qui améliorent la lisibilité. L'utilisation de nœuds sentinelles de tête/queue est une technique sophistiquée qui simplifie la logique de la liste chaînée. L'inclusion d'indications de type, de `__slots__`, et de validation d'entrée pour la capacité démontre des pratiques de codage solides et professionnelles.
Valeur pratique
Poids 15%La solution a une grande valeur pratique. Elle fournit une implémentation efficace, typique d'un manuel, d'une structure de données fondamentale et largement utilisée. Ce code pourrait être utilisé dans des applications réelles et sert d'excellente référence sur la façon de construire un cache LRU à partir de zéro.
Respect des consignes
Poids 10%La solution respecte parfaitement toutes les instructions. Elle implémente correctement le cache LRU à partir de zéro sans utiliser de bibliothèques interdites comme `collections.OrderedDict`. Elle atteint la complexité temporelle moyenne requise en O(1) pour ses opérations principales et inclut la démonstration obligatoire.
Score total
Commentaire global
Excellente implémentation d'un Cache LRU. La solution utilise correctement une liste doublement chaînée combinée à une table de hachage pour atteindre une complexité temporelle moyenne de O(1) pour les opérations get et put. Le code évite les constructions interdites (OrderedDict, functools.lru_cache), gère correctement tous les cas limites et produit exactement la sortie attendue. L'utilisation de nœuds sentinelles de tête/queue factices est une approche propre qui élimine les cas limites. Le code est bien structuré, utilise __slots__ pour l'efficacité mémoire, inclut la validation des entrées et est clairement commenté. La démonstration correspond exactement à la sortie requise.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%L'implémentation est entièrement correcte. La liste doublement chaînée avec des sentinelles factices suit correctement la récence, get déplace les nœuds accédés vers le début, put gère les cas d'insertion et de mise à jour, l'éviction supprime le nœud tail.prev (LRU), et toutes les sorties de démonstration correspondent aux valeurs attendues (10, -1, -1, 30, 40).
Completude
Poids 20%La solution est entièrement complète : elle inclut la classe LRUCache avec toutes les méthodes requises (constructeur, get, put), les méthodes privées auxiliaires, la classe _Node, la validation des entrées et le code de démonstration complet tel que spécifié dans la tâche.
Qualite du code
Poids 20%La qualité du code est excellente. L'utilisation de __slots__ sur _Node témoigne d'une attention à l'efficacité mémoire. Les méthodes d'aide privées (_add_to_front, _remove, _move_to_front, _evict_lru) sont bien nommées et n'ont qu'un seul objectif. Des indications de type sont utilisées. Les commentaires expliquent la conception du nœud sentinelle. Le code est propre et lisible.
Valeur pratique
Poids 15%L'implémentation est très pratique. Elle inclut la validation des entrées avec un message d'erreur significatif, utilise __slots__ pour la performance, et la conception est extensible. Le seul petit défaut est qu'elle ne gère pas la sécurité des threads, mais cela n'était pas requis par la tâche.
Respect des consignes
Poids 10%Toutes les instructions sont suivies à la lettre : aucune utilisation d'OrderedDict ou de functools.lru_cache, complexité O(1) atteinte via table de hachage + liste doublement chaînée, la structure de données sous-jacente est implémentée manuellement, et le code de démonstration exact de la tâche est inclus avec des commentaires de sortie attendue corrects.
Score total
Commentaire global
Cette réponse fournit une implémentation Python correcte, efficace et autonome d'un cache LRU utilisant une table de hachage et une liste doublement chaînée. Elle respecte les opérations O(1) requises, gère correctement la capacité et l'éviction, et inclut la démonstration demandée qui afficherait les sorties attendues. Le code est propre et lisible ; les problèmes mineurs se limitent à de petits points de style (par exemple, le nom 'map' masque un élément intégré et il n'y a pas de docstrings), mais ceux-ci n'affectent pas la correction ou les performances.
Afficher le detail de l evaluation ▼
Exactitude
Poids 35%Implémente correctement LRU en utilisant une table de hachage + une liste doublement chaînée. get et put fonctionnent en temps moyen O(1), la logique d'éviction est correcte et la démonstration fournie produira les sorties attendues.
Completude
Poids 20%Toutes les fonctionnalités requises sont présentes : constructeur avec validation de capacité, sémantiques get et put, éviction LRU lorsque la capacité est dépassée, aucune utilisation de OrderedDict ou functools.lru_cache, et la démonstration demandée est incluse.
Qualite du code
Poids 20%Le code est bien structuré, clair et utilise des têtes/queues factices pour simplifier les opérations de liste. Les méthodes sont petites et ciblées. Petits détails de style : le nom d'attribut 'map' masque un élément intégré et il n'y a pas de docstrings, mais cela n'affecte pas la correction.
Valeur pratique
Poids 15%L'implémentation est pratique et prête à être utilisée dans du code réel : efficace, sûre (valide la capacité) et économe en mémoire (utilise __slots__). Elle bénéficierait de petits ajouts comme des docstrings ou des tests unitaires, mais elle est fonctionnellement complète.
Respect des consignes
Poids 10%Suit les instructions à la lettre : n'utilise pas de bibliothèques interdites, implémente manuellement les structures de données requises, garantit les opérations O(1) et inclut la démonstration exacte avec les résultats imprimés attendus.