Design a Thread-Safe LRU Cache with O(1) Operations in Java

🚀 One of the Most Complex Java Problems Asked in Top Tech Interviews 💡 Design a Thread-Safe LRU Cache with O(1) Operations --- 🧠 Problem Statement: Design and implement an LRU (Least Recently Used) Cache with the following operations: - "get(key)" → Returns value if present, else -1 - "put(key, value)" → Insert/update the value ⚡ Constraints: - Both operations must run in O(1) time - Must be thread-safe (handle concurrent access properly) --- 🔥 Why this is challenging? This problem tests: - Data Structures (HashMap + Doubly Linked List) - Concurrency (Locks, synchronization) - Real-world system design (cache eviction strategy) --- 🛠️ Approach: To achieve O(1): - Use a HashMap → Fast lookup - Use a Doubly Linked List → Maintain LRU order For Thread Safety: - Use ReentrantLock (better than synchronized for flexibility) --- 💻 Java Implementation: import java.util.*; import java.util.concurrent.locks.ReentrantLock; class LRUCache { class Node { int key, value; Node prev, next; Node(int k, int v) { key = k; value = v; } } private final int capacity; private Map<Integer, Node> map; private Node head, tail; private ReentrantLock lock = new ReentrantLock(); public LRUCache(int capacity) { this.capacity = capacity; this.map = new HashMap<>(); head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; } public int get(int key) { lock.lock(); try { if (!map.containsKey(key)) return -1; Node node = map.get(key); remove(node); insert(node); return node.value; } finally { lock.unlock(); } } public void put(int key, int value) { lock.lock(); try { if (map.containsKey(key)) { remove(map.get(key)); } if (map.size() == capacity) { Node lru = tail.prev; remove(lru); map.remove(lru.key); } Node newNode = new Node(key, value); insert(newNode); map.put(key, newNode); } finally { lock.unlock(); } } private void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } private void insert(Node node) { node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; } } --- ⚠️ Common Mistakes: - Forgetting to update order after "get()" - Not handling concurrency → leads to race conditions - Using only HashMap (misses LRU behavior) --- 📈 Follow-up Questions Asked in Interviews: - Can you make it lock-free? - How would you scale this in distributed systems? - What if capacity is millions? #Java #SystemDesign #CodingInterview #Concurrency #TechCareers

To view or add a comment, sign in

Explore content categories