# 13 — Interview Master Problems

> **এখান থেকে শুরু করুন:** [সহজ ব্যাখ্যা, শেখার ক্রম ও বাস্তব ব্যবহার](learning-guide.md) → [প্রশ্ন, official link ও স্থানীয় সমাধান](problems/README.md)। [উৎসের তালিকা](source-map.md)-এ reference পাবেন।

> Capstone-টা। আগের প্রতিটা folder একটা করে tool শিখিয়েছে; আসল interview problem তোমার হাতে ধরিয়ে দেয় একটা গল্প, যেটার চুপিচুপি দরকার একসাথে দু-তিনটে tool। এই section train করে সেই *mixing*-টা।

---

## What this section is (এই section-টা কী)

এটা কোনো নতুন data structure নয়। এটা একটা **cross-topic problem gym**: বাছাই করা একগুচ্ছ problem, যেখানে solution-টা আগের folder-গুলোর 2–3-টা idea মেশায় — একটা heap *plus* intervals, একটা graph *plus* DP, binary search *plus* একটা greedy check।

এতদিনে তুমি "একটা segment tree problem" solve করতে পারো, যখন কেউ বলে দেয় এটা segment tree-র problem। বাকি skill-টা — যেটা interview আর contest আসলে test করে — হলো ছদ্মবেশী একটা problem *কোন* tool চায় তা চেনা, আর সেই চেনাটা মুখে narrate করা।

এই folder-এর thinking tweak: **"উত্তরটা কী?" জিজ্ঞেস করা বন্ধ করো, আর জিজ্ঞেস করতে শুরু করো "এই গল্পটা আমার কোন tool-এ map হয়, আর কেন?"** এখানকার প্রতিটা file সেই mapping-টাই drill করে।

## An important disclaimer about company "styles" (company "style" নিয়ে জরুরি disclaimer)

