Problem link ও উৎস
- **Original source:** Classic cache-design interview problem (Least Recently Used eviction)
- **Platform:** LeetCode —
- **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)।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা **fixed-size cache** বানাতে হবে যেটা `capacity`-টা key→value জোড়া রাখে। দুটো operation:
- `get(key)` — থাকলে value ফেরত দাও, নাহলে -1। আর এই key-টাকে "এইমাত্র ব্যবহার হলো" হিসেবে গণ্য করো।
- `put(key, value)` — থাকলে আপডেট করো, নাহলে যোগ করো। যদি capacity ছাড়িয়ে যায়, তাহলে **সবচেয়ে আগে যেটা ব্যবহার হয়েছিল (least recently used)** সেটাকে বের করে দাও।
দুটো operation-ই গড়ে O(1)-এ হতে হবে।
```text
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 {#8-example-input-and-output}
```text
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 হয় না
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তোমার পড়ার টেবিলে শুধু দুটো বই রাখার জায়গা। নতুন বই দরকার হলে যেটা **সবচেয়ে অনেকদিন ছোঁওনি** সেটাই তাক-এ ফেরত দাও। প্রতিবার কোনো বই পড়লে সেটা আবার টেবিলের সামনে চলে আসে। dict হলো তোমার মনে রাখা "কোন বই কোথায়", আর list হলো টেবিলে বাঁ-থেকে-ডান recency সাজানো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **05 hashing** ([../../05-hashing/](../../05-hashing/README.md)) থেকে: একটা dict রাখি `key -> node`, যাতে যেকোনো key-কে O(1)-এ খুঁজে তার ঠিক জায়গায় পৌঁছানো যায়।
- **03 linked lists** ([../../03-linked-list/](../../03-linked-list/README.md)) থেকে: একটা doubly linked list-এ সব entry-কে "recency order"-এ সাজিয়ে রাখি; কোনো node-কে O(1)-এ unlink করা আর head-এর পাশে নিয়ে আসা।
একা hashmap বলতে পারে "key আছে কি না", কিন্তু order রাখতে পারে না; একা linked list order রাখে কিন্তু খুঁজতে O(n)। দুটো মিললেই O(1) get/put।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো 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) লাগত।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো একসাথে: **(a) একটা hashmap** `key -> node`, আর **(b) একটা doubly linked list** দুটো sentinel (dummy `head`, dummy `tail`) সহ। Sentinel রাখলে কোনো edge case (খালি list, প্রথম/শেষ node) আলাদা করে ভাবতে হয় না — এটাই 03 linked lists-এর dummy-head trick।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
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)-এ রাখে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: শুধু একটা list of (key, value) রাখি। `get`-এ list scan করে key খুঁজি, পেলে সেটাকে শেষে সরাই (most-recent চিহ্ন)। `put`-এ full হলে list-এর সামনের element ফেলে দিই।
```text
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)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
list scan করে key খোঁজা মানে প্রতিটা `get`/`put` **O(n)** — n element-এর মধ্যে linear search, আর middle থেকে সরাতে আরও shift। বড় cache-এ এটা ধীর। কারণ আমরা "key থেকে position" mapping রাখছি না — ঠিক এটাই hashmap (05) দূর করতে আসে: scan-কে O(1) lookup বানায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **দুটো প্রশ্ন আলাদা — "key কোথায়?" আর "সবচেয়ে পুরনো কোনটা?"** একটা structure দুটোর দুটোই fast দিতে পারে না। তাই দুটো structure পাশাপাশি রাখো — hashmap উত্তর দেয় প্রথমটার, doubly list দ্বিতীয়টার — আর তাদের একই node object দিয়ে জুড়ে দাও যাতে একটায় খুঁজে অন্যটায় O(1)-এ কাজ করা যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
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 থেকে দুই জায়গায়)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "একটা structure দিয়ে সব করব" ভাবা ছাড়ো। ভাবো "প্রতিটা entry একই সময়ে দুই জায়গায় বাস করে — dict-এ নাম দিয়ে, list-এ বয়স দিয়ে।" একই node দুই view-তে থাকায় lookup আর reorder দুটোই O(1)।
### ছবিতে বোঝা {#7-visual-explanation}
```text
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-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`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
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `_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 মিলিয়ে দেখা {#17-output-walkthrough}
`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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(1)** প্রতি operation — dict lookup O(1), আর doubly list-এ unlink/add_front constant pointer কাজ। কোনো scan নেই।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(capacity)** — dict-এ আর list-এ মিলিয়ে বড়জোর `capacity`-টা node; cache কখনো এর বেশি রাখে না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- 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 সহজ।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: hashmap দিয়ে O(1) key lookup (05 hashing-এর [../../05-hashing/](../../05-hashing/README.md)) + doubly linked list-এ O(1) node insert/delete আর dummy-head pattern (03 linked lists-এর [../../03-linked-list/](../../03-linked-list/README.md))। এই দুটো cold অবস্থায় জানা থাকলে LRU-র design নিজে থেকেই দাঁড়িয়ে যায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- LFU Cache (least-frequently-used; frequency bucket + dict, আরও এক স্তর) —