# Google-Style Patterns

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

---

## The commonly reported emphasis

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

- **Graphs আর implicit graphs।** যেসব problem-এ graph-টা একটা গল্পের ভেতরে লুকানো — এক অক্ষরে আলাদা শব্দ, একটা puzzle-এর state, একটা grid-এর cell — আর প্রথম insight-টা হলো "এটা একটা graph; node হলো X আর edge হলো Y।"
- **Dynamic programming।** বিশেষ করে যেসব problem-এ state definition-ই পুরো যুদ্ধ (folder 12-এর 5-step doctrine-টাই ঠিক narrate করার script)।
- **Deliberate ambiguity।** Report অনুযায়ী prompt-গুলো ইচ্ছে করেই under-specified: input size, duplicates, tie-breaking, এমনকি exact goal-টাও *তোমার* জন্য ছেড়ে রাখা — clarifying প্রশ্ন দিয়ে pin করতে হবে। ভুল precise problem solve করা দুটো বাড়তি প্রশ্ন করার চেয়ে খারাপ score পায়।
- **Scaling follow-ups।** Report অনুযায়ী একটা solved problem-এর পরে আসে "এবার input 100× বড় / streamed / memory-তে আঁটে না — কী বদলাবে?" Follow-up-টা test করে তোমার solution-টা একটা idea ছিল, নাকি মুখস্থ snippet।
- **Complexity fluency।** Complexity-টা যা, *কেন* তা — বলতে পারা, আর next-best বিকল্পটার খরচ কত, তাও।

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

- প্রতিটা prompt-কে ইচ্ছাকৃত অসম্পূর্ণ ধরো। *প্রতিবার* 2–3-টা clarifying প্রশ্ন দিয়ে শুরু করো, এমনকি উত্তর জানো মনে হলেও — অভ্যাসটাই skill।
- Code-এর আগে abstraction-টা মুখে বলো: "আমি এটাকে একটা graph হিসেবে model করব, যেখানে node হলো ___ আর edge হলো ___" বা "আমার DP state হলো ___।" Model-এর নাম বলাটাই credit-এর বেশিরভাগ।
- Solve করার পরে নিজের solution-টাকেই আক্রমণ করো: "n যদি 10⁹ হতো, এটা ভাঙত কারণ ___; আমি ___-এ switch করতাম।" জিজ্ঞেস হওয়ার আগেই follow-up-টা practice করা।

## Representative public problems for this style

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

Table-টা পড়ার guide:

- **Underlying tools** হলো সেটাই, যা একটা mock-এর প্রথম পাঁচ মিনিটের মধ্যে *মুখে নাম ধরে বলতে* পারা উচিত — এই style-এ differentiator হলো নামটা বলা, final code নয়।
- **Taught in** হলো পিছু হটার পথ: কোনো tool নড়বড়ে মানে mock schedule থামিয়ে আগে ওই folder-এর tracker আবার করা।
- এগুলো mock হিসেবে solve করো ([README.md](README.md)-এর 45-minute format), study problem হিসেবে নয় — এই folder ধরে নেয় tool-গুলো আগেই শেখা।

