LRU Cache medium

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with 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.

The functions get and put must each run in O(1) average time complexity.

Example 1

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Example 2

Input
["LRUCache", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [2, 1], [2], [3, 2], [2], [4, 4], [2], [3], [4]]
Output
[null, null, 1, null, -1, null, -4, -1, 4]

Steps and Explanation

The optimal solution uses a combination of a Dictionary (or Hashtable) for O(1) key lookup and a DoublyLinkedList for O(1) insertion and deletion at both ends.

1. Data Structures:

   • Dictionary<int, Node> cache: Stores key-value pairs along with a reference to a Node in the doubly linked list.
   • DoublyLinkedList list: Maintains the order of elements based on LRU. The head represents the most recently used, and the tail represents the least recently used.

2. Node Class:

   • int key: Key of the cache entry.
   • int value: Value of the cache entry.
   • Node prev: Pointer to the previous node.
   • Node next: Pointer to the next node.

3. get(key):

   • Check if the key exists in the cache.
   • If found:
     • Move the corresponding node to the head of the list (making it the most recently used).
     • Return the value.
   • If not found: Return -1.

4. put(key, value):

   • Check if the key exists in the cache.
   • If found:
     • Update the value.
     • Move the corresponding node to the head of the list.
   • If not found:
     • Create a new Node.
     • Add the new Node to the head of the list.
     • Add the key-value pair to the cache.
     • If the cache size exceeds capacity:
       • Remove the tail node (LRU) from the list.
       • Remove the corresponding key from the cache.

Code

using System.Collections.Generic;

public class Node
{
    public int key;
    public int value;
    public Node prev;
    public Node next;
    public Node(int k, int v) { key = k; value = v; }
}

public class DoublyLinkedList
{
    public Node head;
    public Node tail;
    public int count;

    public DoublyLinkedList() { head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; count = 0; }

    public void addFirst(Node node)
    {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
        count++;
    }

    public void remove(Node node)
    {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        count--;
    }

    public Node removeLast()
    {
        if (count == 0) return null;
        Node last = tail.prev;
        remove(last);
        return last;
    }

}


public class LRUCache {
    private Dictionary<int, Node> cache;
    private DoublyLinkedList list;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new Dictionary<int, Node>();
        list = new DoublyLinkedList();
    }

    public int Get(int key) {
        if (!cache.ContainsKey(key)) return -1;
        Node node = cache[key];
        list.remove(node);
        list.addFirst(node);
        return node.value;
    }

    public void Put(int key, int value) {
        if (cache.ContainsKey(key))
        {
            list.remove(cache[key]);
            cache[key].value = value;
            list.addFirst(cache[key]);
        }
        else
        {
            Node node = new Node(key, value);
            cache.Add(key, node);
            list.addFirst(node);
            if (list.count > capacity)
            {
                Node last = list.removeLast();
                cache.Remove(last.key);
            }
        }
    }
}

Complexity

• Time Complexity:

  • get(key): O(1) on average.
  • put(key, value): O(1) on average.

• Space Complexity: O(capacity) to store the cache entries.