# Microsoft-Style Patterns

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

---

## The commonly reported emphasis

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

- **Linked lists।** Pointer-এর অস্ত্রোপচার — reversal, cycle detection, merge, reorder — যেখানে algorithm সহজ কিন্তু pointer-এর হিসাব রাখাটা নির্মম।
- **Trees।** Traversal, validation, lowest common ancestor, serialization — classic binary-tree toolkit, পরিচ্ছন্নভাবে execute করা।
- **Strings।** Parsing, নিয়মসহ reversal, palindrome, in-place transformation — প্রায়ই আসল পরীক্ষাটা নেয় নোংরা input (বাড়তি space, sign, overflow)।
- **Edge-case discipline-ই core signal।** Report অনুযায়ী এই style exotic algorithm-এর চেয়ে বেশি দেখে তোমার code empty list, single node, all-duplicates array, head-এর cycle, overflow boundary-র integer — এসব survive করে কি না। Testing-এ নিজে যে bug খোঁজো সেটা reportedly তোমার *পক্ষে* গোনা হয়; interviewer যেটা খোঁজে সেটা বিপক্ষে।
- **Clean incremental coding।** পড়া-যায় এমন variable name, ছোট ছোট ধাপ, narrate করা invariant ("এই মুহূর্তে `prev` হলো reversed অংশের head...")।

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

- **প্রতিবার, coding-এর আগেই edge case-গুলোর list বানাও।** যেকোনো list problem-এ: empty, one node, two nodes, cycle। যেকোনো string problem-এ: empty, all-spaces, single char, max length। List-টা মুখে বলো; এটা rubric-এর সোনা।
- **Pointer-গুলো আঁকো।** Linked list-এ, যে pointer আঁকোনি তাকে কখনো নাড়িও না। কাগজে তিনটা বাক্স আর কিছু তীর 90% bug ঠেকায়।
- **Invariant-এর নাম দাও।** "প্রতিটা loop iteration-এর পরে `slow`-এর বাঁয়ের সবকিছু final" — একটা বলা invariant একইসাথে correctness-এর প্রমাণ আর communication-এর জয়।
- Mock-এর phase 5-এ **নিজের code line by line trace করো** — report অনুযায়ী এই style self-testing-কে ভারী ওজন দেয়।

## Representative public problems for this style

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

Table-টা পড়ার guide:

- এখানকার **Underlying tools** ইচ্ছে করেই exotic *নয়* — পরীক্ষাটা execution-এর মানের, তাই নিজেকে judge করো phase 5 (trace) দিয়ে, idea-টা দ্রুত পাওয়া দিয়ে নয়।
- **Taught in** হলো পিছু হটার পথ; pointer-এর গোলমাল বিশেষ করে জমতে থাকে, তাই problem-প্রতি ঠিক না করে গোড়ায় — folder 04-এ — ঠিক করো।
- প্রতিটা block-এর ভেতরের ordering জরুরি: প্রতিটা problem আগেরটার একটা sub-skill reuse করে (যেমন Reorder List = find-middle + reverse + merge, প্রত্যেকটা আগে আলাদা drilled)।

