Algorithmen und Datenstrukturen · Middle · Frage 27 von 75
Wie baut man meist einen LRU-Cache mit get und put in O(1)?
- 1Ein Min-Heap, geordnet nach dem Zeitpunkt des Hinzufügens
- 2Eine Hash-Map plus eine doppelt verkettete Liste nach letzter Nutzung
- 3Ein sortiertes Array von Schlüsseln mit binärer Suche
Antwort zeigen
Richtige Antwort: Eine Hash-Map plus eine doppelt verkettete Liste nach letzter Nutzung
Erklärung
Die Map findet einen Knoten per Schlüssel; die Liste verschiebt ihn in O(1) nach vorne und wirft bei Überfüllung das Ende ab. In JavaScript reicht eine Map allein: sie behält die Einfügereihenfolge, also beim Zugriff den Schlüssel löschen und neu setzen und map.keys().next().value verdrängen.