13 — Interview Master Problems¶

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, amazon-style.md আর microsoft-style.md file-গুলো বর্ণনা করে publicly discussed interview PATTERN, যেমনটা community resource-গুলোতে report করা হয় — যেমন Tech Interview Handbook আর NeetCode।

এই 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 এই 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)। তারপর:

এই README-র methodology আর rubric পড়ো।
hard-patterns.md একবার, পুরোটা পড়ো — ওটাই combo dictionary।
তোমার কাছের লক্ষ্যের সাথে মেলা একটা style file বাছো, বা তিনটেই ঘুরিয়ে ঘুরিয়ে নাও।
problems/README.md-এর master table-টা mock condition-এ (নিচে) কাজ করো।
প্রতিটা 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`-এর চেনাটা কাজে দেয়)। 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`	Publicly discussed emphasis: graphs, DP, ambiguous prompts, scaling follow-ups
`amazon-style.md`	Publicly discussed emphasis: BFS/grids, heaps, intervals, string parsing, customer-scenario framing
`microsoft-style.md`	Publicly discussed emphasis: linked lists, trees, strings, edge-case discipline
`hard-patterns.md`	Combo dictionary-টা: recognition signal-সহ আটটা cross-topic pattern
`problems/README.md`	28-problem-এর master table, প্রতিটা row বলে দেয় কোন 2–3-টা repo section মিশেছে
`source-map.md`	এখানকার সবকিছু কোথা থেকে এসেছে, copying status-সহ

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

README.md — এই file-টা (methodology + rubric)।
hard-patterns.md — কোনো problem-এর আগে পুরোটা পড়ো; ওটাই recognition dictionary।
তোমার পছন্দের একটা style file (google-style.md / amazon-style.md / microsoft-style.md)।
problems/README.md — master table শুরু করো, style বদল করতে করতে।
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-এর Div. 2 C–E toolkit আর CSES problem set-এর কঠিন অর্ধেক। Interview prep আর contest prep ঠিক এই স্তরেই মিলে যায়: দুটোই পুরস্কার দেয় দ্রুত, নাম-ধরে-বলা pattern recognition-কে।

Source map¶

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