# Amazon-Style Patterns

> আগে disclaimer: এখানে "Amazon-style" মানে সেই *publicly discussed pattern emphasis*, যা interview-prep community-রা — বিশেষ করে [Tech Interview Handbook](https://www.techinterviewhandbook.org/) আর [NeetCode](https://neetcode.io/roadmap) — এই ধরনের interview-র জন্য সচরাচর report করে। নিচের কোনো নির্দিষ্ট problem Amazon-এ জিজ্ঞেস করা হয়েছিল — এমন কোনো দাবি এটা নয় (NOT a claim)। [README.md](README.md)-এর disclaimer-টা দেখো।

---

## The commonly reported emphasis

Community-র আলোচনা ধারাবাহিকভাবে এই interview style-টাকে এদিকে ঝুঁকে থাকা বলে বর্ণনা করে:

- **Grid-এর উপর BFS আর shortest steps।** Package, warehouse, delivery বা ছড়িয়ে-পড়া process-এর গল্প, যেগুলো নেমে আসে "grid-এ minimum steps" বা "সবকিছুতে পৌঁছাতে কতক্ষণ"-এ — multi-source BFS এখানে বারবার ফেরা star।
- **Heaps আর top-K।** "The K best / closest / most frequent" — এই ধরনের ভাষা, প্রায়ই streaming flavor-এ, যেখানে data আসতেই থাকে।
- **Intervals।** Interval merge করা, overlap করা আর schedule করা — meeting, delivery, time window।
- **String parsing আর counting।** Log line, product ID, frequency-র প্রশ্ন — exotic algorithm নয়, hashmap-আর-string-এর খাটুনে ঘোড়া।
- **Customer-scenario framing।** Report অনুযায়ী problem-গুলো মোড়ানো থাকে concrete operational গল্পে ("a customer wants...", "the warehouse needs...")। মোড়কটা ফালতু — *শুধু* ভেতরে লুকানো constraint-গুলো ছাড়া — একবার পড়ো গল্পের জন্য, একবার সংখ্যার জন্য।
- **Behavioral interleaving।** Report অনুযায়ী coding round-গুলো leadership-principle প্রশ্নের সাথে সময় ভাগ করে; ঝরঝরে, দ্রুত problem setup practice করা তোমার coding মিনিটগুলো বাঁচায়।

## The thinking posture to practice (যে ভঙ্গিটা practice করবে)

- **এক বাক্যে problem-টার গল্প খোলো (de-story)।** "Package-রা প্রতি মিনিটে neighbor-দের পচন ছড়ায়" → "multi-source BFS, উত্তর হলো last level।" Translation-এর reflex-টা train করো।
- **Trigger word-গুলো শোনো।** "K closest / K most frequent / K largest" → size K-এর heap। "Overlapping meetings / merge time windows" → start দিয়ে sort, তারপর sweep। "Count occurrences / group by" → hashmap।
- **হাতে-কলমে tradeoff-টা বলো।** Report অনুযায়ী এই style পুরস্কার দেয় এমন কথায়: "heap দেয় O(n log k) আর stream সামলায়; full sort O(n log n) কিন্তু সহজ — stream-এর framing দেখে, heap" — একটা সচেতন, মুখে-বলা choice।

## Representative public problems for this style

সবগুলোই public LeetCode problem, বাছা হয়েছে কারণ এরা উপরের *reported emphasis*-টা exercise করায় — প্রতিটা map করা সেই repo folder-এ, যেটা tool-টা শেখায়।

Table-টা পড়ার guide:

- **Underlying tools** হলো তোমার de-storying-এর target: official statement একবার পড়েই এই column-এর content নিজে লিখতে পারা উচিত।
- **Taught in** হলো tool নড়বড়ে হলে পিছু হটার পথ — folder-টা ঠিক করো, তারপর ফেরো।
- একটা entry (Meeting Rooms II) LeetCode premium; না পেলে একই pattern free-তে practice করো Merge Intervals plus [hard-patterns.md](hard-patterns.md)-এর combo 3-এর heap-of-end-times idea দিয়ে।

| Problem (described in our own words) | Link | Underlying tools | Taught in |
| --- | --- | --- | --- |
| Rotting Oranges — প্রতিটা কমলায় পচন পৌঁছাতে কত মিনিট, নাকি কখনোই না | [LeetCode 994](https://leetcode.com/problems/rotting-oranges/) | Level ধরে multi-source BFS | [../09-graphs/](../09-graphs/README.md) |
| Number of Islands — connected জমির তাল গোনো | [LeetCode 200](https://leetcode.com/problems/number-of-islands/) | Grid flood fill | [../09-graphs/](../09-graphs/README.md) |
| Merge Intervals — overlapping range-গুলো গুটিয়ে ফেলো | [LeetCode 56](https://leetcode.com/problems/merge-intervals/) | Sort + linear sweep | [পূর্বশর্ত](../02-arrays-and-strings/README.md), [hard-patterns.md](hard-patterns.md) |
| Meeting Rooms II — সব meeting-এর জন্য minimum রুম | [LeetCode · Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/) (premium) | Intervals + end time-গুলোর min-heap | [../08-heap-priority-queue/](../08-heap-priority-queue/README.md), [hard-patterns.md](hard-patterns.md) |
| Kth Largest Element in an Array | [LeetCode 215](https://leetcode.com/problems/kth-largest-element-in-an-array/) | Size K-এর heap (বা quickselect) | [../08-heap-priority-queue/](../08-heap-priority-queue/README.md) |
| Top K Frequent Elements | [LeetCode 347](https://leetcode.com/problems/top-k-frequent-elements/) | Hashmap count + heap | [../05-hashing/](../05-hashing/README.md), [../08-heap-priority-queue/](../08-heap-priority-queue/README.md) |
| K Closest Points to Origin | [LeetCode 973](https://leetcode.com/problems/k-closest-points-to-origin/) | Size K-এর max-heap | [../08-heap-priority-queue/](../08-heap-priority-queue/README.md) |
| Merge k Sorted Lists — k-টা sorted stream-কে একটায় মেশাও | [LeetCode 23](https://leetcode.com/problems/merge-k-sorted-lists/) | K-টা head-এর উপর heap + linked lists | [../08-heap-priority-queue/](../08-heap-priority-queue/README.md), [../03-linked-list/](../03-linked-list/README.md) |
| LRU Cache — fixed-size cache design করো, least recently used-কে evict করে | [LeetCode 146](https://leetcode.com/problems/lru-cache/) | Hashmap + doubly linked list | [../05-hashing/](../05-hashing/README.md), [../03-linked-list/](../03-linked-list/README.md) |
| Group Anagrams — অক্ষর-content দিয়ে শব্দ bucket করো | [LeetCode 49](https://leetcode.com/problems/group-anagrams/) | Canonical key + hashmap | [../05-hashing/](../05-hashing/README.md), [../02-arrays-and-strings/](../02-arrays-and-strings/README.md) |
| Minimum Window Substring — সব দরকারি char ধারণ করা smallest window | [LeetCode 76](https://leetcode.com/problems/minimum-window-substring/) | Sliding window + counting hashmap | [../02-arrays-and-strings/](../02-arrays-and-strings/README.md), [hard-patterns.md](hard-patterns.md) |
| Word Ladder — এক-অক্ষর-বদলের shortest chain | [LeetCode 127](https://leetcode.com/problems/word-ladder/) | Implicit graph-এ BFS | [../09-graphs/](../09-graphs/README.md) |

## How to practice this style (এই style কীভাবে practice করবে)

1. [README.md](README.md)-এর **45-minute mock format চালাও**, একটা "de-story" step যোগ করে: phase 2-এর আগে problem-টা গল্পবিহীন এক বাক্যে লেখো আর original constraint-গুলোর সাথে মিলিয়ে নাও।
2. **Trigger word drill করো।** Flashcard বানাও: সামনে phrase-টা ("k most frequent", "merge time windows", "spreads each minute"), পেছনে tool-টা। সপ্তাহে এক ঘণ্টার চেয়ে দিনে পাঁচ মিনিট ভালো।
3. **সময়ের চাপে practice করো।** এই style-এর round-গুলো report অনুযায়ী behavioral প্রশ্নের সাথে সময় ভাগ করে, তাই 45-এ solve করা problem-গুলোর মাঝেমধ্যে 30-minute version চালাও — novelty নয়, fluency।
4. উপরের table-এর **আক্রমণের order**: Group Anagrams → Top K Frequent → Kth Largest (hashmap/heap warm-up), তারপর Rotting Oranges → Number of Islands (grids), তারপর Merge Intervals → Meeting Rooms II (intervals), শেষে Merge k Sorted Lists, LRU Cache আর Minimum Window Substring (combo-গুলো)।
5. **Weakness routing:** heap-এর mechanics-এ ইতস্তত করলে যাও [../08-heap-priority-queue/](../08-heap-priority-queue/README.md)-এ; window-র invariant-এ হোঁচট খেলে [../02-arrays-and-strings/](../02-arrays-and-strings/README.md)-এর sliding-window pattern-এ।

## The de-storying drill, worked twice (দুবার করে দেখানো)

গল্প → tool-এর translation-ই এই style-এর core muscle। Translation-টার দুটো worked example:

```text
STORY:  "Each minute, every rotten orange spoils its fresh up/down/left/right
         neighbors. How many minutes until nothing fresh remains — or is it
         impossible?"

STRIP:   simultaneous sources -> spread one layer per tick -> need the last tick
TOOL:    multi-source BFS; seed the queue with ALL rotten cells at t = 0;
         answer = depth of the final layer; leftover fresh cells -> -1
```

```text
STORY:  "Meetings have start and end times. What is the smallest number of
         rooms so that no two meetings share a room while overlapping?"

STRIP:   max number of intervals alive at any single moment
TOOL:    sort by start; min-heap of end times; pop ended meetings before
         each new one; the heap's peak size is the answer
```

নিচের table-এর প্রতিটা problem-এর জন্য এই strip-and-name step-টা *লিখে* করো, যতদিন না translation-টা নিজে থেকেই ঘটে।

## Common failure modes in this style (and the fix) (সাধারণ ভুল আর সমাধান)

| Failure mode | What it looks like | Fix |
| --- | --- | --- |
| গল্পে ডুবে যাওয়া | Scenario তিনবার পড়া, উদ্বেগ বাড়তে থাকা | একবার পড়ো গল্পের জন্য, একবার ONLY constraint/সংখ্যার জন্য |
| Size-k heap-এ চললেও full sort | Streaming top-K প্রশ্নে O(n log n) উত্তর | "K of ___" শুনলেই → আর কিছু ভাবার আগে বলো "heap of size K" |
| ভুল heap polarity | Min দরকার ছিল, max-heap বসানো (বা Python-এর min-only `heapq` নিয়ে গোলমাল) | মুখে বলো: "Best K-এর মধ্যে WORST-টা আমি উপরে রাখি, তাই..." |
| Interval-এর প্রান্ত-ছোঁয়া ভুলে যাওয়া | "[1,3] কি [3,5]-এর সাথে overlap করে?" — চুপচাপ আর ভুলভাবে ঠিক করা | এটাকে প্রতিবার phase-1-এর clarifying প্রশ্ন বানাও |
| Level boundary ছাড়া BFS | Reachability সঠিক, মিনিটের হিসাব ভুল | Level-এর size track করো বা (cell, time) pair রাখো — কোনটা করছ narrate করো |
| Setup-এ তাড়াহুড়ো (সময়-চাপের অভ্যাস) | নাহলে-সহজ problem-এ এলোমেলো bookkeeping bug | আগেই-solve-করা problem-এ 30-minute squeezed format practice করো |

## A one-week practice block for this style

| Day | Work | Focus |
| --- | --- | --- |
| 1 | Group Anagrams + Top K Frequent (mocks) | Hashmap reflex + heap-of-K |
| 2 | Kth Largest + K Closest Points (mocks) | Heap polarity, মুখে বলা |
| 3 | Rotting Oranges + Number of Islands (mocks) | Level গোনাসহ multi-source BFS |
| 4 | Merge Intervals + Meeting Rooms II (mocks) | Sort-then-sweep / heap-of-ends জুটিটা |
| 5 | Merge k Sorted Lists (mock) | Heap + linked list combo |
| 6 | LRU Cache (mock, 60 min অনুমোদিত) | Hashmap + doubly-linked-list-এর design আলাপ |
| 7 | Minimum Window Substring (mock) + সপ্তাহের সবচেয়ে খারাপ score-টা আবার করো | Window invariant, তারপর loop বন্ধ |

প্রতিটা দিন শেষ করো তোমার flashcard-স্তূপে একটা লেখা de-storying card যোগ করে (উপরে গল্প, নিচে strip + tool)।

## What "good" sounds like in this style ("ভালো" শুনতে কেমন)

> "গল্পটা খুলে ফেলছি: এটা হলো 'একটা grid cover করতে multi-source spread-এর minimum মিনিট' — multi-source BFS, যেখানে সব পচা cell time 0-তে queue-তে শুরু করে আর উত্তর হলো last layer-এর depth। Handle করার edge case: কোনো fresh কমলাই নেই (উত্তর 0), আর unreachable fresh কমলা (উত্তর -1)। Constraint বলছে grid সর্বোচ্চ 10×10, তাই O(rows·cols) BFS দরকারের চেয়ে ঢের বেশি fast..."

এক বাক্যে de-storied, tool-এর নাম বলা, coding-এর আগে edge case-গুলোর list — rubric ঠিক এটাকেই পুরস্কার দেয়।

## Readiness checklist for this style

পরের style file-এ rotate করতে তৈরি, যখন এগুলো সবকটায় সৎভাবে টিক দিতে পারবে:

- [ ] Table-এর যেকোনো problem দুই মিনিটের মধ্যে এক tool-নাম-বলা বাক্যে de-story করতে পারো।
- [ ] "K most/closest/largest" শুনলে অন্য কোনো চিন্তার আগেই "heap of size K" trigger হয়।
- [ ] Sort-then-sweep interval skeleton আর heap-of-end-times skeleton — দুটোই মুখস্থ থেকে লিখতে পারো।
- [ ] একটা চেনা problem 30-minute squeezed format-এ পরিষ্কারভাবে চালাতে পারো।
- [ ] Table থেকে তোমার শেষ তিনটা mock [README.md](README.md)-এর rubric-এ 12+/16 পেয়েছে।