# একাধিক ধারণা মিলিয়ে problem সমাধান

[অধ্যায়ের সূচি](README.md) · [মূল প্রশ্ন ও সব নোট](problems/README.md) · [কঠিন pattern](hard-patterns.md)

এই অধ্যায়ে নতুন data structure মুখস্থ করার চেয়ে পরিচিত structure **কেন একসঙ্গে লাগছে** তা ব্যাখ্যা করবেন। একটি component যে প্রশ্নের উত্তর দ্রুত দিতে পারে না, অন্য component সেটি সামলায়।

## পড়া ও অনুশীলনের ক্রম

1. [Master tracker](problems/README.md) থেকে পরিচিত একটি medium problem নিন। Source হলো মূল প্রশ্ন, Note file হলো এই সাইটের সমাধান।
2. নিজের ভাষায় input, output, constraints এবং একটি ছোট উদাহরণ লিখুন।
3. সরল সমাধানের কোন operation বারবার ধীর হচ্ছে তা চিহ্নিত করুন।
4. সেই operation-এর জন্য structure বাছুন; প্রতিটির দায়িত্ব এক বাক্যে লিখুন।
5. Code-এর আগে পূর্ণ ছোট trace, পরে edge case এবং complexity লিখুন।

[Google-style](google-style.md), [Amazon-style](amazon-style.md) ও [Microsoft-style](microsoft-style.md) পৃষ্ঠাগুলো আলাদা practice emphasis হিসেবে পড়ুন। কোনো company-তে নির্দিষ্ট প্রশ্ন আসার নিশ্চয়তা হিসেবে নয়।

## একটি প্রোগ্রাম: LRU cache

Capacity 2। Key দিয়ে দ্রুত value পেতে **hash map** লাগে। শেষ কবে ব্যবহার হয়েছে সেই order বদলাতে এবং সবচেয়ে পুরোনো entry বাদ দিতে **doubly linked list** লাগে। শুধু map এই order update-এর কাজ করে না; শুধু list দিয়ে key খুঁজতে scan লাগে।

```mermaid
flowchart LR
  head["HEAD"] <--> a["key 2 / value 20"]
  a <--> b["key 1 / value 10"]
  b <--> tail["TAIL"]
  map2["map[2]"] --> a
  map1["map[1]"] --> b
```

HEAD-এর কাছে সবচেয়ে সম্প্রতি ব্যবহৃত entry। HEAD ও TAIL হলো dummy node; capacity-তে গোনা হয় না।

| Operation | Recent → old | Hash map | Return |
| --- | --- | --- | --- |
| শুরু | খালি | {} | — |
| put(1,10) | [1] | {1: node1} | — |
| put(2,20) | [2,1] | {1: node1, 2: node2} | — |
| get(1) | [1,2] | একই দুই key | 10 |
| put(3,30) | [3,1] | {1: node1, 3: node3} | 2 বাদ |
| get(2) | [3,1] | অপরিবর্তিত | -1 |
| put(1,11) | [1,3] | একই key, value বদলেছে | — |

প্রতিটি operation-এ গড় `O(1)` hash lookup এবং `O(1)` pointer update। Map ও list-এ একই জীবিত key থাকতে হবে—eviction-এর সময় দুই জায়গা থেকেই মুছতে হবে। [সম্পূর্ণ LRU নোট](problems/021-lru-cache.md) ও [মূল প্রশ্ন](https://leetcode.com/problems/lru-cache/)।

## আরও চারটি সমন্বয়

| Problem | প্রথম ধারণার কাজ | দ্বিতীয় ধারণার কাজ | স্থানীয় নোট |
| --- | --- | --- | --- |
| Word Ladder | BFS কম transformation খোঁজে | Wildcard bucket neighbor খোঁজে | [নোট](problems/022-word-ladder.md) |
| Merge k Lists | প্রতিটি list-এর head পরের candidate | Heap সব head-এর minimum দেয় | [নোট](problems/024-merge-k-sorted-lists.md) |
| Count Smaller After Self | Compression value-কে rank দেয় | Fenwick ছোট rank-এর count দেয় | [নোট](problems/029-count-of-smaller-after-self.md) |
| Longest Increasing Path | বড় neighbor-এর দিকে edge; cycle নেই | Memo প্রতিটি cell-এর উত্তর একবার হিসাব করে | [নোট](problems/028-longest-increasing-path-matrix.md) |

## ৪৫ মিনিটের একটি অনুশীলন

| সময় | লিখিত ফল |
| --- | --- |
| 0–5 মিনিট | Input/output, শর্ত, একটি উদাহরণ |
| 5–12 মিনিট | Brute force এবং কোন operation ধীর |
| 12–20 মিনিট | State/structure, invariant, পুরো ছোট trace |
| 20–35 মিনিট | Implementation |
| 35–42 মিনিট | Empty/minimum, duplicate, boundary এবং সাধারণ case |
| 42–45 মিনিট | Time/space এবং কোন constraint বদলালে পদ্ধতি বদলাবে |

সমাধান দেখে বুঝতে পারা আর নিজে লিখতে পারা আলাদা অর্জন। নোট পড়ার পরে বন্ধ করে ছোট input-এ আবার trace করুন; tracker-এর ব্যক্তিগত status তখনই নিজের অগ্রগতি অনুযায়ী বদলান।