কনটেন্টে যান

021 — LRU Cache

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • Original source: Classic cache-design interview problem (Least Recently Used eviction)
  • Platform: LeetCode — https://leetcode.com/problems/lru-cache/
  • Topic: hashing + linked lists (design)
  • Difficulty: Medium
  • Pattern: Hashmap + doubly linked list design
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 05 hashing (key থেকে node-এ O(1) jump) আর 03 linked lists (একটা doubly linked list-এ order রাখা, O(1)-তে কোনো node খুলে ফেলা/সামনে আনা)। দুটো জোড়া লাগলেই get আর put দুটোই O(1)।

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

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

তোমাকে একটা fixed-size cache বানাতে হবে যেটা capacity-টা key→value জোড়া রাখে। দুটো operation:

  • get(key) — থাকলে value ফেরত দাও, নাহলে -1। আর এই key-টাকে "এইমাত্র ব্যবহার হলো" হিসেবে গণ্য করো।
  • put(key, value) — থাকলে আপডেট করো, নাহলে যোগ করো। যদি capacity ছাড়িয়ে যায়, তাহলে সবচেয়ে আগে যেটা ব্যবহার হয়েছিল (least recently used) সেটাকে বের করে দাও।

দুটো operation-ই গড়ে O(1)-এ হতে হবে।

উদাহরণ
capacity = 2
put(1, 1)        # cache: {1=1}
put(2, 2)        # cache: {1=1, 2=2}
get(1)  -> 1     # 1 এখন সবচেয়ে recent
put(3, 3)        # 2 evict হয় (LRU), cache: {1=1, 3=3}
get(2)  -> -1    # নেই

Input ও output

উদাহরণ
ops    : LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)
output :              -        -          1       -          -1       -          -1       3        4

Edge case 1 (capacity 1): put(1,1); put(2,2); get(1) -> -1   # 1 সঙ্গে সঙ্গে evict
Edge case 2 (update বিদ্যমান key): put(1,1); put(1,5); get(1) -> 5   # value বদলায়, evict হয় না

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

ভাবো তোমার পড়ার টেবিলে শুধু দুটো বই রাখার জায়গা। নতুন বই দরকার হলে যেটা সবচেয়ে অনেকদিন ছোঁওনি সেটাই তাক-এ ফেরত দাও। প্রতিবার কোনো বই পড়লে সেটা আবার টেবিলের সামনে চলে আসে। dict হলো তোমার মনে রাখা "কোন বই কোথায়", আর list হলো টেবিলে বাঁ-থেকে-ডান recency সাজানো।

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

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

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

  • 05 hashing (../../05-hashing/) থেকে: একটা dict রাখি key -> node, যাতে যেকোনো key-কে O(1)-এ খুঁজে তার ঠিক জায়গায় পৌঁছানো যায়।
  • 03 linked lists (../../03-linked-list/) থেকে: একটা doubly linked list-এ সব entry-কে "recency order"-এ সাজিয়ে রাখি; কোনো node-কে O(1)-এ unlink করা আর head-এর পাশে নিয়ে আসা।

একা hashmap বলতে পারে "key আছে কি না", কিন্তু order রাখতে পারে না; একা linked list order রাখে কিন্তু খুঁজতে O(n)। দুটো মিললেই O(1) get/put।

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

লুকানো logic একটা invariant: list সবসময় recency order-এ থাকে — head-এর পাশে সবচেয়ে recent, tail-এর পাশে সবচেয়ে পুরনো। যেকোনো access (get বা put) মানে সেই node-কে head-এর দিকে সরাও। eviction দরকার হলে tail-এর ঠিক আগের node-টাই LRU, সেটাকে ফেলো।

মূল গণিত: doubly link থাকায় কোনো node-এর prev আর next দুটোই হাতে, তাই তাকে list থেকে খোলা O(1) — singly list হলে আগের node খুঁজতে O(n) লাগত।

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

দুটো একসাথে: (a) একটা hashmap key -> node, আর (b) একটা doubly linked list দুটো sentinel (dummy head, dummy tail) সহ। Sentinel রাখলে কোনো edge case (খালি list, প্রথম/শেষ node) আলাদা করে ভাবতে হয় না — এটাই 03 linked lists-এর dummy-head trick।

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

