Design a Least Recently Used (LRU) cache with get(key) and put(key,value) operations, both O(1). Evict the least recently used item when capacity is exceeded.
LRUCache(2), put(1,1), put(2,2), get(1)→1, put(3,3) [evicts 2], get(2)→-1, get(3)→3
Use a HashMap + Doubly Linked List. Map stores key→node. DLL keeps order (head=most recent, tail=LRU). On access, move node to front.
- DLL with sentinel head and tail.
- get: if exists, move to front, return val.
- put: if exists update and move to front; else insert at front; if over capacity remove tail.
import java.util.*;
class LRUCache {
class Node { int key, val; Node prev, next; Node(int k,int v){key=k;val=v;} }
Map<Integer,Node> map = new HashMap<>();
Node head = new Node(0,0), tail = new Node(0,0);
int cap;
public LRUCache(int capacity) {
cap=capacity; head.next=tail; tail.prev=head;
}
private void remove(Node n) { n.prev.next=n.next; n.next.prev=n.prev; }
private void insertFront(Node n) { n.next=head.next; n.prev=head; head.next.prev=n; head.next=n; }
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node n=map.get(key); remove(n); insertFront(n); return n.val;
}
public void put(int key, int value) {
if (map.containsKey(key)) { Node n=map.get(key); n.val=value; remove(n); insertFront(n); return; }
Node n = new Node(key,value); map.put(key,n); insertFront(n);
if (map.size()>cap) { map.remove(tail.prev.key); remove(tail.prev); }
}
}
- Time Complexity: get/put: O(1)
- Space Complexity: O(N)