Problem Statement
Describe how you would implement an LRU cache with O(1) get and put operations, using hashing and a doubly linked list.
Explanation
Use a hash map from key→node and a doubly linked list storing nodes with most recently used at head and least at tail. On get: if key exists move its node to head. On put: if full remove tail node and map entry, then insert new node at head and into map. Hashing gives O(1) lookup, list gives O(1) insertion/removal. Common interview system design for caching.
Code Solution
SolutionRead Only
class Node{int key,val; Node prev, next;} class LRU{ Map<Integer,Node> map; Node head,tail; int cap; LRU(int c){cap=c; map=new HashMap<>(); head=new Node(); tail=new Node(); head.next=tail; tail.prev=head;} int get(int k){ if(!map.containsKey(k)) return -1; Node n=map.get(k); remove(n); insertToHead(n); return n.val;} void put(int k,int v){ if(map.containsKey(k)){ Node n=map.get(k); n.val=v; remove(n); insertToHead(n); } else { if(map.size()==cap){ Node lru=tail.prev; remove(lru); map.remove(lru.key);} Node n=new Node(k,v); map.put(k,n); insertToHead(n);} } void remove(Node n){ n.prev.next=n.next; n.next.prev=n.prev;} void insertToHead(Node n){ n.next=head.next; head.next.prev=n; head.next=n; n.prev=head;} }