021 — LRU Cache

Source

• Original source: Classic system-design-flavored data structure exercise
• Platform: LeetCode — https://leetcode.com/problems/lru-cache/
• Topic: linked list (doubly) + hash map
• Difficulty: Hard
• Pattern: doubly linked list + hash map
• Basic idea inherited from: এই chapter-এর সব pointer-rewiring + hash maps (map-as-memory)

1. Problem in simple words

একটা LRU (Least Recently Used) cache design করতে হবে, যার একটা নির্দিষ্ট capacity আছে। দুটো কাজ দুটোই O(1)-এ হতে হবে:

• get(key) — key থাকলে তার value ফেরাও (আর key-টাকে "সদ্য ব্যবহৃত" বানাও); না থাকলে -1।
• put(key, value) — key বসাও/আপডেট করো। capacity ভরে গেলে সবচেয়ে পুরোনো (least recently used) entry-টা ফেলে দাও।

capacity = 2
put(1,1) put(2,2)  get(1)=1  put(3,3)→2 বাদ  get(2)=-1  ...

2. Which basic idea does this inherit from?

এটা পুরো chapter-এর capstone: এক জায়গায় দুটো জিনিস জোড়া —

• Doubly linked list — node-কে O(1)-তে যেকোনো জায়গা থেকে খুলে সামনে আনতে (এই chapter-এর সব pointer-rewiring discipline)।
• Hash map (map-as-memory, problem 18-এর মতো) — key থেকে সরাসরি সেই node-এ O(1) lookup।

দুটোর সমন্বয়েই দুই operation O(1) হয়।

3. What is the hidden math or logic?

লুকানো logic: "recently used" ক্রমটা ধরে রাখতে হলে দরকার এমন একটা order যেখানে — (১) যেকোনো item-কে চট করে "সবার সামনে" আনা যায়, আর (২) "সবার পিছনের" (পুরোনো) item-কে চট করে ফেলা যায়। doubly linked list-এ যেকোনো node-এর prev/next জানা থাকায় তাকে O(1)-তে খুলে সামনে বসানো যায়; আর hash map সেই node-কে key দিয়ে O(1)-তে এনে দেয়। এই দুইয়ের জোড়ই invariant রক্ষা করে: map সবসময় key → তার DLL node, আর DLL সবসময় recency-order-এ সাজানো।

4. Which data structure is needed?

দুটো একসাথে: একটা hash map (key → node) আর একটা doubly linked list (recency order ধরে রাখতে — এক প্রান্তে সবচেয়ে recent, অন্য প্রান্তে সবচেয়ে পুরোনো)। দুই প্রান্ত সামলাতে dummy head ও tail sentinel রাখি।

5. Why this data structure fits

শুধু hash map দিয়ে lookup O(1), কিন্তু "কে সবচেয়ে পুরোনো" বলা যায় না। শুধু list দিয়ে order রাখা যায়, কিন্তু একটা key খুঁজতে O(n)। doubly linked list লাগে (singly নয়) কারণ একটা node-কে মাঝখান থেকে খুলতে তার আগের node দরকার — doubly-তে node.prev হাতেই থাকে, তাই unlink O(1)। map + DLL জোড়ায় lookup, move-to-front, আর evict — তিনটাই O(1)।

6. Real-life analogy

ডেস্কে কাগজের একটা স্তূপ ভাবো, capacity সীমিত। কোনো কাগজ ব্যবহার করলেই সেটা তুলে স্তূপের একদম উপরে রাখো (সদ্য-ব্যবহৃত)। জায়গা ফুরালে একদম নিচের কাগজটা (সবচেয়ে দিন ছোঁয়া হয়নি) ফেলে দাও। আর কোন কাগজ কোথায় আছে দ্রুত জানতে একটা index-খাতা (hash map) রাখো — খুঁজতে পুরো স্তূপ ঘাঁটতে হয় না।

7. Visual explanation

DLL: head (most recent প্রান্ত) ↔ ... ↔ tail (least recent প্রান্ত)। capacity = 2:

put(1,1): head <-> [1] <-> tail
put(2,2): head <-> [2] <-> [1] <-> tail        (2 সবচেয়ে recent)
get(1)=1: 1 কে সামনে আনো → head <-> [1] <-> [2] <-> tail
put(3,3): ভরে গেছে → tail-এর আগের (2) বাদ
          head <-> [3] <-> [1] <-> tail
get(2)=-1: 2 আর নেই

8. Example input and output

capacity = 2
put(1, 1)
put(2, 2)
get(1)    -> 1
put(3, 3) -> key 2 evict (least recently used)
get(2)    -> -1
put(4, 4) -> key 1 evict
get(1)    -> -1
get(3)    -> 3
get(4)    -> 4

