⚡Flashcard Drill➔
NeetCode #338LC-146MediumLinked ListNC 150NC 250
← Back to All Problems

#338 · #146 · LRU Cache(LRU 缓存)

📌 Problem Statement & Constraints

Design a Least Recently Used (LRU) cache with a fixed capacity. Implement get(key) returning the value or -1, and put(key, value). Both must run in O(1) average time. When the capacity is exceeded, evict the least recently used key. Constraints: 1 <= capacity <= 3000; at most 2 * 10^5 calls.

💡 Core Algorithmic Approaches

  1. Two structures are needed: a hash map for O(1) lookup and a doubly linked list for O(1) recency updates.
  2. The list orders keys from most recently used (head) to least recently used (tail).
  3. get and put both move the touched key to the head; when full, put removes the tail.
  4. Python's OrderedDict implements exactly this, with move_to_end and popitem(last=False).

💻 Benchmark Python3 Implementation

class LRUCache:
    def __init__(self, capacity: int):
        from collections import OrderedDict
        self.cap = capacity
        self.d = OrderedDict()             # front = most recently used

    def get(self, key: int) -> int:
        if key not in self.d:
            return -1
        self.d.move_to_end(key)            # mark as recently used
        return self.d[key]

    def put(self, key: int, value: int) -> None:
        if key in self.d:
            self.d.move_to_end(key)        # refresh recency
        self.d[key] = value
        if len(self.d) > self.cap:
            self.d.popitem(last=False)     # evict the least recently used


# From-scratch doubly linked list, if OrderedDict is disallowed
class LRUCache2:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        self.head = {"prev": None, "next": None}   # sentinels
        self.tail = {"prev": self.head, "next": None}
        self.head["next"] = self.tail

    def _remove(self, node):
        node["prev"]["next"] = node["next"]
        node["next"]["prev"] = node["prev"]

    def _add_front(self, node):
        node["next"] = self.head["next"]
        node["prev"] = self.head
        self.head["next"]["prev"] = node
        self.head["next"] = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node["val"]

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = {"key": key, "val": value, "prev": None, "next": None}
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail["prev"]
            self._remove(lru)
            del self.map[lru["key"]]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) per operation for both variants: hash lookup plus a constant number of pointer updates.
💾 Space Complexity
O(capacity).

⚠️ Interview Pitfalls & Follow-ups

  • Using a plain dict: Python dicts preserve insertion order but provide no O(1) way to remove the least recently used entry by recency.
  • Forgetting to refresh recency on put of an existing key: the key would be evicted too early.
  • Evicting before inserting: the size check must happen after the insertion.
  • Using popitem() without last=False: that removes the most recently used item, the opposite of what is needed.
  • Using a singly linked list: removing an arbitrary node (needed for get) requires the previous pointer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems