Microsoft-Style Patterns¶
আগে disclaimer: এখানে "Microsoft-style" মানে সেই publicly discussed pattern emphasis, যা interview-prep community-রা — বিশেষ করে Tech Interview Handbook আর NeetCode — এই ধরনের interview-র জন্য সচরাচর report করে। নিচের কোনো নির্দিষ্ট problem Microsoft-এ জিজ্ঞেস করা হয়েছিল — এমন কোনো দাবি এটা নয় (NOT a claim)।
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 | Three-pointer surgery | ../04-linked-lists/ |
| Linked List Cycle — O(1) space-এ loop ধরো | LeetCode 141 | Slow/fast pointers | ../04-linked-lists/ |
| Merge Two Sorted Lists | LeetCode 21 | Dummy-head technique | ../04-linked-lists/ |
| Remove Nth Node From End of List — এক pass-এ | LeetCode 19 | Gap-সহ two pointers | ../04-linked-lists/ |
| Reorder List — সামনের আর পেছনের অর্ধেক in place interleave করো | LeetCode 143 | Find middle + reverse + merge (3-টা sub-skill) | ../04-linked-lists/ |
| Validate Binary Search Tree | LeetCode 98 | Range-passing recursion (classic edge-case ফাঁদ) | ../07-trees/ |
| Lowest Common Ancestor of a Binary Tree | LeetCode 236 | Post-order reasoning | ../07-trees/ |
| Binary Tree Level Order Traversal | LeetCode 102 | Level boundary-সহ BFS | ../07-trees/, ../09-graphs/ |
| Serialize and Deserialize Binary Tree | LeetCode 297 | Traversal + null marker (edge-case-এর ভোজ) | ../07-trees/ |
| Reverse Words in a String — বাড়তি space-ও গুটাও | LeetCode 151 | সাবধানী string parsing | ../02-arrays-and-strings/ |
| String to Integer (atoi) — sign, space, overflow clamping-সহ parse করো | LeetCode 8 | State-by-state parsing, boundary discipline | ../02-arrays-and-strings/ |
| Longest Palindromic Substring | LeetCode 5 | Expand-around-center (odd/even case) | ../02-arrays-and-strings/ |
How to practice this style (এই style কীভাবে practice করবে)¶
README.md-এর 45-minute mock format চালাও, কিন্তু phase 5-কে (test aloud) star বানাও: পুরো 10 মিনিট budget রাখো আর তোমার pre-coding list-এর EVERY edge case আসল code-এর ভেতর দিয়ে হাঁটাও।- একটা edge-case ledger রাখো। যে edge case-গুলো তোমাকে কোনোদিন কামড়েছে, তাদের একটা চলমান file (empty list, single node,
headনিজেই removed, even-length palindrome, leading "+", INT_MIN...)। প্রতিটা mock-এর আগে পড়ো; পরে যোগ করো। - Mutate করার আগে আঁকো। প্রতিটা linked-list problem-এ, pointer code-এর প্রথম লাইনের আগে কাগজে একটা pointer diagram বাধ্যতামূলক। Diagram নেই, code নেই।
- উপরের 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)।
- Weakness routing: pointer নিয়ে যেকোনো বিভ্রান্তি পাঠায়
../04-linked-lists/-এ; tree-তে recursion-এর অস্বস্তি পাঠায়../06-recursion-and-backtracking/-এ, তারপর../07-trees/-এ।
The starter edge-case ledger¶
তোমার নিজের ledger এগুলো দিয়ে seed করো; ভবিষ্যতের প্রতিটা bug একটা করে row যোগ করবে। প্রতিটা mock-এর আগে প্রাসঙ্গিক block-টা পড়ো।
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 আর single-node case-সহ, কারণ ওগুলোতে loop body কখনো চলেই না।"
আগে 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-এর rubric-এ 12+/16 পেয়েছে।