LRU Cache

• LRU stands for "Least Recently Used", a cache eviction policy that removes the least recently accessed item when the cache reaches capacity.
• Core idea: Ensures that the most recently used (MRU) elements remain in the cache, while the least recently used (LRU) elements get evicted first.
• Data structures used: Typically implemented using a combination of a hash map (for $O(1)$ key lookup) and a doubly linked list (for efficient reordering of usage).
• Operations supported:
  • Get(key): Retrieves the value if present and moves the accessed item to the front (MRU position).
  • Put(key, value): Adds or updates an item and moves it to the front. If the cache is full, removes the item at the back (LRU position) before inserting.
• Use cases: Frequently applied in memory management, CPU cache, web caching, and databases to optimize data retrieval and resource usage.
• Benefits: Maintains fast access time (O(1) for both get and put operations) and automatic eviction of old, unused data, making it efficient for limited-size memory situations.

---

Defining the Node class

class Node:
    def __init__(self, key_: int, value_: int):
        # Each node stores a key-value pair
        self.value = [key_, value_]
        self.prev = None  # Pointer to the previous node
        self.next = None  # Pointer to the next node

    def __str__(self):
        return f"({self.value[0]}, {self.value[1]})"

    def getKey(self):
        return self.value[0]

    def getValue(self):
        return self.value[1]

    def setValue(self, val_: int):
        self.value[1] = val_

class LRUCache:
    def __init__(self, capacity):
        # Initialize the cache with a given capacity
        self.capacity = capacity
        self.number_of_elements = 0
        self.cache_head = None  # Most recently used
        self.cache_tail = None  # Least recently used
        self.cache_map = {}     # Dictionary to store key -> Node mapping

    # Utility function to print the current state of the cache for debugging purposes
    def print_cache(self):
        temp_node = self.cache_head
        while temp_node is not None:
            print(temp_node, end=" ")
            temp_node = temp_node.next
        print()

Algorithm for get method

1. Check if key exists:
   • If the key does not exist in the map/dictionary return -1 (indicating a cache miss).
2. Access the node:
   • Retrieve the node corresponding to the key from the map.
3. Move node to front (most recently used):
   • If the node is not already at the front, remove it from its current position and insert it at the head of the doubly linked list.
     • Update the previous and next pointers as needed.
     • Update head and tail references if necessary.
4. Return value:
   • Return the value associated with the node.

---

def get(self, key_: int):
    # Return the value of the key if present, else -1
    if key_ not in self.cache_map:
        return -1

    node = self.cache_map[key_]

    # If node is already at the head, it's the most recently used
    if node.prev is None:
        return node.getValue()

    # If node is at the tail, update tail and move node to head
    if node.next is None:
        self.cache_tail = self.cache_tail.prev
        self.cache_tail.next = None
    else:
        # Remove node from its current position
        node.prev.next = node.next
        node.next.prev = node.prev

    # Move node to the head
    node.next = self.cache_head
    self.cache_head.prev = node
    node.prev = None
    self.cache_head = node

    return node.getValue()

Algorithm for put method

1. Check for Key Existence:
   • If the key is already present in the cache:
     • Update its value.
     • Move the corresponding node to the front (most recently used position).
2. If Key Not Present:
   • If the cache is at full capacity:
     • Remove the least recently used item (the tail of the linked list or the first item in an insertion-order map).
     • Remove its entry from both the linked list and the key-node mapping (hashmap).
   • Create a new node for the key and value.
3. Insert at Front:
   • Insert the new or updated node at the front of the linked list (marks it most recently used).
   • Update the key-node mapping in the hashmap to point to the front node.
4. Time Complexity: Each of these sub-operations (checking, adding, removing, updating) takes O(1) time using a combination of hashmap and doubly linked list.

---

def put(self, key_: int, value_: int):
    # modular code to update existing node and move it to the head
    def updateNode():
        node = self.cache_map[key_]
        node.setValue(value_)
        if node.prev is None:
            return
        if node.next is None:
            self.cache_tail = self.cache_tail.prev
            self.cache_tail.next = None
            node.next = self.cache_head
            self.cache_head.prev = node
            node.prev = None
            self.cache_head = node
            return
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = self.cache_head
        self.cache_head.prev = node
        self.cache_head = node

    # Insert or update the value_ of the key_
    if self.capacity == 0:
        # Special handling when capacity is 0
        if self.number_of_elements == 1:
            self.cache_map.pop(self.cache_tail.getKey())
            self.cache_head = Node(key_, value_)
            self.cache_tail = self.cache_head
            self.cache_map[key_] = self.cache_head
            return

        if key_ in self.cache_map:
            updateNode(); return
        else:
            self.cache_map.pop(self.cache_tail.getKey())
            self.cache_tail = self.cache_tail.prev
            self.cache_tail.next = None
            node = Node(key_, value_)
            self.cache_head.prev = node
            node.next = self.cache_head
            self.cache_head = node
            self.cache_map[key_] = self.cache_head
            return

    if key_ in self.cache_map:
        updateNode(); return

    # Insert new node
    if self.number_of_elements == 0:
        self.cache_tail = Node(key_, value_)
        self.cache_head = self.cache_tail
        self.capacity -= 1
        self.number_of_elements = 1
    elif self.number_of_elements == 1:
        self.cache_head = Node(key_, value_)
        self.cache_head.next = self.cache_tail
        self.cache_tail.prev = self.cache_head
        self.capacity -= 1
        self.number_of_elements += 1
    else:
        node = Node(key_, value_)
        node.next = self.cache_head
        self.cache_head.prev = node
        self.cache_head = node
        self.capacity -= 1
        self.number_of_elements += 1

    self.cache_map[key_] = self.cache_head

Binding the methods to the class

LRUCache.get = get
LRUCache.put = put

Testcase(s)

test = (["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"],
         [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]])
expected_result = [None, None, None, 1, None, -1, None, -1, 3, 4]

Driver code

result = []
cacheObj = None
for i in range(len(test[0])):
    if test[0][i] == "LRUCache":
        result.append(None)
        cacheObj = LRUCache(test[1][i][0])
    if test[0][i] == "put":
        result.append(None)
        key, value = test[1][i]
        cacheObj.put(key, value)
    if test[0][i] == "get":
        value = cacheObj.get(test[1][i][0])
        result.append(value)

if result == expected_result:
    print(f"Result matches expected result\n{result}")

Result matches expected result
[None, None, None, 1, None, -1, None, -1, 3, 4]

---