| Problem (described in our own words) | Link | Underlying tools | Taught in |
| --- | --- | --- | --- |
| Word Ladder — দুটো শব্দের মধ্যে এক-অক্ষর বদলের shortest chain | [LeetCode 127](https://leetcode.com/problems/word-ladder/) | Implicit graph + BFS shortest path | [../09-graphs/](../09-graphs/README.md), [../05-hashing/](../05-hashing/README.md) |
| Number of Islands — একটা grid-এ connected জমির তাল গোনো | [LeetCode 200](https://leetcode.com/problems/number-of-islands/) | Grid as graph + flood fill (BFS/DFS) | [../09-graphs/](../09-graphs/README.md) |
| Course Schedule — prerequisite দিয়ে কি সব course শেষ করা যায়? | [LeetCode 207](https://leetcode.com/problems/course-schedule/) | Cycle detection / topological sort | [../09-graphs/topological-sort.md](../09-graphs/topological-sort.md) |
| Longest Increasing Subsequence | [LeetCode 300](https://leetcode.com/problems/longest-increasing-subsequence/) | Anchored state-এর DP; O(n log n) follow-up | [../12-dynamic-programming/](../12-dynamic-programming/README.md) |
| Word Break — একটা string-কে dictionary-শব্দে ভাগ করো | [LeetCode 139](https://leetcode.com/problems/word-break/) | Prefix DP + hash set | [../12-dynamic-programming/](../12-dynamic-programming/README.md), [../05-hashing/](../05-hashing/README.md) |
| Edit Distance — দুই string-এর মধ্যে minimum edit | [LeetCode 72](https://leetcode.com/problems/edit-distance/) | Two-sequence string DP | [../12-dynamic-programming/](../12-dynamic-programming/README.md) |
| Median of Two Sorted Arrays — মিলিত median দ্রুত খোঁজো | [LeetCode 4](https://leetcode.com/problems/median-of-two-sorted-arrays/) | Partition-এর উপর binary search | [পূর্বশর্ত](../01-math-based-programming-fundamentals/07-binary-search-on-answer/README.md) (binary search) |
| Longest Consecutive Sequence — unsorted input-এ পরপর integer-এর longest দৌড় | [LeetCode 128](https://leetcode.com/problems/longest-consecutive-sequence/) | Hash set + চালাক scan start | [../05-hashing/](../05-hashing/README.md) |
| Count of Smaller Numbers After Self | [LeetCode 315](https://leetcode.com/problems/count-of-smaller-numbers-after-self/) | BIT + compression দিয়ে order statistics | [../11-segment-tree-and-fenwick-tree/](../11-segment-tree-and-fenwick-tree/README.md) |
| Trapping Rain Water — দেয়ালের মাঝে জমা পানি | [LeetCode 42](https://leetcode.com/problems/trapping-rain-water/) | Two pointers / monotonic stack | [../02-arrays-and-strings/](../02-arrays-and-strings/README.md), [hard-patterns.md](hard-patterns.md) |
| Serialize and Deserialize Binary Tree — round-trip encoding design করো | [LeetCode 297](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/) | Tree traversal + format design (ambiguity practice) | [../07-trees/](../07-trees/README.md) |
| Unique Paths — lattice path গোনা, "blocked cell হলে?" follow-up-সহ | [LeetCode 62](https://leetcode.com/problems/unique-paths/) | Grid DP + follow-up scaling | [../12-dynamic-programming/](../12-dynamic-programming/README.md) |

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

1. [README.md](README.md)-এর **45-minute mock format চালাও**, কিন্তু phase 1-কে (clarify) বাড়তি ওজন দাও: তুমি যে অন্তত তিনটা assumption বাছলে, আর কেন — লিখে রাখো।
2. **নিজের উপর একটা follow-up চাপাও।** প্রতিটা solve-এর পরে 5 মিনিট বাড়তি খরচ করো এগুলোর একটার উত্তরে: "input একটা stream", "input 1000× বড়", "এবার শুধু count নয়, আসল solution-টা return করো"। বদলটা sketch করো; code করতেই হবে এমন নয়।
3. **Model-টা narrate করো।** Graph problem-এ node/edge মুখে না বলে কখনো coding শুরু কোরো না। DP-তে state-এর বাক্যের আগে কখনোই না।
4. উপরের table-এর **আক্রমণের order**: Number of Islands → Course Schedule → Word Ladder (graphs warm to hot), তারপর Word Break → LIS → Edit Distance (DP warm to hot), তারপর বাকিগুলো।
5. **Weakness routing:** graph modeling step-এ জমে গেলে ফিরে যাও [../09-graphs/](../09-graphs/README.md)-এ; state definition-এ জমে গেলে [../12-dynamic-programming/state-transition-thinking.md](../12-dynamic-programming/state-transition-thinking.md)-এ।

## A clarifying-question bank for ambiguous prompts

Ambiguity সামলানো একটা trainable script, talent নয়। এগুলো একটা card-এ রাখো আর প্রতিটা mock-এর phase 1-এ প্রাসঙ্গিকগুলো ছোড়ো:

- **Size and scale:** "n কত বড় হতে পারে — শত, নাকি million? Input কি memory-তে আঁটে?"
- **Value ranges:** "Value কি negative হতে পারে? Zero? Duplicated? কত বড়?"
- **Structure guarantees:** "Input কি sorted? Connected? Acyclic? Tree কি empty হতে পারে?"
- **Output contract:** "Count চাও, value, নাকি আসল solution reconstruct করা? কয়েকটা valid উত্তরের যেকোনোটা, নাকি নির্দিষ্ট কোনো tie-break?"
- **Degenerate inputs:** "Empty input / কোনো valid উত্তর না থাকলে কী হবে — -1 return, empty list, নাকি raise?"
- **Mutation rights:** "Input-টা কি in place modify করতে পারি, নাকি অক্ষত রাখতে হবে?"

তারপর solve করার আগে *তোমার বাছা assumption-গুলো মুখে বলো*: "আমি ধরছি সর্বোচ্চ 10⁵ শব্দ, শুধু lowercase, আর chain length return করব, impossible হলে 0।" Assumption বাছা আর ঘোষণা করাটাই demonstrated skill।

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

| Failure mode | What it looks like | Fix |
| --- | --- | --- |
| না-জিজ্ঞেস-করা problem solve করা | ভুল spec-এর জন্য 20 মিনিটের সুন্দর solution | Phase 2-এর আগেই problem-টা আবার বলো আর সম্মতি নাও |
| Model-এর বাক্যটা skip করা | "Node হলো X, edge হলো Y" ছাড়াই code হাজির | কড়া নিয়ম: abstraction মুখে না বলা পর্যন্ত code নয় |
| মুখস্থ-solution-এর ধস | Main solution নিখুঁত, scaling follow-up-এ পুরো জমে যাওয়া | প্রতি practice problem-এ নিজের উপর একটা follow-up, সবসময় |
| হাত-নাড়া complexity | "এটা মোটামুটি n log n-এর মতো?" | Derive করো: states × work per state, মুখে বলে |
| DP state design নয়, আন্দাজ | Transition বারবার fail করে, আতঙ্কে rewrite | Folder 12-এর পুরো 5-step doctrine চালাও, কাগজে |
| ভাবার সময় নীরবতা | 90 সেকেন্ডের চুপচাপ মানে আটকে গেছ বলে মনে হয় | Dead end-গুলোও narrate করো: "এখানে sorting কাজে দিচ্ছে না কারণ..." |

## A one-week practice block for this style

| Day | Work | Focus |
| --- | --- | --- |
| 1 | Number of Islands + Course Schedule (mocks) | Graph model-টা মুখে বলা |
| 2 | Word Ladder (mock) + wildcard-bucket optimization-টা লেখো | Implicit graphs + একটা scaling choice |
| 3 | Word Break + LIS (mocks) | State-এর বাক্য, code-এর আগে বলা |
| 4 | Edit Distance (mock) + তার table হাতে আবার derive করো | Two-dimensional state fluency |
| 5 | Longest Consecutive Sequence + Trapping Rain Water (mocks) | Obvious sort-এর ওপারে হাত বাড়ানো |
| 6 | Median of Two Sorted Arrays (mock, 60 min অনুমোদিত) | Partition-এর উপর binary search — এখানকার কঠিনতম একক idea |
| 7 | সপ্তাহের সবচেয়ে খারাপ rubric score-টা cold অবস্থায় আবার চেষ্টা করো | Loop-টা বন্ধ করা |

প্রতিটা দিন শেষ হয় দিনের একটা problem-এর উপর পাঁচ মিনিটের self-imposed follow-up দিয়ে ("streamed হলে? 1000× বড় হলে? আসল path লাগলে?")।

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

> "Solve করার আগে: dictionary-তে কি শব্দ repeat করতে পারে? Alphabet কি শুধু lowercase? মোটামুটি কয়টা শব্দ — 10² না 10⁵? ... ঠিক আছে। আমি এটাকে একটা implicit graph হিসেবে model করব: node হলো শব্দ, edge জোড়ে এক অক্ষরে আলাদা শব্দদের। Shortest chain মানে BFS। সব edge naively বানালে O(n²·L); n 10⁵ পর্যন্ত গেলে সেটা too slow, তাই আমি বরং wildcard bucket generate করব — সেটা O(n·L²) preprocessing..."

ওখানকার প্রতিটা বাক্য rubric point কামায়: clarification, model-এর নাম, complexity আর scaling-সচেতন একটা design choice — code-এর একটা লাইন জন্মানোর আগেই।

## Readiness checklist for this style

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

- [ ] প্রতিটা mock-এ অন্তত তিনটা clarifying প্রশ্ন করো, আগে দেখা problem-সহ।
- [ ] প্রতিবার, কোনো code লেখার আগে graph model বা DP state-এর বাক্যটা বলো।
- [ ] প্রতি problem-এ একটা self-imposed scaling follow-up-এর উত্তর পাঁচ মিনিটের sketch-এর মধ্যে দিতে পারো।
- [ ] Complexity মনে করার বদলে derive করো — states × work (বা nodes + edges) হিসেবে।
- [ ] Table থেকে তোমার শেষ তিনটা mock [README.md](README.md)-এর rubric-এ 12+/16 পেয়েছে।