Antwort A: OpenAI GPT-5 mini
Zielsprache: de Antwort: # LRU-Cache-Implementierung unter Verwendung einer Hashmap + doppelt verketteten Liste # - Hashmap (dict) bietet O(1)-Zugriff von Schlüssel -> Knoten # - Die doppelt verkettete Liste hält die Nutzungsreihenfolge: am häufigsten verwendet direkt nach head, am wenigsten verwendet vor tail # - Wenn auf einen Schlüssel zugegriffen oder er aktualisiert wird, verschieben wir dessen Knoten an den head # - Wenn die Kapazität überschritten wird, entfernen wir den tail-Knoten (LRU) und löschen seinen Schlüssel aus der Map class _Node: """Knoten der doppelt verketteten Liste zur Speicherung von...
Vollstandige Antwort anzeigen ▼
Zielsprache: de Antwort: # LRU-Cache-Implementierung unter Verwendung einer Hashmap + doppelt verketteten Liste # - Hashmap (dict) bietet O(1)-Zugriff von Schlüssel -> Knoten # - Die doppelt verkettete Liste hält die Nutzungsreihenfolge: am häufigsten verwendet direkt nach head, am wenigsten verwendet vor tail # - Wenn auf einen Schlüssel zugegriffen oder er aktualisiert wird, verschieben wir dessen Knoten an den head # - Wenn die Kapazität überschritten wird, entfernen wir den tail-Knoten (LRU) und löschen seinen Schlüssel aus der Map class _Node: """Knoten der doppelt verketteten Liste zur Speicherung von Schlüssel und Wert.""" 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): """Initialisiert LRUCache mit gegebener Kapazität. Behandelt capacity <= 0, indem der Cache effektiv unbrauchbar gemacht wird (get gibt -1 zurück, put macht nichts). """ self.capacity = max(0, int(capacity)) self.cache = {} # key -> _Node # Sentinel-Knoten für head und tail, um Randfälle zu vermeiden self.head = _Node() # Am häufigsten verwendete kommen direkt nach head self.tail = _Node() # Am wenigsten häufig verwendete ist direkt vor tail self.head.next = self.tail self.tail.prev = self.head self.size = 0 # Interner Helfer: Knoten direkt nach head einfügen (als kürzlich verwendet markieren) 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 # Interner Helfer: einen vorhandenen Knoten aus der verketteten Liste entfernen 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 # Interner Helfer: einen vorhandenen Knoten an den head verschieben (am häufigsten verwendet) def _move_to_head(self, node: _Node) -> None: self._remove_node(node) self._add_node(node) # Interner Helfer: den am wenigsten kürzlich verwendeten Knoten entfernen (direkt vor 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: """Gibt den mit dem Schlüssel verknüpften Wert zurück, falls vorhanden; andernfalls -1. Der Zugriff markiert den Schlüssel als kürzlich verwendet. Durchschnittliche Zeit O(1). """ if self.capacity == 0: return -1 node = self.cache.get(key) if not node: return -1 # Verschiebe den aufgerufenen Knoten an den head (kürzlich verwendet) self._move_to_head(node) return node.value def put(self, key: int, value: int) -> None: """Fügt einen Schlüssel mit Wert ein oder aktualisiert ihn. Entfernt LRU, wenn die Kapazität überschritten wird. Durchschnittliche Zeit O(1). """ if self.capacity == 0: return node = self.cache.get(key) if node: # Aktualisieren und als kürzlich verwendet markieren node.value = value self._move_to_head(node) else: # Neuen Knoten einfügen new_node = _Node(key, value) self.cache[key] = new_node self._add_node(new_node) self.size += 1 if self.size > self.capacity: # Am wenigsten kürzlich verwendeten Knoten entfernen tail_node = self._pop_tail() if tail_node: del self.cache[tail_node.key] self.size -= 1 # Demonstration der Implementierung mit der gegebenen Testsequenz if __name__ == "__main__": cache = LRUCache(2) cache.put(1, 10) cache.put(2, 20) print(cache.get(1)) # Erwartet: 10 cache.put(3, 30) # Entfernt Schlüssel 2 print(cache.get(2)) # Erwartet: -1 cache.put(4, 40) # Entfernt Schlüssel 1 print(cache.get(1)) # Erwartet: -1 print(cache.get(3)) # Erwartet: 30 print(cache.get(4)) # Erwartet: 40
Ergebnis
Siegstimmen
3 / 3
Durchschnittsscore
Gesamtpunktzahl
Gesamtkommentar
Dies ist eine starke, gut strukturierte Implementierung eines LRU-Cache unter Verwendung einer Hashmap und einer doppelt verketteten Liste. Der Code liefert korrekt alle erwarteten Ausgaben (10, -1, -1, 30, 40), behandelt Randfälle wie capacity 0, verwendet Sentinel-Knoten zur Vereinfachung der Listenoperationen und enthält durchgehend klare Kommentare. Die Implementierung ist sauber, folgt den Python-Konventionen und erreicht durchschnittlich O(1)-Zeit für sowohl get als auch put. Kleine Anmerkung: die get-Methode verwendet 'if not node', was theoretisch problematisch sein könnte, falls node einen falsy-Wert hätte, aber da nodes Objekte sind, ist das in der Praxis unproblematisch. Der edge case capacity=1 wird implizit und korrekt behandelt. Insgesamt eine qualitativ hochwertige Antwort mit nur sehr kleinen stilistischen Anmerkungen.
Bewertungsdetails anzeigen ▼
Korrektheit
Gewichtung 35%Die Implementierung liefert korrekt alle fünf erwarteten Ausgaben (10, -1, -1, 30, 40). Die Operationen auf der doppelt verketteten Liste sind korrekt, Sentinel-Knoten verhindern Randfallfehler, und die Eviktionslogik ist stimmig. Sowohl get als auch put haben durchschnittlich O(1)-Laufzeit. Der Randfall capacity=0 wird behandelt. Die 'if not node'-Prüfung in get ist technisch in Ordnung, da nodes Objekte sind, aber 'if node is None' wäre expliziter.
Vollstandigkeit
Gewichtung 20%Alle erforderlichen Komponenten sind vorhanden: die _Node-Klasse, die LRUCache-Klasse mit get und put, interne Hilfsfunktionen zur Listenmanipulation, Sentinel-Knoten, Randfallbehandlung für capacity 0 und 1, die vollständige Testsequenz mit erwarteten Ausgabe-Kommentaren und ein main-Guard. Nichts Bedeutendes fehlt.
Codequalitat
Gewichtung 20%Der Code ist sauber, gut organisiert und folgt den Python-Konventionen. Kommentare erklären den Gesamtansatz und jede Methode. Sentinel-Knoten sind eine gute Designwahl. Hilfsmethoden sind treffend benannt und haben jeweils eine einzige Aufgabe. Type-Hinweise werden verwendet. Kleiner Punkt: 'if not node' ist etwas weniger explizit als 'if node is None', und die Nullprüfungen im _remove_node für prev/nxt sind angesichts vorhandener Sentinel-Knoten unnötig, aber das sind sehr kleine Probleme.
Praktischer Nutzen
Gewichtung 15%Die Implementierung ist direkt in realen Szenarien einsetzbar. Sie behandelt capacity 0 korrekt, bietet eine saubere Schnittstelle, und das Design mit Sentinel-Knoten macht sie robust. Der Code ist selbstständig und ausführbar. Er lässt sich leicht erweitern (z. B. Thread-Sicherheit, TTL). Die Demonstration zeigt deutlich das erwartete Verhalten.
Befolgung der Anweisungen
Gewichtung 10%Alle Anweisungen werden befolgt: Es wird kein OrderedDict oder functools.lru_cache verwendet, Hashmap + doppelt verkettete Liste sind implementiert, die Klasse heißt LRUCache und hat die korrekte Schnittstelle, die Testsequenz ist mit erwarteten Ausgabe-Kommentaren enthalten, Randfälle werden behandelt, und Kommentare erläutern den Ansatz. Der Code ist vollständig und ausführbar.
Gesamtpunktzahl
Gesamtkommentar
Bietet eine korrekte, ausführbare LRUCache-Implementierung, die ein dict plus eine doppelt verkettete Liste mit Sentinelknoten nutzt, erreicht O(1) durchschnittlich für get/put und liefert die erwarteten Ausgaben für den gegebenen Test. Enthält klare Kommentare und behandelt die Kapazität 0 elegant. Kleinere Probleme: _pop_tail ist mit Rückgabetyp _Node annotiert, kann aber None zurückgeben; einige defensive Überprüfungen in _remove_node sind angesichts der Verwendung von Sentineln überflüssig, aber nicht schädlich.
Bewertungsdetails anzeigen ▼
Korrektheit
Gewichtung 35%Korrektes LRU-Verhalten: get bewegt Knoten in die MRU-Position, put aktualisiert/bewegt vorhandene Schlüssel und entfernt beim Überlauf das LRU-Element. Die gegebene Testsequenz gibt wie erwartet 10, -1, -1, 30, 40 aus. Kapazität 0 wird so behandelt, dass get = -1 ergibt und put keine Wirkung hat.
Vollstandigkeit
Gewichtung 20%Enthält die vollständige Klassenimplementierung, interne Hilfsfunktionen und die exakt angeforderte Testsequenz. Die Kommentare erklären den Ansatz und die wichtigsten Operationen. Randfälle für Kapazität 0 werden explizit behandelt; Kapazität 1 funktioniert auf natürliche Weise durch die Eviktionslogik.
Codequalitat
Gewichtung 20%Der Code ist sauber, lesbar und gut strukturiert, mit Sentinelknoten zur Vereinfachung der Listenoperationen. Kleine Qualitätskritikpunkte: Die Rückgabeannotation von _pop_tail stimmt nicht mit der möglichen Rückgabe von None überein, und einige Prüfungen in _remove_node sind durch das Sentinel-Invariant redundant.
Praktischer Nutzen
Gewichtung 15%Eine praktische Referenzimplementierung: O(1)-Operationen, vermeidet verbotene Bibliotheken und ist leicht anpassbar. Der Demo-Code ist sofort ausführbar.
Befolgung der Anweisungen
Gewichtung 10%Folgt allen Anweisungen: kein OrderedDict/functools, verwendet hashmap + doppelt verkettete Liste, enthält erläuternde Kommentare, behandelt Randfälle (insbesondere Kapazität 0) und liefert vollständigen, ausführbaren Code mit dem angegebenen Test.
Gesamtpunktzahl
Gesamtkommentar
Dies ist eine hervorragende Antwort, die eine mustergültige Implementierung eines LRU-Cache liefert. Der Code ist korrekt, effizient und außerordentlich gut strukturiert; er verwendet die ausgefeilte Technik von Sentinel-Knoten, um die Logik der doppeltverketteten Liste zu vereinfachen. Er hält alle Vorgaben perfekt ein, enthält ausgezeichnete Kommentare, behandelt Randfälle elegant und liefert den geforderten ausführbaren Testfall. Sie dient als Modellantwort für diese Aufgabe.
Bewertungsdetails anzeigen ▼
Korrektheit
Gewichtung 35%Die Implementierung ist vollkommen korrekt. Die Logik für sowohl `get` als auch `put` Operationen erhält korrekt die Least-Recently-Used-Reihenfolge und hält die Kapazitätsbeschränkung ein. Die bereitgestellte Testsequenz erzeugt exakt die erwartete Ausgabe. Die durchschnittliche O(1)-Zeitkomplexität für beide Operationen wird erfolgreich durch die Kombination aus Hashmap und doppelt verketteter Liste erreicht. Randfälle, wie eine Kapazität von 0, werden korrekt behandelt.
Vollstandigkeit
Gewichtung 20%Die Einreichung ist vollständig. Sie enthält die Klasse `LRUCache`, die private Hilfsklasse `_Node` und den vollständigen, ausführbaren Demonstrationsblock (`if __name__ == "__main__":`) wie gefordert. Alle erforderlichen Komponenten der Aufgabenstellung wurden geliefert.
Codequalitat
Gewichtung 20%Die Codequalität ist außergewöhnlich. Der Einsatz privater Hilfsmethoden zur Knotemanipulation (`_add_node`, `_remove_node` usw.) macht die Hauptmethoden `get` und `put` sauber und gut lesbar. Die Implementierung von Sentinel-Head- und Tail-Knoten ist ein ausgefeiltes und effizientes Muster, das die Notwendigkeit von Sonderfallprüfungen innerhalb der Listenmanipulationslogik eliminiert. Die Kommentare sind klar, prägnant und erklären sowohl das Was als auch das Warum der Implementierung. Es ist eine Lösung von professionellem Niveau.
Praktischer Nutzen
Gewichtung 15%Die Antwort hat hohen praktischen und didaktischen Wert. Es ist eine klassische, von Grund auf neu implementierte Umsetzung eines fundamentalen Caching-Algorithmus, der in der Systemarchitektur weit verbreitet ist. Dieser Code dient als ausgezeichnete Referenz für alle, die einen LRU-Cache verstehen oder implementieren müssen, und ist eine kanonische Lösung für ein sehr häufiges Interviewproblem in der Softwareentwicklung.
Befolgung der Anweisungen
Gewichtung 10%Die Antwort folgt akribisch jeder Anweisung in der Aufgabenstellung. Sie implementiert korrekt die Klasse `LRUCache` unter Verwendung einer Hashmap und einer eigenen doppelt verketteten Liste, wobei ausdrücklich die verbotenen `collections.OrderedDict` und `functools.lru_cache` vermieden werden. Der Code ist ausführbar, kommentiert und enthält den angegebenen Testfall.