[google-style.md](google-style.md), [amazon-style.md](amazon-style.md) আর [microsoft-style.md](microsoft-style.md) file-গুলো বর্ণনা করে **publicly discussed interview PATTERN**, যেমনটা community resource-গুলোতে report করা হয় — যেমন [Tech Interview Handbook](https://www.techinterviewhandbook.org/) আর [NeetCode](https://neetcode.io/roadmap)।

- এই label-গুলো বর্ণনা করে *problem-এর style আর emphasis*, যা candidate আর interview-prep community-রা সচরাচর report করে — কোনো company আসলে কী প্রশ্ন করে, তার verified list **নয়**।
- এই repo-র কোনো problem সম্পর্কেই দাবি করা হয় না যে Google, Amazon, Microsoft বা অন্য কোনো company সেটা জিজ্ঞেস করেছে।
- Company-রা প্রশ্ন প্রতিনিয়ত rotate করে আর শেয়ার করা নিষেধ করে; "আসল list" বিক্রি করছে যে, সে fiction বিক্রি করছে।
- Style label-এর সৎ মূল্যটা: প্রতিটা company-র *publicly discussed emphasis* (বেশি graphs না বেশি strings, বেশি ambiguity না বেশি edge-case-এর কড়াকড়ি) practice সাজানোর একটা কাজের axis। আমরা শুধু সে কাজেই এগুলো ব্যবহার করি।

## Why it exists (কোন ব্যথাটা সারায়)

Topic-by-topic পড়া শেষ করা শিক্ষার্থীদের তিনটে ব্যথা ধরে:

- **The labeling crutch।** "Heaps" নামের chapter-এর ভেতরে practice করা মানে প্রতিটা problem-ই heap-এর problem। Interview chapter-এর title-টা সরিয়ে দেয়। এই folder সেটা আগেই সরায়।
- **Single-tool tunnel vision।** অনেক আসল problem-এর দরকার একটা combination ("binary search the answer, check feasibility greedily"), যেটা কোনো একক chapter শেখায় না। [hard-patterns.md](hard-patterns.md) এই combo-গুলোর explicitly নাম দিয়েছে।
- **Silent solving।** কাগজে নিখুঁত হয়েও চুপচাপ solve করে interview-তে fail করা যায়। নিচের methodology narration-এ বাধ্য করে।

## How to use this section (এই section কীভাবে ব্যবহার করবে)

এখানে এসো folder 01–12 শেষ করার **পরে** (বা ন্যূনতম: arrays, hashing, recursion, trees, heaps, graphs, segment/Fenwick trees, DP)। তারপর:

1. এই README-র methodology আর rubric পড়ো।
2. [hard-patterns.md](hard-patterns.md) একবার, পুরোটা পড়ো — ওটাই combo dictionary।
3. তোমার কাছের লক্ষ্যের সাথে মেলা একটা style file বাছো, বা তিনটেই ঘুরিয়ে ঘুরিয়ে নাও।
4. [problems/README.md](problems/README.md)-এর master table-টা mock condition-এ (নিচে) কাজ করো।
5. প্রতিটা problem-এর পরে note file লেখো আর rubric-টা সৎভাবে ভরো।

## Practice methodology — the 45-minute mock format

এখানকার প্রতিটা problem একটা timed mock হিসেবে চালাও — একা, মুখে বলতে বলতে (হ্যাঁ, সত্যিই মুখে — হাস্যকর লাগে, আর কাজ করে):

| Phase | Minutes | What you do |
| --- | --- | --- |
| 1. Clarify | 0–5 | Problem-টা নিজের ভাষায় আবার বলো। Clarifying প্রশ্ন করো (আর উত্তরও দাও): input size? duplicates? negative number? empty input? tie হলে কী return করব? |
| 2. Brute force | 5–12 | সবচেয়ে বোকা সঠিক solution আর তার complexity বলো। O(n³) হলেও মুখে বলো। এতে correctness-এর বোঝাপড়া প্রমাণ হয় আর ভাবার সময় কেনা হয়। |
| 3. Optimize | 12–22 | Pattern-টা শিকার করো: কী আবার আবার computed হচ্ছে? ভেতরের প্রশ্নটার উত্তর কোন structure দ্রুত দিত? Tool-গুলোর নাম বলো (এখানেই [hard-patterns.md](hard-patterns.md)-এর চেনাটা কাজে দেয়)। Coding শুরুর আগেই approach-এ একমত হও। |
| 4. Code | 22–37 | পরিষ্কার Python লেখো, প্রতিটা block-এর উদ্দেশ্য narrate করতে করতে। চালাক one-liner-এর বদলে helper function। |
| 5. Test aloud | 37–45 | একটা normal case আর দুটো edge case তোমার code-এর ভেতর দিয়ে line by line, হাতে হাঁটাও। কোনো "interviewer"-এর আগে নিজের bug নিজে খোঁজো। শেষে time আর space complexity বলো। |

নিয়ম: IDE autocomplete নয়, phase 5 কাগজে শেষ হওয়ার আগে code চালানো নয়, 45 মিনিট শেষ হওয়ার আগে solution-এ উঁকি নয়। Fail করলে সেটাও data — note file-এ log করো আর একটা revisit schedule করো।

## Self-grading rubric

প্রতিটা mock-এ প্রতি row-তে 0–2 score দাও (0 = missing, 1 = partial, 2 = solid)। একটা problem-কে done বলার আগে 12+/16 target করো।

| Dimension | What "2" looks like |
| --- | --- |
| Communication | পুরোটা সময় চিন্তার process শোনা যায়; code-এর আগে approach-এ একমত; লম্বা নীরবতা নেই |
| Clarification | Size, range, duplicates, empties, ties নিয়ে জিজ্ঞেস করেছ — solve করার আগে |
| Brute force first | না বলতেই একটা সঠিক slow solution, complexity-সহ, বলেছ |
| Pattern recognition | নিচের tool-গুলোর নাম বলেছ আর *কেন* মানায় ("sorted + range question → binary search") |
| Edge cases | Empty input, single element, all-equal, extremes — না বলতেই test করেছ |
| Correctness | Final code hand-trace pass করে; off-by-one-গুলো phase 5-এ ধরা পড়েছে |
| Complexity tradeoffs | Time এবং space দুটোই বলেছ; অন্তত একটা বিকল্প tradeoff-এর কথা তুলেছ |
| Code quality | পড়া-যায় এমন নাম, ছোট ছোট function, কোনো dead code নেই |

দুটো সততার নিয়ম rubric-টাকে কাজের রাখে:

- **Grade the recording, not the memory।** পারলে তোমার mock-এর audio record করো (একটা phone-ই যথেষ্ট) আর playback থেকে score দাও — স্মৃতি সবাইকে তোয়াজ করে।
- **জমে-যাওয়া mock-ও score পায়।** Solve করতে fail করা problem-এও communication আর clarification-এর point কামানো যায়; আসল interview ঠিক এভাবেই scored হয়।

## Scheduling: how often, how many (কত ঘন ঘন, কয়টা)

- **Cadence।** সপ্তাহে দুই থেকে তিনটা mock প্রতিদিনের grinding-কে হারায় — mock-গুলোর মাঝখানের rubric review আর note-লেখাটাই শেখার আসল জায়গা।
- **Mixing।** একই pattern-এর দুটো problem কখনো পরপর চালিও না। এই folder-এর পুরো পয়েন্ট হলো পরের problem-এর pattern-টা অজানা থাকা।
- **Plateau response।** পরপর তিনটা mock-এ 10/16-এর নিচে score মানে থামো, এক সপ্তাহের জন্য সবচেয়ে দুর্বল folder-এর tracker-এ ফিরে যাও, তারপর ফিরে এসো। আরও mock দিয়ে tool-এর ফাঁক ঠেলে যাওয়া মানে ফাঁকটারই rehearsal।
- **Endgame।** Master table-এর গড় 13+/16 হয়ে গেলে solo mock-গুলোকে live দিয়ে বদলাও — একজন বন্ধু problem-টা মুখে পড়ে শোনালে অভিজ্ঞতাটা যতটা বদলায়, আর কোনো solo practice ততটা বদলাবে না।

## What lives in this folder (এই folder-এ কী কী আছে)

| File | What it covers |
| --- | --- |
| [google-style.md](google-style.md) | Publicly discussed emphasis: graphs, DP, ambiguous prompts, scaling follow-ups |
| [amazon-style.md](amazon-style.md) | Publicly discussed emphasis: BFS/grids, heaps, intervals, string parsing, customer-scenario framing |
| [microsoft-style.md](microsoft-style.md) | Publicly discussed emphasis: linked lists, trees, strings, edge-case discipline |
| [hard-patterns.md](hard-patterns.md) | Combo dictionary-টা: recognition signal-সহ আটটা cross-topic pattern |
| [problems/README.md](problems/README.md) | 28-problem-এর master table, প্রতিটা row বলে দেয় কোন 2–3-টা repo section মিশেছে |
| [source-map.md](source-map.md) | এখানকার সবকিছু কোথা থেকে এসেছে, copying status-সহ |

## Recommended order through this folder (এই folder-এর ভেতর দিয়ে যাওয়ার ক্রম)

1. [README.md](README.md) — এই file-টা (methodology + rubric)।
2. [hard-patterns.md](hard-patterns.md) — কোনো problem-এর আগে পুরোটা পড়ো; ওটাই recognition dictionary।
3. তোমার পছন্দের একটা style file ([google-style.md](google-style.md) / [amazon-style.md](amazon-style.md) / [microsoft-style.md](microsoft-style.md))।
4. [problems/README.md](problems/README.md) — master table শুরু করো, style বদল করতে করতে।
5. Rotate করতে করতে বাকি style file-গুলোতে ফিরে এসো।

## Connection to everything before (আগের সবকিছুর সাথে যোগ)

Master table-এর প্রতিটা row বলে দেয় সে কোন আগের folder-গুলো টানে — পয়েন্টটাই এটা। এখানকার কোনো problem যদি একটা দুর্বল tool ফাঁস করে দেয় (ধরো, "merge k lists"-এর heap step-এ জমে গেলে), ওই folder-এ ফিরে যাও, তার tracker আবার করো, তারপর ফেরো। এই folder যতটা gym, ততটাই diagnostic।

আগের কোন folder-গুলো এখানে সবচেয়ে বেশি ভার বহন করে, তার একটা দ্রুত map:

| Earlier folder | How often it appears in the master table |
| --- | --- |
| 02 arrays and strings | সারাক্ষণ — প্রায় প্রতিটা problem-এর ভিত |
| 05 hashing | যেকোনো combo-র সবচেয়ে common "second tool" |
| 06 recursion | প্রতিটা tree, graph DFS আর memoized DP-র নিচে |
| 08 heaps | top-K আর intervals-এর মেরুদণ্ড |
| 09 graphs | modeling problem-গুলো (islands, ladders, schedules) |
| 11 segment/Fenwick | order-statistics-এর hard-গুলো |
| 12 dynamic programming | hard problem-গুলোর সবচেয়ে বড় একক ভাগ |

## Connection to competitive programming

এখানকার combo pattern-গুলো (binary search on answer, monotonic structures, DP on DAGs, meet-in-the-middle) ঠিক [Codeforces](https://codeforces.com/problemset/)-এর Div. 2 C–E toolkit আর [CSES problem set](https://cses.fi/problemset/)-এর কঠিন অর্ধেক। Interview prep আর contest prep ঠিক এই স্তরেই মিলে যায়: দুটোই পুরস্কার দেয় দ্রুত, *নাম-ধরে-বলা* pattern recognition-কে।

## Source map

এই folder-এর সব source, link আর copying status আছে [source-map.md](source-map.md)-এ।