LRU Cache

LRU Cache Implementation

Problem

Design a data structure that implements a Least Recently Used (LRU) cache.

The LRUCache class should have:

• LRUCache(int capacity): Initializes the cache with a positive capacity.
• int get(int key): Returns the value associated with the key. Return -1 if the key does not exist.
• void put(int key, int value): Updates the value if the key exists. Otherwise, insert the key-value pair. If inserting causes the cache to exceed the capacity, evict the least recently used key.

The get and put operations must run in O(1) time on average.

Naive Approach

A simple approach would be to use a dictionary (hash map) to store the key-value pairs and an array or list to keep track of the order in which keys are accessed. When a get or put operation is performed, the list is updated to reflect the most recently used item. When the capacity is exceeded, the least recently used item (located at the start of the list) is removed.

• Time Complexity: get - O(n) to search for the key in the list and update the order. put - O(n) in the worst case if shifting elements after eviction. O(1) for dictionary access.
• Space Complexity: O(capacity), where capacity is the maximum number of items the cache can hold.

This approach does not meet the O(1) average time complexity requirement.

Optimal Approach

The optimal approach utilizes a combination of a hash map and a doubly linked list.

• Hash Map (Dictionary): Stores key-value pairs, providing O(1) average time complexity for get and put operations.
• Doubly Linked List: Maintains the order of keys based on their usage. The most recently used key is moved to the tail of the list, and the least recently used key is at the head. Doubly linked lists allow O(1) removal from anywhere in the list.

Algorithm:

1. Initialization:
   • Initialize the hash map to store key-node pairs.
   • Initialize the doubly linked list with a head and tail sentinel node.
   • Store the capacity of the cache.
2. get(key):
   • Check if the key exists in the hash map.
   • If it exists:
     • Move the corresponding node to the tail of the linked list (most recently used).
     • Return the value stored in the node.
   • If it doesn't exist, return -1.
3. put(key, value):
   • Check if the key exists in the hash map.
   • If it exists:
     • Update the value in the node.
     • Move the node to the tail of the linked list.
   • If it doesn't exist:
     • Create a new node with the key and value.
     • Add the node to the tail of the linked list.
     • Add the key-node pair to the hash map.
     • If the cache exceeds its capacity:
       • Remove the node at the head of the linked list (least recently used).
       • Remove the corresponding key from the hash map.

Edge Cases:

• Capacity of 1: Ensure the implementation handles the edge case when the LRU cache has a capacity of 1.
• Duplicate Keys: The put operation should update the value if the key already exists.
• Empty Cache: The get operation should return -1 when the cache is empty.

Code Example (Python):

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = 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 get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._move_to_tail(node)
            return node.value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_tail(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_tail(node)
            if len(self.cache) > self.capacity:
                self._remove_lru()

    def _move_to_tail(self, node):
        self._remove_node(node)
        self._add_to_tail(node)

    def _add_to_tail(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def _remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _remove_lru(self):
        lru_node = self.head.next
        del self.cache[lru_node.key]
        self._remove_node(lru_node)

• Time Complexity:
  • get(key): O(1) - Hash map lookup and linked list move.
  • put(key, value): O(1) - Hash map lookup/insertion and linked list add/remove.
• Space Complexity: O(capacity) - Storing the key-value pairs in the hash map and doubly linked list.