hashmap (05) দেয় খোঁজার গতি — key থেকে সরাসরি node, scan ছাড়া। doubly linked list (04) দেয় order maintenance — যেকোনো node O(1)-এ tear out করে front-এ বসানো, আর tail থেকে LRU তুলে নেওয়া। array দিয়ে order রাখলে middle থেকে সরাতে O(n) shift লাগত; singly list-এ unlink-এ O(n) লাগত। তাই hashmap + doubly list-ই একমাত্র জোড়া যেটা দুই operation-কেই O(1)-এ রাখে।

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

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

প্রথম সরল চিন্তা: শুধু একটা list of (key, value) রাখি। get-এ list scan করে key খুঁজি, পেলে সেটাকে শেষে সরাই (most-recent চিহ্ন)। put-এ full হলে list-এর সামনের element ফেলে দিই।

উদাহরণ
get(key):  for each (k,v) in list: if k==key: move to end; return v
           return -1
put(key,v): if key present: update + move to end
            elif len == capacity: pop front
            append (key, v)

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

list scan করে key খোঁজা মানে প্রতিটা get/put O(n) — n element-এর মধ্যে linear search, আর middle থেকে সরাতে আরও shift। বড় cache-এ এটা ধীর। কারণ আমরা "key থেকে position" mapping রাখছি না — ঠিক এটাই hashmap (05) দূর করতে আসে: scan-কে O(1) lookup বানায়।

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

মূল observation: দুটো প্রশ্ন আলাদা — "key কোথায়?" আর "সবচেয়ে পুরনো কোনটা?" একটা structure দুটোর দুটোই fast দিতে পারে না। তাই দুটো structure পাশাপাশি রাখো — hashmap উত্তর দেয় প্রথমটার, doubly list দ্বিতীয়টার — আর তাদের একই node object দিয়ে জুড়ে দাও যাতে একটায় খুঁজে অন্যটায় O(1)-এ কাজ করা যায়।

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

dict রাখে key -> node। doubly list (head/tail sentinel সহ) রাখে recency: front = recent, back = old। get: dict-এ খোঁজো, পেলে node-কে unlink করে front-এ বসাও, value দাও। put: থাকলে value আপডেট + front-এ আনো; না থাকলে নতুন node front-এ বসাও আর dict-এ রাখো — full হলে আগে tail-এর আগের node evict করো (list থেকে + dict থেকে দুই জায়গায়)।

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

মোচড়: "একটা structure দিয়ে সব করব" ভাবা ছাড়ো। ভাবো "প্রতিটা entry একই সময়ে দুই জায়গায় বাস করে — dict-এ নাম দিয়ে, list-এ বয়স দিয়ে।" একই node দুই view-তে থাকায় lookup আর reorder দুটোই O(1)।

ছবিতে বোঝা

উদাহরণ
capacity = 2,  list:  HEAD <-> TAIL (শুরুতে খালি)   (HEAD পাশে = recent)

put(1,1):   HEAD <-> [1] <-> TAIL
put(2,2):   HEAD <-> [2] <-> [1] <-> TAIL
get(1):     1-কে front-এ আনো
            HEAD <-> [1] <-> [2] <-> TAIL
put(3,3):   full! tail-এর আগের node = [2] = LRU -> evict
            HEAD <-> [3] <-> [1] <-> TAIL
get(2):     dict-এ নেই -> -1

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

capacity = 2:

  1. put(1,1): dict={1:n1}, list: H<->n1<->T
  2. put(2,2): dict={1:n1, 2:n2}, list: H<->n2<->n1<->T
  3. get(1): dict-এ আছে → n1 unlink, front-এ → list: H<->n1<->n2<->T; return 1
  4. put(3,3): full → LRU = tail-এর আগের = n2 → n2 unlink + dict থেকে 2 মুছি; n3 front-এ; dict={1:n1, 3:n3}, list: H<->n3<->n1<->T
  5. get(2): dict-এ নেই → return -1

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

Python

Python
class _Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                      # key -> _Node  (05 hashing)
        self.head = _Node()                # dummy: front = সবচেয়ে recent
        self.tail = _Node()                # dummy: back = সবচেয়ে old
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):               # O(1) unlink (03 linked lists)
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):            # head-এর ঠিক পরে বসাও
        node.prev = self.head
        node.next = self.head.next
        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)                 # access = front-এ আনা
        self._add_front(node)
        return node.val

    def put(self, key, value):
        if key in self.map:                # বিদ্যমান: value আপডেট + front
            node = self.map[key]
            node.val = value
            self._remove(node)
            self._add_front(node)
            return
        if len(self.map) >= self.cap:      # full: LRU evict
            lru = self.tail.prev           # tail-এর আগের = সবচেয়ে old
            self._remove(lru)
            del self.map[lru.key]
        node = _Node(key, value)           # নতুন entry front-এ
        self.map[key] = node
        self._add_front(node)