| Problem (described in our own words) | Link | Underlying tools | Taught in |
| --- | --- | --- | --- |
| Reverse Linked List — iteratively আর recursively | [LeetCode 206](https://leetcode.com/problems/reverse-linked-list/) | Three-pointer surgery | [../03-linked-list/](../03-linked-list/README.md) |
| Linked List Cycle — O(1) space-এ loop ধরো | [LeetCode 141](https://leetcode.com/problems/linked-list-cycle/) | Slow/fast pointers | [../03-linked-list/](../03-linked-list/README.md) |
| Merge Two Sorted Lists | [LeetCode 21](https://leetcode.com/problems/merge-two-sorted-lists/) | Dummy-head technique | [../03-linked-list/](../03-linked-list/README.md) |
| Remove Nth Node From End of List — এক pass-এ | [LeetCode 19](https://leetcode.com/problems/remove-nth-node-from-end-of-list/) | Gap-সহ two pointers | [../03-linked-list/](../03-linked-list/README.md) |
| Reorder List — সামনের আর পেছনের অর্ধেক in place interleave করো | [LeetCode 143](https://leetcode.com/problems/reorder-list/) | Find middle + reverse + merge (3-টা sub-skill) | [../03-linked-list/](../03-linked-list/README.md) |
| Validate Binary Search Tree | [LeetCode 98](https://leetcode.com/problems/validate-binary-search-tree/) | Range-passing recursion (classic edge-case ফাঁদ) | [../07-trees/](../07-trees/README.md) |
| Lowest Common Ancestor of a Binary Tree | [LeetCode 236](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/) | Post-order reasoning | [../07-trees/](../07-trees/README.md) |
| Binary Tree Level Order Traversal | [LeetCode 102](https://leetcode.com/problems/binary-tree-level-order-traversal/) | Level boundary-সহ BFS | [../07-trees/](../07-trees/README.md), [../09-graphs/](../09-graphs/README.md) |
| Serialize and Deserialize Binary Tree | [LeetCode 297](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/) | Traversal + null marker (edge-case-এর ভোজ) | [../07-trees/](../07-trees/README.md) |
| Reverse Words in a String — বাড়তি space-ও গুটাও | [LeetCode 151](https://leetcode.com/problems/reverse-words-in-a-string/) | সাবধানী string parsing | [../02-arrays-and-strings/](../02-arrays-and-strings/README.md) |
| String to Integer (atoi) — sign, space, overflow clamping-সহ parse করো | [LeetCode 8](https://leetcode.com/problems/string-to-integer-atoi/) | State-by-state parsing, boundary discipline | [../02-arrays-and-strings/](../02-arrays-and-strings/README.md) |
| Longest Palindromic Substring | [LeetCode 5](https://leetcode.com/problems/longest-palindromic-substring/) | Expand-around-center (odd/even case) | [../02-arrays-and-strings/](../02-arrays-and-strings/README.md) |

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

1. [README.md](README.md)-এর **45-minute mock format চালাও**, কিন্তু phase 5-কে (test aloud) star বানাও: পুরো 10 মিনিট budget রাখো আর তোমার pre-coding list-এর EVERY edge case আসল code-এর ভেতর দিয়ে হাঁটাও।
2. **একটা edge-case ledger রাখো।** যে edge case-গুলো তোমাকে কোনোদিন কামড়েছে, তাদের একটা চলমান file (empty list, single node, `head` নিজেই removed, even-length palindrome, leading "+", INT_MIN...)। প্রতিটা mock-এর আগে পড়ো; পরে যোগ করো।
3. **Mutate করার আগে আঁকো।** প্রতিটা linked-list problem-এ, pointer code-এর প্রথম লাইনের আগে কাগজে একটা pointer diagram বাধ্যতামূলক। Diagram নেই, code নেই।
4. উপরের table-এর **আক্রমণের order**: Reverse Linked List → Merge Two Sorted Lists → Linked List Cycle → Remove Nth Node (pointer fundamentals), তারপর Reorder List (combo-টা), তারপর tree block, তারপর string block — শেষটা atoi (edge-case-এর final boss)।
5. **Weakness routing:** pointer নিয়ে যেকোনো বিভ্রান্তি পাঠায় [../03-linked-list/](../03-linked-list/README.md)-এ; tree-তে recursion-এর অস্বস্তি পাঠায় [../06-recursion-and-backtracking/](../06-recursion-and-backtracking/README.md)-এ, তারপর [../07-trees/](../07-trees/README.md)-এ।

## The starter edge-case ledger

তোমার নিজের ledger এগুলো দিয়ে seed করো; ভবিষ্যতের প্রতিটা bug একটা করে row যোগ করবে। প্রতিটা mock-এর আগে প্রাসঙ্গিক block-টা পড়ো।

```text
LINKED LISTS                          TREES
- empty list (head is None)           - empty tree (root is None)
- single node                         - single node
- exactly two nodes                   - completely skewed (all left / all right)
- operation hits the head itself      - duplicate values (BST validation trap!)
- operation hits the tail             - target node IS the root / IS an ancestor
- cycle present where none expected   - values at int extremes (range-passing)

STRINGS                               NUMBERS
- empty string                        - 0 and negative inputs
- all spaces / all delimiters         - overflow boundaries (clamp behavior)
- single character                    - "+" and "-" signs, leading zeros
- entire string is one token          - division truncation toward zero vs floor
- unicode / case assumptions: ASK
```

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

| Failure mode | What it looks like | Fix |
| --- | --- | --- |
| Diagram ছাড়া pointer-এর অস্ত্রোপচার | Instinct-এ `curr.next = prev` type করা, list নিঃশব্দে হারানো | কাগজে diagram নেই, pointer code নেই — কড়া নিয়ম |
| List-এর বাকিটা হারানো | Save করার আগেই `.next` overwrite করা | মন্ত্র: "save next FIRST" — প্রতিটা reassignment-এর আগে বলা |
| Head/tail special-case-এর bug | List-এর মাঝে কাজ করে, head delete করতে গেলে crash | Default-এ একটা dummy head node নাও; special case-টাই মুছে যায় |
| শুধু parent-এর বিরুদ্ধে BST validate করা | `[5, 1, 7, null, null, 4, 8]` ভুল validator pass করে | (low, high) bound নিচে pass করো; deep-violation case-টা test করো |
| Even-length case ভুলে যাওয়া | Palindrome / middle-of-list code, যেটা শুধু odd সামলায় | প্রতিটা odd test-এর সাথে তার even যমজ, সবসময় |
| Trace ছাড়াই done ঘোষণা | "ঠিকই তো লাগছে" → interviewer off-by-one খুঁজে পায় | Phase 5 non-negotiable: line-by-line, মুখে, কমপক্ষে দুটো edge case |

## A one-week practice block for this style

| Day | Work | Focus |
| --- | --- | --- |
| 1 | Reverse Linked List (দুইভাবে) + Merge Two Sorted Lists (mocks) | আগে diagram; dummy-head-এর অভ্যাস |
| 2 | Linked List Cycle + Remove Nth From End (mocks) | Two-pointer-এর নাচ + head deletion-এর edge case |
| 3 | Reorder List (mock, 60 min অনুমোদিত) | তিনটা sub-skill পরিচ্ছন্নভাবে গাঁথা |
| 4 | Level Order Traversal + Validate BST (mocks) | Level boundary; range-passing recursion |
| 5 | Lowest Common Ancestor + Serialize/Deserialize (mocks) | Post-order reasoning; null-marker discipline |
| 6 | Reverse Words in a String + Longest Palindromic Substring (mocks) | Parsing-এর যত্ন; odd/even center |
| 7 | String to Integer (atoi) (mock) + সপ্তাহের সবচেয়ে খারাপ score-টা আবার করো | Edge-case-এর final boss, তারপর loop বন্ধ |

প্রতিটা mock-এর পরে নতুন bug-গুলো উপরের ledger-এ তোলো — ledger-টা প্রতি সপ্তাহে *আস্তে* বাড়াটাই progress-এর metric।

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

> "Coding-এর আগে আমার edge case: empty list → null return; single node → সে নিজেই নিজের reversal; দুই node — ওটা আমি explicitly trace করব, কারণ ওতে প্রতিটা pointer move একবার করে খাটে। আমার invariant: প্রতিটা loop-এর শুরুতে `prev` হলো already-reversed অংশের মাথা আর `curr` হলো অছোঁয়া অংশের মাথা। ... Code শেষ — এবার `1 → 2` হাতে trace করছি: prev=None, curr=1; save next=2; 1.next=None; prev=1, curr=2; save next=None; 2.next=1 ... return করে 2 → 1। সঠিক — empty case-এ loop চলে না; single-node case-এ একবার চলে এবং node.next=None রেখে সেই node-ই ফেরত দেয়।"

আগে edge case-গুলোর তালিকা, invariant-এর নাম, নিজের trace সম্পন্ন — এই ক্রমটাই *আসলে* এই style-এর scoring rubric।

## Readiness checklist for this style

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

- [ ] নিজেকে মনে না করিয়েই, প্রতিটা problem-এ, coding-এর আগে মুখে edge case-গুলোর তালিকা বলো।
- [ ] কাগজে boxes-and-arrows diagram না থাকলে কখনো pointer code লেখো না।
- [ ] Linked list reverse করা, তার middle খোঁজা আর দুটো list merge করা — মুখস্থ থেকে, bug-free, প্রথম চেষ্টায় পারো।
- [ ] সপ্তাহে phase 5-এ নিজের অন্তত একটা bug নিজে খোঁজো (একটাও না পাওয়ার মানে সাধারণত trace-টা সৎ ছিল না)।
- [ ] তোমার edge-case ledger এ সপ্তাহে গত সপ্তাহের চেয়ে আস্তে বেড়েছে — আসল progress metric।
- [ ] Table থেকে তোমার শেষ তিনটা mock [README.md](README.md)-এর rubric-এ 12+/16 পেয়েছে।