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 cache = new LRUCache(2);
cache.put(1, 1); // cache is {1=1}
cache.put(2, 2); // cache is {1=1, 2=2}
cache.get(1);    // return 1
cache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
cache.get(2);    // returns -1 (not found)
cache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
cache.get(1);    // return -1 (not found)
cache.get(3);    // return 3
cache.get(4);    // return 4

Example 2

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

Explanation:

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

Steps

To implement an LRU cache efficiently, we'll use a combination of a HashMap and a DoublyLinkedList.

1. HashMap: Stores key-value pairs for O(1) access time. The key will map to a Node in the DoublyLinkedList.
2. DoublyLinkedList: Maintains the order of usage. The most recently used item is at the head, and the least recently used is at the tail. We need a doubly linked list because we need to be able to remove nodes from the middle efficiently (in O(1) time).

For each get and put operation:

• get(key):

  • Check if the key exists in the HashMap. If not, return -1.
  • If it exists, get the corresponding node from the linked list.
  • Move this node to the head of the linked list (marking it as most recently used).
  • Return the value.

• put(key, value):

  • Check if the key exists in the HashMap. If it does, update the value and move the node to the head of the linked list.
  • If the key doesn't exist:
    • If the cache is full, remove the tail node (LRU) from both the HashMap and the linked list.
    • Add the new node to the head of the linked list.
    • Add the key-node pair to the HashMap.

Explanation

The use of a HashMap and DoublyLinkedList provides the O(1) time complexity required. The HashMap allows for instant lookup of keys, while the DoublyLinkedList efficiently manages the order of usage, allowing for quick removal of the LRU element. Moving nodes in the linked list is also O(1) because we maintain references to the head and tail.

Code

import java.util.HashMap;

class Node {
    int key;
    int value;
    Node prev;
    Node next;

    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class LRUCache {
    private int capacity;
    private HashMap<Integer, Node> map;
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0); // Dummy head
        tail = new Node(0, 0); // Dummy tail
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        remove(node);
        add(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            remove(node);
            add(node);
        } else {
            if (map.size() == capacity) {
                remove(tail.prev);
            }
            Node node = new Node(key, value);
            add(node);
            map.put(key, node);
        }
    }

    private void add(Node node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        map.remove(node.key);
    }
}

Complexity

• Time Complexity:
  • get(key): O(1)
  • put(key, value): O(1)
• Space Complexity: O(capacity) – proportional to the cache size.