Problem link ও উৎস
- **Original source:** Classic system-design-flavored data structure exercise
- **Platform:** LeetCode —
- **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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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-টা ফেলে দাও।
```text
capacity = 2
put(1,1) put(2,2) get(1)=1 put(3,3)→2 বাদ get(2)=-1 ...
```
### Input ও output {#8-example-input-and-output}
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ডেস্কে কাগজের একটা স্তূপ ভাবো, capacity সীমিত। কোনো কাগজ ব্যবহার করলেই সেটা তুলে **স্তূপের একদম উপরে** রাখো (সদ্য-ব্যবহৃত)। জায়গা ফুরালে **একদম নিচের** কাগজটা (সবচেয়ে দিন ছোঁয়া হয়নি) ফেলে দাও। আর কোন কাগজ কোথায় আছে দ্রুত জানতে একটা index-খাতা (hash map) রাখো — খুঁজতে পুরো স্তূপ ঘাঁটতে হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: একটা সাধারণ list (বা array) of `(key, value)` রাখো, আর সাথে একটা "শেষ কবে ব্যবহার" timestamp। `get`/`put`-এ পুরো list scan করে key খোঁজো; evict করতে পুরো list scan করে সবচেয়ে পুরোনো timestamp খুঁজে ফেলো।
```text
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)-এর রহস্য।
### ছবিতে বোঝা {#7-visual-explanation}
DLL: `head` ও `tail` sentinel-এর মাঝখানে বাস্তব node থাকে; head-এর পাশটি most recent। capacity = 2:
```text
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-এ ধাপে ধাপে {#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`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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 থেকেও মুছে দাও।
### Output মিলিয়ে দেখা {#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!`।
### JavaScript ও test cases {#25-javascript-solution-with-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 {#26-typescript-solution-with-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