We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

LRU Cache

Difficulty: Medium

Problem Description

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with the following methods:

  • LRUCache(int capacity): Initialize the LRU cache with a positive size capacity.
  • int get(int key): Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value): Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Key Insights

  • An LRU cache evicts the least recently used item when it reaches its capacity.
  • To achieve O(1) time complexity for both get and put operations, we can use a combination of a hash map and a doubly linked list.
  • The hash map provides quick access to cache items, while the doubly linked list maintains the order of usage for the cache items.

Space and Time Complexity

Time Complexity:

  • O(1) for both get and put operations on average.

Space Complexity:

  • O(capacity), since we need to store at most capacity items in the cache.

Solution

To implement the LRU Cache, we will use a hash map (dictionary) for fast access to cache items and a doubly linked list to maintain the order of usage. The most recently used items will be closer to the head of the list, while the least recently used items will be closer to the tail. When we need to add a new item and the cache is full, we will remove the tail item from the list and the hash map.

  1. Initialize a hash map to store key-value pairs.
  2. Use a doubly linked list to track the order of usage.
  3. For the get method, retrieve the value from the hash map and move the corresponding node to the head of the linked list to mark it as recently used.
  4. For the put method, if the key already exists, update its value and move the node to the head. If the key does not exist, add it to the head of the list. If the cache exceeds its capacity, remove the tail node from both the list and the hash map.

Code Solutions

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)  # Dummy head
        self.tail = Node(0, 0)  # Dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add_to_head(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add_to_head(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]
← Back to All Questions