021 — LRU Cache

Problem link ও উৎস

• 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)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা 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  ...

Input ও 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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা পুরো 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) হয়।

ভেতরের যুক্তি

লুকানো 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-এ সাজানো।

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

শুধু 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)।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ

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

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

প্রতিটা 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 আলাদা সামলাতে হয় না।

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

DLL: head ও tail sentinel-এর মাঝখানে বাস্তব node থাকে; head-এর পাশটি most 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 আর নেই

ছোট input-এ ধাপে ধাপে

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।

কোড ও ব্যাখ্যা

Python

Python

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!")

কোডের প্রতিটি অংশ

• 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 থেকেও মুছে দাও।

Output মিলিয়ে দেখা

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!।

JavaScript ও test cases

JavaScript

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 রাখা।

TypeScript ও test cases

TypeScript

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-গুলো লুকিয়ে রাখে।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

• 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-প্রবণ।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

• 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/

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

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

কোথায় কাজে লাগে

• 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।