# ---- tests ----
c = LRUCache(2)
c.put(1, 1)
c.put(2, 2)
assert c.get(1) == 1          # 1 এখন recent
c.put(3, 3)                   # 2 evict (LRU)
assert c.get(2) == -1         # নেই
c.put(4, 4)                   # 1 evict (এখন LRU)
assert c.get(1) == -1
assert c.get(3) == 3
assert c.get(4) == 4

c1 = LRUCache(1)             # capacity 1
c1.put(1, 1)
c1.put(2, 2)                 # 1 সঙ্গে সঙ্গে evict
assert c1.get(1) == -1
assert c1.get(2) == 2

cu = LRUCache(2)            # বিদ্যমান key update
cu.put(1, 1)
cu.put(1, 5)                # value বদলায়, evict না
assert cu.get(1) == 5
print("সব test pass!")

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

  • _Node (__slots__ সহ) — doubly node, prev/next দুটোই থাকায় O(1) unlink সম্ভব (03 linked lists)।
  • self.map = {} — key থেকে node-এ O(1) jump (05 hashing); এটাই scan মুছে দেয়।
  • head/tail dummy sentinel — খালি list বা প্রান্তের node আলাদা করে ভাবা লাগে না।
  • _remove(node) — দুটো pointer ঘুরিয়ে node-কে list থেকে খুলে দেয়, O(1)।
  • _add_front(node) — node-কে head-এর ঠিক পরে বসায় = "এইমাত্র ব্যবহার হলো"।
  • get — না থাকলে -1; থাকলে remove + add_front করে recent বানায়, তারপর value।
  • put — বিদ্যমান হলে value আপডেট + front; নতুন হলে full চেক করে আগে tail.prev (LRU) evict, তারপর নতুন node front-এ + dict-এ।

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

LRUCache(2)-এ put(1), put(2)-এর পর get(1) → 1, আর 1 front-এ; put(3) এ full বলে n2 (LRU) evict; get(2) → -1; put(4) এ এখন n1 LRU, তাই 1 evict → get(1) -1, get(3) 3, get(4) 4 — সব assert pass। capacity-1 আর update cases-ও সঠিক। শেষে print: সব test pass!।

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

সময়

O(1) প্রতি operation — dict lookup O(1), আর doubly list-এ unlink/add_front constant pointer কাজ। কোনো scan নেই।

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

O(capacity) — dict-এ আর list-এ মিলিয়ে বড়জোর capacity-টা node; cache কখনো এর বেশি রাখে না।

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

  • singly linked list ব্যবহার করা — তখন node unlink করতে আগের node খুঁজতে O(n) লাগে; doubly লাগবেই।
  • evict করার সময় শুধু list থেকে মোছা, dict থেকে না মোছা (বা উল্টো) — দুই জায়গা sync না থাকলে stale entry থেকে যায়; তাই del self.map[lru.key]।
  • put-এ বিদ্যমান key-কে নতুন হিসেবে যোগ করা — duplicate বানায়; আগে if key in self.map চেক করো।
  • sentinel না রাখা — তখন head/tail None-হ্যান্ডলিং-এ off-by-one bug সহজ।

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

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

ভিত্তি: hashmap দিয়ে O(1) key lookup (05 hashing-এর ../../05-hashing/) + doubly linked list-এ O(1) node insert/delete আর dummy-head pattern (03 linked lists-এর ../../03-linked-list/)। এই দুটো cold অবস্থায় জানা থাকলে LRU-র design নিজে থেকেই দাঁড়িয়ে যায়।

পরের অনুশীলন

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

Hashmap + doubly linked list design: একই node-কে দুই view-তে রাখো — dict দেয় O(1) lookup, doubly list দেয় O(1) reorder/eviction। যেকোনো "O(1) get/put with ordering/eviction policy" problem-এর canonical রূপ।

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

ভবিষ্যতের আমাকে: "O(1)-এ get/put + কোনো eviction rule" শুনলেই dict + doubly list মনে করবে। dict রাখে key→node, list রাখে recency (front recent, tail-এর আগের = LRU)। প্রতিটা access-এ node-কে front-এ আনো; full হলে tail-এর আগের node দুই জায়গা থেকেই মোছো। sentinel head/tail রাখলে edge case উধাও। এটা hashing আর linked list-এর সবচেয়ে পরিষ্কার design মেলবন্ধন।

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