9. Brute force thinking

সরল চিন্তা: একটা সাধারণ list (বা array) of (key, value) রাখো, আর সাথে একটা "শেষ কবে ব্যবহার" timestamp। get/put-এ পুরো list scan করে key খোঁজো; evict করতে পুরো list scan করে সবচেয়ে পুরোনো timestamp খুঁজে ফেলো।

get(k): পুরো list খোঁজো → O(n)
evict : সবচেয়ে পুরোনো খুঁজে বাদ → O(n)

10. Why brute force is slow

প্রতিটা get/put-এ key খুঁজতে বা পুরোনোতম বের করতে পুরো list scan — O(n) প্রতি operation। অথচ শর্ত হলো দুটোই O(1)। তাই lookup-এর জন্য hash map আর order-এর জন্য doubly linked list — দুটো জুড়ে scan-টাই মুছে ফেলতে হয়।

11. Key observation

মূল observation: lookup আর ordering আলাদা দুটো দরকার, দুটোর জন্য দুটো structure। hash map key→node lookup O(1) করে; doubly linked list "সদ্য-ব্যবহৃত সামনে, পুরোনো পিছনে" order O(1)-তে রক্ষা করে। একটা node দুই জায়গাতেই বাস করে — map তাকে খুঁজে দেয়, DLL তার recency ধরে রাখে।

12. Optimized intuition

প্রতিটা key-র জন্য একটা DLL node বানাও (key + value সহ)। map রাখে key → node। get: map-এ না থাকলে -1; থাকলে node-কে DLL থেকে খুলে head-প্রান্তে এনে value ফেরাও। put: key থাকলে পুরোনো node খুলে দাও; নতুন node বানিয়ে head-এ বসাও আর map-এ রাখো; এরপর size capacity ছাড়ালে tail-প্রান্তের node (least recent) খুলে map থেকেও মুছে দাও। dummy head/tail sentinel থাকায় প্রান্তের edge case আলাদা সামলাতে হয় না।

13. Thinking tweak

মোচড়: "একটাই structure দিয়ে সব" করার চেষ্টা ছাড়ো — lookup আর order দুটো আলাদা সমস্যা, তাই দুটো structure। map দেয় "কোথায়", DLL দেয় "কত recent"; একই node-কে দুজনে দুই দৃষ্টিতে দেখে। এই বিভাজনই O(1)-এর রহস্য।

14. Step-by-step dry run

capacity = 2:

1. put(1,1): node(1) head-এ; map={1}। DLL: 1।
2. put(2,2): node(2) head-এ; map={1,2}। DLL: 2, 1।
3. get(1): আছে → 1-কে head-এ আনো; ফেরাও 1। DLL: 1, 2।
4. put(3,3): নতুন node(3) head-এ; size 3 > 2 → tail-প্রান্তের 2 evict, map থেকেও বাদ। DLL: 3, 1; map={1,3}।
5. get(2): map-এ নেই → ফেরাও -1।
6. put(4,4): node(4) head-এ; size 3 > 2 → tail-প্রান্তের 1 evict। DLL: 4, 3।
7. get(1) = -1, get(3) = 3, get(4) = 4।

15. Python solution

class DLLNode:
    def __init__(self, key=0, val=0):
        self.key = key          # key রাখি যাতে evict-এর সময় map থেকেও মুছতে পারি
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                   # key -> DLLNode
        self.head = DLLNode()           # dummy: most-recent প্রান্ত
        self.tail = DLLNode()           # dummy: least-recent প্রান্ত
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):            # node-কে DLL থেকে খোলো (O(1))
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):         # node-কে head-প্রান্তে বসাও (most recent)
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)           # সদ্য-ব্যবহৃত → সামনে
        return node.val

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key]) # পুরোনোটা খুলে দাও
        node = DLLNode(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:    # ভরে গেলে least-recent বাদ
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

# ---- tests (LeetCode-style operation sequence) ----
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
assert cache.get(1) == 1        # 1 এখন most recent
cache.put(3, 3)                 # key 2 evict
assert cache.get(2) == -1
cache.put(4, 4)                 # key 1 evict
assert cache.get(1) == -1
assert cache.get(3) == 3
assert cache.get(4) == 4

# capacity 1 + একই key update
c2 = LRUCache(1)
c2.put(1, 1)
assert c2.get(1) == 1
c2.put(2, 2)                    # key 1 evict
assert c2.get(1) == -1
assert c2.get(2) == 2
c2.put(2, 20)                   # update, evict নয়
assert c2.get(2) == 20
print("সব test pass!")

16. Line-by-line code explanation

• DLLNode — key + value দুটোই রাখে; evict-এর সময় node থেকে key পেয়ে map থেকেও মোছা যায়।
• head/tail dummy sentinel — সবসময় দুই প্রান্তে থাকে, তাই "list খালি" বা "প্রথম/শেষ node" আলাদা করে সামলাতে হয় না।
• _remove(node) — node.prev ও node.next জোড়া দিয়ে node-কে O(1)-তে খুলে ফেলে (doubly বলেই prev হাতে আছে)।
• _add_front(node) — head-এর ঠিক পরে বসিয়ে node-কে most-recent বানায়।
• get — না থাকলে -1; থাকলে node খুলে সামনে এনে (recency আপডেট) value ফেরায়।
• put — থাকলে আগে খোলো; নতুন node সামনে বসিয়ে map-এ রাখো; size > cap হলে tail.prev (least recent) খুলে map থেকেও মুছে দাও।

17. Output walkthrough

cap=2-তে: put(1,1) put(2,2) → DLL 2,1। get(1)=1, 1 সামনে → 1,2। put(3,3) → 3 সামনে, size 3>2, tail-প্রান্তের 2 evict → 3,1। get(2)=-1। put(4,4) → 1 evict → 4,3। get(1)=-1, get(3)=3, get(4)=4 — সব assert pass। cap=1-এর update-case-ও pass; শেষে print: সব test pass!।

18. Time complexity

O(1) প্রতি get/put — map lookup O(1), আর DLL-এ remove/add-front ধ্রুবক কয়েকটা pointer-বদল।

19. Space complexity

O(capacity) — map-এ ও DLL-এ একসাথে সর্বোচ্চ capacity-টা entry/node থাকে।

20. Common mistakes

• singly linked list ব্যবহার করা — তখন মাঝের node খুলতে আগের node খুঁজতে O(n) লাগে; doubly লাগবেই।
• node-এ key না রাখা — evict-এর সময় কোন key map থেকে মুছব জানা যায় না।
• get-এও recency আপডেট করতে ভুলে যাওয়া (শুধু value ফেরানো) — তখন LRU order ভুল হয়ে যায়।
• evict-এর পর map থেকে মুছতে ভুলে যাওয়া — map আর DLL বেমিল হয়ে যায়; size হিসাবও নষ্ট।
• dummy head/tail না রাখা — প্রতিটা প্রান্তের None-check আলাদা করে সামলাতে গিয়ে code bug-প্রবণ।

21. Which basic problem this inherits from

ভিত্তি: এই chapter-এর সব pointer-rewiring (বিশেষত doubly list-এ unlink/insert) আর map-as-memory (018-copy-random-list.md-এর hash map ব্যবহার)। দুটো জুড়েই এই design।

22. Similar harder problems

• LFU Cache (least frequently used) — https://leetcode.com/problems/lfu-cache/
• Design Linked List — https://leetcode.com/problems/design-linked-list/
• All O(1) Data Structure — https://leetcode.com/problems/all-oone-data-structure/

23. Pattern learned

Hash map + doubly linked list = O(1) cache: map দেয় O(1) lookup, DLL দেয় O(1) recency-order রক্ষা — দুই structure এক node-এ মিলিয়ে design করা।

24. Final summary

ভবিষ্যতের আমাকে: "O(1) get/put + 'recently used' order? hash map (key→node) + doubly linked list (front = recent, back = old)।" lookup আর order আলাদা সমস্যা — দুটোর জন্য দুটো structure, এটাই মূল চাবি।

25. JavaScript solution (with test cases)

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

class DLLNode {
  constructor(key = 0, val = 0) {
    this.key = key;          // key রাখি, evict-এ map থেকেও মুছতে
    this.val = val;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();              // key -> DLLNode
    this.head = new DLLNode();         // dummy: most-recent প্রান্ত
    this.tail = new DLLNode();         // dummy: least-recent প্রান্ত
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  _remove(node) {                       // O(1) unlink (doubly বলেই prev হাতে)
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  _addFront(node) {                     // head-প্রান্তে = most recent
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._addFront(node);               // সদ্য-ব্যবহৃত -> সামনে
    return node.val;
  }
  put(key, value) {
    if (this.map.has(key)) this._remove(this.map.get(key));  // পুরোনোটা খোলো
    const node = new DLLNode(key, value);
    this.map.set(key, node);
    this._addFront(node);
    if (this.map.size > this.cap) {      // ভরে গেলে least-recent বাদ
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

// ---- test cases (LeetCode-style operation sequence) ----
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
assert(cache.get(1) === 1, "1 most recent");
cache.put(3, 3);                         // key 2 evict
assert(cache.get(2) === -1, "2 evicted");
cache.put(4, 4);                         // key 1 evict
assert(cache.get(1) === -1, "1 evicted");
assert(cache.get(3) === 3, "3 present");
assert(cache.get(4) === 4, "4 present");

const c2 = new LRUCache(1);              // capacity 1 + একই key update
c2.put(1, 1);
assert(c2.get(1) === 1, "c2 get1");
c2.put(2, 2);                            // key 1 evict
assert(c2.get(1) === -1, "c2 1 evicted");
c2.put(2, 20);                           // update, evict নয়
assert(c2.get(2) === 20, "c2 updated");
console.log("সব JS test pass!");

JS টীকা: capacity-check-এ this.map.size ব্যবহার করো — Map-এর size O(1)-তে পাওয়া যায়। dummy head/tail sentinel রাখায় কখনো null-prev/next check করতে হয় না, তাই _remove/_addFront শাখাহীন ও O(1)। মনে রেখো get-এও recency আপডেট করতে হয় (শুধু value ফেরালে LRU order ভেঙে যায়), আর evict-এর পর map.delete(lru.key) না করলে map ও DLL বেমিল হয়ে যায় — সেজন্যই node-এ key রাখা।

26. TypeScript solution (with test cases)

class DLLNode {
  key: number;
  val: number;
  prev: DLLNode | null = null;
  next: DLLNode | null = null;
  constructor(key = 0, val = 0) { this.key = key; this.val = val; }
}

class LRUCache {
  private cap: number;
  private map = new Map<number, DLLNode>();
  private head = new DLLNode();
  private tail = new DLLNode();
  constructor(capacity: number) {
    this.cap = capacity;
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  private remove(node: DLLNode): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }
  private addFront(node: DLLNode): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }
  get(key: number): number {
    const node = this.map.get(key);
    if (!node) return -1;
    this.remove(node);
    this.addFront(node);
    return node.val;
  }
  put(key: number, value: number): void {
    const existing = this.map.get(key);
    if (existing) this.remove(existing);
    const node = new DLLNode(key, value);
    this.map.set(key, node);
    this.addFront(node);
    if (this.map.size > this.cap) {
      const lru = this.tail.prev!;
      this.remove(lru);
      this.map.delete(lru.key);
    }
  }
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
const cache = new LRUCache(2);
cache.put(1, 1); cache.put(2, 2);
expect(cache.get(1), 1, "get1");
cache.put(3, 3);
expect(cache.get(2), -1, "2 evicted");
cache.put(4, 4);
expect(cache.get(1), -1, "1 evicted");
expect(cache.get(3), 3, "get3");
expect(cache.get(4), 4, "get4");
const c2 = new LRUCache(1);
c2.put(1, 1); c2.put(2, 2);
expect(c2.get(1), -1, "c2 evict");
c2.put(2, 20);
expect(c2.get(2), 20, "c2 update");
console.log("সব TS test pass!");

TS টীকা: Map<number, DLLNode> generic-এ key ও value-র type বাঁধা, তাই ভুল কিছু রাখলে compile error। const node = this.map.get(key); if (!node) return -1; প্যাটার্নে get-এর DLLNode | undefined return narrow হয়ে নিচে node non-undefined হয় — এটাই TS-এর নিরাপদ lookup idiom। prev!/next! assertion শুধু সেখানেই দিই যেখানে dummy sentinel-এর কারণে নিশ্চিত non-null। private modifier internal DLL helper-গুলো লুকিয়ে রাখে।

27. কোথায় কাজে লাগে (real-world use)

• Database/page cache: OS ও DB buffer pool LRU eviction দিয়ে কোন page মেমরিতে রাখবে ঠিক করে।
• Web/CDN cache: browser, CDN, reverse-proxy সাম্প্রতিক response রাখতে LRU ব্যবহার করে।
• API rate/result caching: ব্যয়বহুল API/DB result-এর bounded cache — পুরোনো entry স্বয়ংক্রিয়ভাবে বাদ।
• Mobile/image caching: সীমিত মেমরিতে সম্প্রতি-দেখা image/thumbnail ধরে রাখতে।
• CPU/hardware caches: cache-line replacement policy-র (pseudo-)LRU এই ধারণার hardware রূপ।

এক কথায়, যেখানে দ্রুত (O(1)) lookup এবং "সাম্প্রতিকতা"-ভিত্তিক bounded eviction দুটোই দরকার, সেখানে hash map + doubly linked list-এর এই জোড়াই canonical সমাধান।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।