Design an LRU Cache

Problem Statement

Design and implement an LRU (Least Recently Used) Cache from scratch.

An LRU Cache is a data structure that stores a fixed number of items. When the cache is full and a new item needs to be inserted, it evicts the item that was least recently used (i.e., not accessed for the longest time).

This is used everywhere in real systems — CPU caches, browser caches, database query caches, CDN caches.

Requirements

Core Operations

Method	Description
`LRUCache(int capacity)`	Initialize the cache with a fixed capacity
`int get(int key)`	Return value if key exists, else return `-1`
`void put(int key, int value)`	Insert or update a key-value pair. If cache is full, evict the LRU item first

Constraints

Both get and put must run in O(1) time
Capacity is always a positive integer
Accessing a key via get counts as a "use" (moves it to most recently used)
Updating an existing key via put also counts as a "use"

Example Walkthrough

LRUCache cache = new LRUCache(3);  // capacity = 3

cache.put(1, "A");   // Cache: [1]
cache.put(2, "B");   // Cache: [1, 2]
cache.put(3, "C");   // Cache: [1, 2, 3]  ← full now

cache.get(1);        // Cache: [2, 3, 1]  ← 1 moved to most recent
                     // returns "A"

cache.put(4, "D");   // Cache is full → evict LRU which is 2
                     // Cache: [3, 1, 4]

cache.get(2);        // returns -1 (was evicted)
cache.get(3);        // Cache: [1, 4, 3]  ← 3 moved to most recent
                     // returns "C"

SOLUTION

class Node {
    int key;
    int val;
    Node next;
    Node prev;
    Node(int k, int v){
        this.key = k;
        this.val = v;
    }

}
class LRUCache {

    private final int capacity;
    private final Map<Integer, Node> mpp;
    private final Node head; 
    private final Node tail; 

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.mpp = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = null;
        node.next = null;
    }
    
    private void addFront(Node node){
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;

    }
    public int get(int key) {
       if(mpp.size() <= 0) return -1;
        Node node = mpp.get(key);
        if(node == null) return -1;
        remove(node);
        addFront(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        if(capacity <= 0){
            return;
        }
        Node node = mpp.get(key);
        if(node != null){
            node.val = value;
            remove(node);
            addFront(node);
        } else {
            if(mpp.size() >= capacity){
                Node lru = tail.prev;
                remove(lru);
                mpp.remove(lru.key);
            }
            Node newNode = new Node(key, value);
            addFront(newNode);
            mpp.put(key, newNode);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */