কোডিং ইন্টারভিউর সমস্যা — প্যাটার্ন ধরে সমাধান

১ · ইন্টারভিউর কাঠামো — সাত ধাপ, কথা বলা আর আটকে গেলে

পর্ব ৬৮–৭০-এ আপনি হাতে চালানো, MCQ আর লিখিত-মৌখিক প্রশ্নের অনুশীলন করেছেন। কোডিং ইন্টারভিউ এর থেকে আলাদা। এখানে একটি অচেনা সমস্যা দেওয়া হয়, আর ৩০–৪৫ মিনিটে আপনাকে সেটি বুঝে, সমাধান বের করে, কোড লিখে, পরীক্ষা করে দেখাতে হয় — পুরো সময় কথা বলে। দেশি সফটওয়্যার প্রতিষ্ঠান, স্টার্টআপ, ব্যাংক বা টেলিকমের আইটি বিভাগ, বিদেশি প্রতিষ্ঠানের রিমোট পদ — প্রতিষ্ঠানভেদে ধাপের নাম আর ক্রম আলাদা হয়, কিন্তু অ্যালগরিদমের অংশটা মোটামুটি একই রকম।

সাত ধাপের পদ্ধতি

চাপের মধ্যে মাথা ফাঁকা হয়ে যাওয়া খুব স্বাভাবিক। এর সবচেয়ে ভালো ওষুধ একটি বাঁধা রুটিন — যাতে “এখন কী করব” ভাবতে না হয়, শুধু পরের ধাপে যেতে হয়। ডাক্তার যেমন প্রতিটি রোগীর ক্ষেত্রে একই ক্রমে এগোন — লক্ষণ জিজ্ঞেস করা, পরীক্ষা, রোগ নির্ণয়, ওষুধ, তারপর ফলো-আপ — আপনিও তেমন।

পদ্ধতিটি একটি সমস্যায় প্রয়োগ করে দেখা যাক। সমস্যা · লাভ-ক্ষতির খাতা (মাঝারি): “একটি মুদি দোকানের n দিনের হিসাব দেওয়া আছে — প্রতিদিনের লাভ (ঋণাত্মক হলে ক্ষতি)। কতগুলো টানা দিনের অংশে মোট লাভ ঠিক k টাকা?” নিচে “পরে” চাপুন:

- ঋণাত্মক মান আছে? (হ্যাঁ, ক্ষতির দিন)
- n কত বড়? (২ লাখ পর্যন্ত)
- অংশগুলো টানা দিন হতে হবে? (হ্যাঁ)
- গুনতে হবে, নাকি অংশগুলো দেখাতে? (গুনতে)
- উত্তর কত বড় হতে পারে?
  n(n+1)/2 ≈ 2·10^10 -> long long

[1, 1, 1],          k = 2  -> 2
[3,4,7,2,-3,1,4,2], k = 7  -> 4
   [3,4] [7] [7,2,-3,1] [1,4,2]
[0, 0, 0],          k = 0  -> 6  শূন্যের ফাঁদ
[5],                k = 5  -> 1
[],                 k = 0  -> 0  খালি

for i in 0..n-1:
    s = 0
    for j in i..n-1:
        s += a[j]          // চলমান যোগফল
        if s == k: ans++
সময় O(n²), বাড়তি মেমরি O(1)
n = 2·10^5 -> প্রায় 2·10^10 ধাপ: ধীর

P[t] = প্রথম t দিনের যোগফল
sum(a[i..j]) = P[j+1] - P[i] = k
  <=>  P[i] = P[j+1] - k
-> "আগের কতগুলো prefix-এর মান
    P[j+1] - k?"  -> hash map-এ গুনে রাখি
sliding window চলবে না: ঋণাত্মক আছে

seen = {0: 1}        // খালি prefix একবার দেখা
pre = 0, ans = 0
for x in a:
    pre += x
    ans += seen[pre - k]   // আগে খুঁজি
    seen[pre] += 1         // পরে রাখি

x=1: pre=1, খুঁজি -1: 0   seen {0:1, 1:1}
x=1: pre=2, খুঁজি  0: 1   seen {.., 2:1}  ans=1
x=1: pre=3, খুঁজি  1: 1   seen {.., 3:1}  ans=2
{0: 1} না দিলে প্রথম অংশ [1,1] হারাত -> ans=1

সময় গড়ে O(n), মেমরি O(n)
(hash map-এর কাজ গড়ে O(1); map নিলে O(n log n))
- সব মান ধনাত্মক হলে? -> sliding window, O(1) মেমরি
- k দিয়ে বিভাজ্য অংশ? -> pre % k গুনুন
- সবচেয়ে লম্বা অংশ? -> প্রথম index রাখুন

ইনপুটের আকার থেকে লক্ষ্য-জটিলতা

ইন্টারভিউয়ার বা প্রশ্নপত্র n-এর সীমা বললে সেটি একটি বড় ইঙ্গিত। একটি সাধারণ হিসাব: সাধারণ কম্পিউটার এক সেকেন্ডে মোটামুটি 10⁸-এর কাছাকাছি সরল কাজ করতে পারে (ভাষা আর কাজের ধরনে কয়েক গুণ কম-বেশি হয়)। তাই:

কথা বলতে বলতে কোড লেখা

ইন্টারভিউয়ার আপনার মাথার ভেতর দেখতে পান না। তাই think aloud — মানে ভাবনাটা জোরে বলা — এখানে সবচেয়ে বড় দক্ষতা। সব কিছু বলার দরকার নেই, সিদ্ধান্তগুলো বলুন। কয়েকটি কাজের বাক্য:

• শুরুতে (clarifying question): “ধরে নিচ্ছি array খালি হতে পারে, আর উত্তর না থাকলে −1 দেব — ঠিক আছে?”
• পদ্ধতি বাছাইয়ে: “দুটি লুপে O(n²); n দুই লাখ হলে সেটা প্রায় দুই হাজার কোটি ধাপ। তাই prefix sum আর hash map ভাবছি — মেমরি O(n) বাড়বে।”
• লেখার মাঝে: “এখানে আগে খুঁজছি, পরে রাখছি, যাতে k = 0-তে একই prefix নিজের সাথে না মেলে।”
• শেষে: “সময় গড়ে O(n), মেমরি O(n). উত্তর long long-এ রাখছি, কারণ সব শূন্য হলে অংশের সংখ্যা n²/2-এর কাছাকাছি।”

আটকে গেলে কী করবেন

আটকে যাওয়া ব্যর্থতা নয় — ইন্টারভিউয়ার প্রায়ই দেখতে চান না-জানা অবস্থায় আপনি কীভাবে এগোন। নীরব হয়ে যাওয়াই আসল বিপদ। এই ক্রমে চেষ্টা করুন:

1. ছোট উদাহরণ হাতে করুন। ৪–৫টি উপাদানের একটি ইনপুটে নিজে উত্তর বের করুন, আর লক্ষ করুন আপনার মাথা কী করছে। সেটাই প্রায়ই অ্যালগরিদম।
2. সমস্যা সহজ করুন। ঋণাত্মক বাদ দিন, ২D-কে ১D করুন, k = 1 ধরুন। সহজটি সমাধান করে মূলটিতে ফিরুন।
3. প্যাটার্নের তালিকা ঘুরে দেখুন। “সাজালে কি সহজ হয়? hash map দিলে? দুই প্রান্ত থেকে? উত্তরের ওপর binary search?” অংশ ৯-এর চিটশিট মুখস্থ থাকলে এটা কয়েক সেকেন্ডের কাজ।
4. Brute force-এর অপচয় খুঁজুন। কোন হিসাব বারবার হচ্ছে? সেটি মনে রাখা (memo, prefix, map) বা বাদ দেওয়া (pointer, pruning) যায় কি?
5. বলে ফেলুন। “আমি এই জায়গায় আটকেছি, কারণ …” — ভালো ইন্টারভিউয়ার তখন ছোট একটি hint দেন। Hint নিয়ে দ্রুত এগোনোও মূল্যায়নের অংশ, লজ্জার কিছু নয়।

এই পাতার বাকি অংশে ১৪টি প্যাটার্ন আছে। প্রতিটির শুরুতে রিভিশনের পর্ব দেওয়া আছে — সমাধান পড়ার আগে সেই পর্বের মূল ধারণা একবার ঝালিয়ে নিন।

২ · Hashing আর two pointer — খোঁজা দ্রুত করা

প্যাটার্ন ১ · Hashing — “এটা কি আগে দেখেছি?”

রিভিশন: পর্ব ৩২ · Hash table, পর্ব ১৫ · STL আর Python-এর কালেকশন

Pseudocode (0-based) — "seen" template
seen = empty hash map            // key -> whatever you need (index, count)
for j = 0 .. n-1:
    if NEED(a[j]) is in seen:    // look first ...
        use seen[NEED(a[j])]
    seen[a[j]] = j               // ... then store

সমাধান-করা সমস্যা · বাজেটের দুই পণ্য (সহজ): “একটি অনলাইন দোকানে n টি পণ্যের দাম দেওয়া আছে। আপনার bKash-এ ঠিক T টাকা আছে। এমন দুটি ভিন্ন পণ্যের index বের করুন, যাদের দামের যোগফল ঠিক T. না থাকলে −1 −1 দিন।” এটি বিখ্যাত two sum সমস্যার একটি রূপ।

• Brute force: সব জোড়া (i, j) দেখুন — n(n−1)/2 টি জোড়া, সময় O(n²), বাড়তি মেমরি O(1).
• অপচয় কোথায়: ভেতরের লুপ প্রতিবার একটাই প্রশ্ন করে — “T − a[j] কি আগে কোথাও আছে?” এই খোঁজাটা hash map-এ গড়ে O(1).
• সেরা: একবার বাঁ থেকে ডানে যান, প্রতিটি j-এ আগে খুঁজুন, তারপর a[j] রাখুন। সময় গড়ে O(n), মেমরি O(n). এটাই সময়-মেমরির বিনিময়।

pair<int, int> twoSum(const vector<int>& a, int target) {
    unordered_map<int, int> seen;                  // value -> index
    for (int j = 0; j < (int)a.size(); ++j) {
        if (auto it = seen.find(target - a[j]); it != seen.end()) return {it->second, j};
        seen.emplace(a[j], j);                     // look first, then store
    }
    return {-1, -1};
}

এই ফাংশন চারটি ইনপুটে চালিয়ে যাচাই করা হয়েছে: দাম [450, 120, 300, 80], T = 380 → 2 3 (300 + 80); [200, 200], T = 400 → 0 1; [500], T = 1000 → -1 -1; [−3, 4, 3, 90], T = 0 → 0 2.

• Edge case: একই দাম দুবার ([200, 200]) — “আগে খুঁজি, পরে রাখি” ক্রম থাকায় ঠিক কাজ করে; ক্রম উল্টালে [500], 1000-এ একই পণ্য নিজের সাথে জোড়া বাঁধত। emplace আগে থেকে থাকা key বদলায় না, তাই ডুপ্লিকেটে প্রথম index থাকে।
• সতর্কতা: unordered_map-এর O(1) গড়ে; ইচ্ছা করে বানানো ইনপুটে (anti-hash test) এটি অনেক ধীর হতে পারে। কনটেস্টে তখন map (O(log n)) বা custom hash নিন (পর্ব ৩২)।
• ফলো-আপ: দাম সাজানো থাকলে? → two pointer, মেমরি O(1) (প্যাটার্ন ২)। সব জোড়া গুনতে হলে? → map-এ গণনা রাখুন, ans += cnt[T − x].

Hashing-এর আরেক রূপ frequency count: প্রতিটি অক্ষর বা মান কতবার এসেছে, তা গুনে রাখা। দুটি শব্দ anagram কি না দেখতে দুটোর গণনা মেলান — ছোট বর্ণমালায় ২৬ ঘরের frequency array-ই যথেষ্ট, hash map-এর চেয়ে দ্রুত।

প্যাটার্ন ২ · Two pointer — দুই প্রান্ত থেকে চেপে আনা

রিভিশন: পর্ব ১৬ · Two pointer আর sliding window, পর্ব ৫০ · Greedy আর exchange argument

Pseudocode (0-based) — opposite ends
L = 0, R = n - 1
while L < R (or L <= R):
    look at a[L], a[R]
    move L right OR R left, whichever side can never be part of an answer

সমাধান-করা সমস্যা · রিকশার যাত্রী (মাঝারি): “স্টেশনের সামনে n জন যাত্রীর ওজন দেওয়া আছে। একটি রিকশায় সর্বোচ্চ ২ জন বসতে পারেন, আর দুজনের মোট ওজন limit-এর বেশি হতে পারবে না। সবাইকে পৌঁছাতে কমপক্ষে কয়টি রিকশা লাগবে?” (কারও একার ওজন limit-এর বেশি নয়।)

• Brute force: সব রকম জোড়া বানানো পরখ করা — সম্ভাবনা সূচকীয় হারে বাড়ে। একটু ভালো: প্রতিবার সবচেয়ে ভারী জনের জন্য বাকিদের মধ্যে সবচেয়ে ভারী সম্ভাব্য সঙ্গী খোঁজা — O(n²)।
• মূল পর্যবেক্ষণ: সবচেয়ে ভারী জনকে কোনো না কোনো রিকশায় উঠতেই হবে। সবচেয়ে হালকা জনও যদি তাঁর সাথে না মেলেন, তাহলে কেউ মিলবেন না — তিনি একা যাবেন। আর মিললে, তাঁর সাথে সবচেয়ে হালকা জনকে বসানো নিরাপদ।
• সেরা: sort করে দুই প্রান্তে L আর R. প্রতি ধাপে R (ভারী জন) রওনা দেন; L-কে সাথে নেওয়া গেলে L-ও। সময় O(n log n) (sort) + O(n), মেমরি sort-এর ওপর নির্ভর করে, বাড়তি O(1).

int minRickshaws(vector<int> w, int limit) {       // at most 2 riders, total <= limit
    sort(w.begin(), w.end());
    int L = 0, R = (int)w.size() - 1, trips = 0;
    while (L <= R) {
        if (w[L] + w[R] <= limit) ++L;             // lightest rides with the heaviest
        --R; ++trips;                              // heaviest always leaves now
    }
    return trips;
}

চালিয়ে যাচাই: ওজন [70, 50, 80, 50], limit 120 → 3 (80 একা, 70 + 50 একসাথে, বাকি 50 একা); [60, 40, 90, 30, 80], limit 120 → 3 (90+30, 80+40, 60); খালি তালিকা → 0. ছোট ইনপুটে সব জোড়া-বিন্যাস পরখ করা একটি brute force-ও একই উত্তর দিয়েছে।

কেন greedy ঠিক (exchange argument, পর্ব ৫০): ধরুন সবচেয়ে ভারী জন H, সবচেয়ে হালকা জন h. ক্ষেত্র ১: H + h > limit হলে বাকি সবাই h-এর চেয়ে ভারী, তাই H কোনো সমাধানেই কারও সাথে বসতে পারেন না — তাঁকে একা পাঠানোই একমাত্র পথ। ক্ষেত্র ২: H + h ≤ limit. যেকোনো সেরা সমাধান নিন। সেখানে H বসেছেন X-এর সাথে, আর h বসেছেন Y-এর সাথে (কেউ একা থাকলে যুক্তি আরও সহজ)। h আর X-এর জায়গা বদলান: নতুন জোড়া (H, h) আর (X, Y). প্রথমটি বৈধ ধরে নেওয়া আছে; দ্বিতীয়টিতে Y ≤ H, তাই X + Y ≤ X + H ≤ limit — এটিও বৈধ। রিকশার সংখ্যা বদলায়নি। অর্থাৎ greedy-র প্রথম সিদ্ধান্ত মেনেও একটি সেরা সমাধান আছে; বাকি যাত্রীদের ওপর একই যুক্তি (induction) চালালেই প্রমাণ শেষ।

• Edge case: এক জন, সবাই খুব ভারী (সবাই একা), সবাই হালকা (সব জোড়া), L == R অবস্থা (শেষ জন একা) — তাই শর্ত L <= R, L < R নয়।
• ফলো-আপ: রিকশায় ৩ জন বসতে পারলে? তখন এই সরল greedy আর প্রমাণসহ খাটে না — সমস্যাটি bin packing-এর কাছাকাছি চলে যায় (পর্ব ৬৫)।

৩ · Sliding window আর prefix sum — টানা অংশের সমস্যা

প্যাটার্ন ৩ · Sliding window — ডানে বাড়ান, বাঁয়ে ছাঁটুন

রিভিশন: পর্ব ১৬, পর্ব ৬০ · Amortized analysis

Pseudocode (0-based) — variable window
L = 0
for R = 0 .. n-1:
    add a[R] to the window
    while window is invalid:      // shrink from the left
        remove a[L]; L = L + 1
    update answer with window a[L..R]

সমাধান-করা সমস্যা · পুনরাবৃত্তিহীন দীর্ঘতম অংশ (মাঝারি): “একটি string দেওয়া আছে। এমন সবচেয়ে লম্বা টানা অংশ বের করুন, যেখানে কোনো অক্ষর দুবার নেই।” Brute force: প্রতিটি শুরু i থেকে ডানে বাড়াতে থাকুন, প্রথম পুনরাবৃত্তিতে থামুন — O(n²) (প্রতিটি অংশ নতুন করে যাচাই করলে O(n³))। উন্নতি: window-এর ডান প্রান্ত R বাড়ান; নতুন অক্ষরটি window-এর ভেতরে আগে থাকলে L-কে সেই আগের অবস্থানের ঠিক পরে লাফিয়ে দিন। প্রতিটি অক্ষরের শেষ দেখা index একটি array-তে রাখলে লাফটা O(1).

নিচে s = "abcbad"-এ অ্যালগরিদমটি চালানো হলো। “last[c] আগে” মানে নতুন অক্ষরটি এর আগে শেষবার কোথায় দেখা গিয়েছিল:

#include <iostream>
#include <string>
#include <vector>
#include <initializer_list>
using namespace std;

// length and start of the longest substring with no repeated character
pair<int, int> longestUnique(const string& s) {
    vector<int> last(256, -1);              // last index where each byte was seen
    int L = 0, best = 0, start = 0;
    for (int R = 0; R < (int)s.size(); ++R) {
        unsigned char c = s[R];
        if (last[c] >= L) L = last[c] + 1;  // repeat inside the window: jump L
        last[c] = R;
        if (R - L + 1 > best) { best = R - L + 1; start = L; }
    }
    return {best, start};
}

int brute(const string& s) {                // O(n^2): grow from every start
    int best = 0;
    for (size_t i = 0; i < s.size(); ++i) {
        vector<bool> seen(256, false);
        for (size_t j = i; j < s.size() && !seen[(unsigned char)s[j]]; ++j) {
            seen[(unsigned char)s[j]] = true;
            best = max(best, int(j - i + 1));
        }
    }
    return best;
}

int main() {
    for (string s : {"abcbad", "abcabcbb", "bbbbb", "", "abba", "tmmzuxt"}) {
        auto [len, st] = longestUnique(s);
        cout << '"' << s << "\" -> " << len << " \"" << s.substr(st, len)
             << "\"  brute=" << brute(s) << '\n';
    }
}

"abcbad" -> 4 "cbad"  brute=4
"abcabcbb" -> 3 "abc"  brute=3
"bbbbb" -> 1 "b"  brute=1
"" -> 0 ""  brute=0
"abba" -> 2 "ab"  brute=2
"tmmzuxt" -> 5 "mzuxt"  brute=5

def longest_unique(s):
    """Return (length, start) of the longest substring with no repeated character."""
    last = {}                        # char -> last index where it was seen
    L = best = start = 0
    for R, c in enumerate(s):
        if last.get(c, -1) >= L:     # repeat inside the window: jump L
            L = last[c] + 1
        last[c] = R
        if R - L + 1 > best:
            best, start = R - L + 1, L
    return best, start

def brute(s):                        # O(n^2): grow from every start
    best = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
            best = max(best, j - i + 1)
    return best

for s in ["abcbad", "abcabcbb", "bbbbb", "", "abba", "tmmzuxt"]:
    n, st = longest_unique(s)
    print(f'"{s}" -> {n} "{s[st:st + n]}"  brute={brute(s)}')

"abcbad" -> 4 "cbad"  brute=4
"abcabcbb" -> 3 "abc"  brute=3
"bbbbb" -> 1 "b"  brute=1
"" -> 0 ""  brute=0
"abba" -> 2 "ab"  brute=2
"tmmzuxt" -> 5 "mzuxt"  brute=5

জটিলতা: R প্রতিটি ধাপে ১ বাড়ে, আর L কখনো কমে না — মোট n টি ধাপ, প্রতিটি O(1): সময় Θ(n). মেমরি O(Σ) (C++-এ ২৫৬ ঘর)। “ভেতরে while থাকলে O(n²)” — এই সাধারণ ভুলটি এড়াতে মনে রাখুন: L-এর মোট সরণ n-এর বেশি হতে পারে না, এটাই amortized হিসাব।

প্যাটার্ন ৪ · Prefix sum + hash map — “আগের কোন যোগফল দরকার?”

রিভিশন: পর্ব ১৭ · Prefix sum আর difference array, পর্ব ৩২

সমাধান-করা সমস্যা হলো অংশ ১-এর লাভ-ক্ষতির খাতা — stepper-এ সাত ধাপ দেখেছেন। এখন পুরো কোড, ছয়টি ইনপুট আর ৫০০টি এলোমেলো ইনপুটে brute force-এর সাথে মিলিয়ে:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

long long countFast(const vector<int>& a, long long k) {   // O(n) on average
    unordered_map<long long, long long> seen{{0, 1}};       // prefix sum -> count
    long long pre = 0, ans = 0;
    for (int x : a) {
        pre += x;
        if (auto it = seen.find(pre - k); it != seen.end()) ans += it->second;
        ++seen[pre];                                         // count AFTER looking up
    }
    return ans;
}

long long countBrute(const vector<int>& a, long long k) {  // O(n^2)
    long long ans = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        long long s = 0;
        for (size_t j = i; j < a.size(); ++j) ans += (s += a[j]) == k;
    }
    return ans;
}

int main() {
    vector<pair<vector<int>, int>> tests = {
        {{1, 1, 1}, 2}, {{3, 4, 7, 2, -3, 1, 4, 2}, 7}, {{0, 0, 0}, 0},
        {{5}, 5}, {{-1, -1, 1}, 0}, {{}, 0}};
    for (auto& [a, k] : tests)
        cout << "k=" << k << ": fast=" << countFast(a, k) << " brute=" << countBrute(a, k) << '\n';
    unsigned seed = 12345; int bad = 0;                      // deterministic stress test
    for (int t = 0; t < 500; ++t) {
        vector<int> a(t % 9);
        for (int& x : a) { seed = seed * 1103515245u + 12345u; x = int(seed >> 16) % 7 - 3; }
        bad += countFast(a, t % 5 - 2) != countBrute(a, t % 5 - 2);
    }
    cout << "stress: 500 random arrays, mismatches = " << bad << '\n';
}

k=2: fast=2 brute=2
k=7: fast=4 brute=4
k=0: fast=6 brute=6
k=5: fast=1 brute=1
k=0: fast=1 brute=1
k=0: fast=0 brute=0
stress: 500 random arrays, mismatches = 0

• জটিলতা: সময় গড়ে O(n), মেমরি O(n) (সব prefix আলাদা হলে map-এ n + 1টি key).
• সবচেয়ে সাধারণ বাগ: seen{{0, 1}} ভুলে যাওয়া — তখন index 0 থেকে শুরু হওয়া অংশগুলো হারায়। দ্বিতীয় বাগ: আগে ++seen[pre], পরে খোঁজা — k = 0-তে প্রতিটি prefix নিজের সাথে মিলে খালি অংশ গুনে ফেলে।
• Overflow: যোগফল আর উত্তর দুটোই long long — n দুই লাখ, প্রতিটি মান 10⁹ পর্যন্ত হলে যোগফল 2 · 10¹⁴.

৪ · উত্তরের ওপর binary search আর monotonic stack

প্যাটার্ন ৫ · Binary search on answer — “এই মানে কি সম্ভব?”

রিভিশন: পর্ব ১৮ · Binary search, পর্ব ১৯ · উত্তরের ওপর binary search

Pseudocode — first value where feasible() becomes true
lo = smallest possible answer, hi = an answer that surely works
while lo < hi:
    mid = lo + (hi - lo) / 2
    if feasible(mid): hi = mid       // mid works: answer is mid or smaller
    else:             lo = mid + 1   // mid fails: answer is bigger
return lo

সমাধান-করা সমস্যা · বন্দরে কার্টন পাঠানো (মাঝারি): “একটি গার্মেন্টস কারখানা থেকে n টি কার্টন এই ক্রমেই চট্টগ্রাম বন্দরে পাঠাতে হবে; প্রতিটির ওজন দেওয়া আছে। একটি ট্রাক দিনে একবার যায় আর সর্বোচ্চ cap কেজি নেয়। D দিনের মধ্যে সব পাঠাতে ট্রাকের ক্ষমতা কমপক্ষে কত হতে হবে?”

• যাচাই সহজ: একটি নির্দিষ্ট cap দিলে greedy-ভাবে ভরে দেখা যায় কত দিন লাগে — যতক্ষণ জায়গা আছে আজকের ট্রাকে তুলুন, না হলে পরের দিন। O(n). (Greedy এখানে নিরাপদ: আজকে যত বেশি পাঠানো যায়, পরের দিনগুলোর কাজ তত কম।)
• Brute force: cap = সবচেয়ে ভারী কার্টন থেকে এক এক করে বাড়িয়ে প্রথম সম্ভব মান — O(n · (S − max)), যেখানে S মোট ওজন। ওজন লাখের ঘরে হলে অচল।
• সেরা: cap যত বাড়ে, দিন তত কমে বা সমান থাকে — একমুখী। তাই [max, S] পরিসরে binary search: O(n log S).

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

// can all cartons (in order) be sent within `days` if a truck carries `cap` per day?
bool feasible(const vector<int>& w, long long cap, int days) {
    int used = 1; long long load = 0;
    for (int x : w) {
        if (load + x > cap) { ++used; load = 0; }   // start a new day
        load += x;
    }
    return used <= days;
}

long long minCapacity(const vector<int>& w, int days) {
    long long lo = *max_element(w.begin(), w.end());           // must fit the heaviest
    long long hi = accumulate(w.begin(), w.end(), 0LL);        // one day carries all
    while (lo < hi) {                       // first cap where feasible() becomes true
        long long mid = lo + (hi - lo) / 2;
        if (feasible(w, mid, days)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

int main() {
    vector<pair<vector<int>, int>> tests = {{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5},
        {{3, 2, 2, 4, 1, 4}, 3}, {{1, 2, 3, 1, 1}, 4}, {{7, 2, 5, 10, 8}, 1}, {{9}, 3}};
    for (auto& [w, d] : tests) {
        long long brute = *max_element(w.begin(), w.end());   // linear scan upward
        while (!feasible(w, brute, d)) ++brute;
        cout << "days=" << d << ": binary=" << minCapacity(w, d) << " linear=" << brute << '\n';
    }
}

days=5: binary=15 linear=15
days=3: binary=6 linear=6
days=4: binary=3 linear=3
days=1: binary=32 linear=32
days=3: binary=9 linear=9

• সবচেয়ে সাধারণ বাগ: while (lo <= hi) আর hi = mid একসাথে — lo == hi হলে চিরকাল ঘোরে। টেমপ্লেট একটি বেছে নিয়ে সবসময় সেটাই লিখুন। আরেকটি: lo 1 থেকে শুরু করা — তখন feasible()-এ সবচেয়ে ভারী কার্টন কোনো দিনেই আঁটে না, অথচ কোড দিন গুনতে থাকে।
• প্রমাণের এক লাইন: feasible একমুখী, তাই মানগুলো দেখতে F F F … T T T; লুপের invariant “উত্তর [lo, hi]-এর মধ্যে” প্রতিটি ধাপে টেকে, আর পরিসর প্রতিবার অন্তত অর্ধেক হয়।

প্যাটার্ন ৬ · Monotonic stack — “ডানে প্রথম বড় কে?”

রিভিশন: পর্ব ১৩ · Stack

মূল সমস্যা · Next greater element: “প্রতিদিনের একটি শেয়ারের দাম দেওয়া আছে। প্রতিটি দিনের জন্য বলুন, তার পরে প্রথম যেদিন দাম বেশি, সেদিনের দাম কত; না থাকলে −1.” ধারণা: stack-এ সেই দিনগুলো রাখুন যাদের উত্তর এখনো জানা নেই। তাদের দাম ওপর থেকে নিচে বাড়তে থাকে (নিচে বড়)। নতুন দিনের দাম stack-এর মাথার চেয়ে বড় হলে মাথার উত্তর পাওয়া গেল — pop করুন, আবার দেখুন।

vector<int> nextGreater(const vector<int>& a) {
    vector<int> ans(a.size(), -1), st;             // st: indices, values decreasing
    for (int i = 0; i < (int)a.size(); ++i) {
        while (!st.empty() && a[st.back()] < a[i]) { ans[st.back()] = a[i]; st.pop_back(); }
        st.push_back(i);
    }
    return ans;
}

এই ফাংশন [4, 2, 5, 3, 1, 6, 2]-এ চালিয়ে 5 5 6 6 6 -1 -1 পাওয়া গেছে — stepper-এর সাথে মেলে। জটিলতা: প্রতিটি index ঠিক একবার push আর সর্বোচ্চ একবার pop হয়, তাই ভেতরের while সব মিলিয়ে সর্বোচ্চ n বার চলে — সময় Θ(n), মেমরি O(n). stack-এ মান না রেখে index রাখুন: তাহলে “কত দিন পরে” (দূরত্ব) প্রশ্নেও একই কোড চলে।

সমাধান-করা সমস্যা · সবচেয়ে বড় বিলবোর্ড (কঠিন): “একটি রাস্তার পাশে পাশাপাশি n টি ভবন, প্রতিটির প্রস্থ ১, উচ্চতা দেওয়া আছে। ভবনগুলোর গায়ে লাগিয়ে একটি আয়তাকার বিলবোর্ড বসাতে হবে, যা কোনো ভবনের ছাদ ছাড়িয়ে যাবে না। সবচেয়ে বড় ক্ষেত্রফল কত?” এটি বিখ্যাত largest rectangle in histogram.

• Brute force: প্রতিটি [i..j] অংশে সবচেয়ে নিচু ভবন × প্রস্থ। চলমান minimum রাখলে O(n²)।
• মূল পর্যবেক্ষণ: সেরা আয়তক্ষেত্রের উচ্চতা কোনো একটি ভবন h[t]-এর সমান। সেই উচ্চতায় আয়তক্ষেত্রটি বাঁয়ে প্রথম নিচু ভবন পর্যন্ত আর ডানে প্রথম নিচু ভবন পর্যন্ত ছড়াতে পারে — অর্থাৎ next smaller element দুই দিকে।
• সেরা: উচ্চতা বাড়ন্ত ক্রমে index-এর stack. নতুন ভবন মাথার চেয়ে নিচু (বা সমান) হলে মাথার ডান সীমা পাওয়া গেল (i), আর stack-এ তার নিচেরটি বাঁ সীমা। শেষে উচ্চতা 0-এর একটি sentinel ভবন সবাইকে বের করে আনে। O(n).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long largestRectangle(vector<int> h) {
    h.push_back(0);                                 // sentinel flushes the stack at the end
    vector<int> st;  long long best = 0;            // indices, heights increasing
    for (int i = 0; i < (int)h.size(); ++i) {
        while (!st.empty() && h[st.back()] >= h[i]) {
            long long height = h[st.back()]; st.pop_back();
            int left = st.empty() ? -1 : st.back(); // first lower bar on the left
            best = max(best, height * (i - left - 1));
        }
        st.push_back(i);
    }
    return best;
}

long long bruteRect(const vector<int>& h) {         // O(n^2): every [i..j], running min
    long long best = 0;
    for (int i = 0; i < (int)h.size(); ++i) {
        int mn = h[i];
        for (int j = i; j < (int)h.size(); ++j) {
            mn = min(mn, h[j]);
            best = max(best, 1LL * mn * (j - i + 1));
        }
    }
    return best;
}

int main() {
    vector<vector<int>> tests = {{2, 1, 5, 6, 2, 3}, {2, 4}, {6, 2, 5, 4, 5, 1, 6}, {3, 3, 3}, {5}, {}};
    for (auto& h : tests)
        cout << "rect=" << largestRectangle(h) << " brute=" << bruteRect(h) << '\n';
}

rect=10 brute=10
rect=4 brute=4
rect=12 brute=12
rect=9 brute=9
rect=5 brute=5
rect=0 brute=0

৫ · Heap আর interval — সেরা k টি আর সময়ের পরিসর

প্যাটার্ন ৭ · Heap / top-k — “সবচেয়ে বড়/ছোট k টি”

রিভিশন: পর্ব ২৩ · Heap আর priority queue, পর্ব ২২ · Quickselect

সমাধান-করা সমস্যা ১ · সবচেয়ে কাছের k জন রাইডার (মাঝারি): “একটি খাবার ডেলিভারি অ্যাপে রেস্তোরাঁ (0, 0) বিন্দুতে। n জন রাইডারের অবস্থান (x, y) দেওয়া আছে। সবচেয়ে কাছের k জনকে বের করুন।” কৌশলটি উল্টো শোনায়: সবচেয়ে কাছের k জনের জন্য max-heap — heap-এ এ পর্যন্ত সেরা k জন, আর মাথায় তাদের মধ্যে সবচেয়ে দূরের জন। নতুন কেউ এলে ঢোকান; আকার k ছাড়ালে মাথা (সবচেয়ে দূরের) ফেলে দিন। দূরত্বের বর্গ তুলনা করুন — sqrt-এর দরকার নেই, আর floating-point-এর ভুলও থাকে না।

সমাধান-করা সমস্যা ২ · k টি শাখার সাজানো তালিকা মেলানো (মাঝারি): “একটি ব্যাংকের k টি শাখার প্রতিটি থেকে সময় অনুযায়ী সাজানো লেনদেনের তালিকা এসেছে। সব মিলিয়ে একটি সাজানো তালিকা বানান।” প্রতিটি তালিকার প্রথম উপাদান একটি min-heap-এ রাখুন; সবচেয়ে ছোটটি বের করে আউটপুটে দিন, আর যে তালিকা থেকে এসেছিল তার পরেরটি heap-এ ঢোকান — এটাই k-way merge.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

// k points closest to (0,0): keep a MAX-heap of size k, O(n log k)
vector<pair<int, int>> kClosest(const vector<pair<int, int>>& pts, int k) {
    priority_queue<tuple<long long, int, int>> heap;            // (dist^2, x, y), largest on top
    for (auto [x, y] : pts) {
        heap.emplace(1LL * x * x + 1LL * y * y, x, y);
        if ((int)heap.size() > k) heap.pop();                   // drop the farthest
    }
    vector<pair<int, int>> out;
    for (; !heap.empty(); heap.pop()) out.push_back({get<1>(heap.top()), get<2>(heap.top())});
    return out;                                                 // farthest of the k first
}

// merge k sorted lists with a MIN-heap of (value, list, index), O(N log k)
vector<int> mergeK(const vector<vector<int>>& lists) {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> heap;
    for (int i = 0; i < (int)lists.size(); ++i)
        if (!lists[i].empty()) heap.emplace(lists[i][0], i, 0);
    vector<int> out;
    while (!heap.empty()) {
        auto [v, i, j] = heap.top(); heap.pop();
        out.push_back(v);
        if (j + 1 < (int)lists[i].size()) heap.emplace(lists[i][j + 1], i, j + 1);
    }
    return out;
}

int main() {
    for (auto [x, y] : kClosest({{3, 3}, {5, -1}, {-2, 4}, {1, 1}, {0, -2}, {4, 0}}, 3))
        cout << "(" << x << "," << y << ") ";
    cout << '\n';
    for (int v : mergeK({{1, 4, 9}, {2, 3, 10, 12}, {}, {5}})) cout << v << ' ';
    cout << '\n';
}

(4,0) (0,-2) (1,1)
1 2 3 4 5 9 10 12 

• জটিলতা: k closest — সময় O(n log k), মেমরি O(k). Merge — মোট N টি উপাদান, heap-এ সর্বোচ্চ k টি, সময় O(N log k), heap-এর মেমরি O(k). জোড়ায় জোড়ায় মেলালে (প্রথম দুটি, তারপর ফলের সাথে তৃতীয়টি …) সবচেয়ে খারাপ ক্ষেত্রে O(N · k).
• বিকল্প: শুধু k টি চাই, ক্রম লাগবে না — quickselect / nth_element, গড়ে O(n).
• Edge case: k = 0, k ≥ n, খালি তালিকা, সমান দূরত্ব (কোনটি নেবেন? ইন্টারভিউয়ারকে জিজ্ঞেস করুন)।

প্যাটার্ন ৮ · Interval — sort করে একবার হেঁটে যান

রিভিশন: পর্ব ২৫ · Comparator, পর্ব ৫০ · Interval scheduling

সমাধান-করা সমস্যা · ডাক্তারের চেম্বারের সময়সূচি (মাঝারি): “একজন ডাক্তার দিনে কয়েকটি সময়-খণ্ডে রোগী দেখেন, কিন্তু তালিকায় খণ্ডগুলো এলোমেলো আর কিছু একটার ওপর আরেকটা পড়েছে। (ক) overlap থাকা খণ্ডগুলো জোড়া লাগিয়ে পরিষ্কার তালিকা বানান। (খ) একটি পরিষ্কার, সাজানো তালিকায় নতুন একটি খণ্ড ঢোকান।” এটি interval merging.

• Brute force: প্রতিটি জোড়া overlap কি না দেখে বারবার জোড়া লাগানো, যতক্ষণ বদল হয় — O(n²) বা খারাপ।
• সেরা (ক): শুরু অনুযায়ী sort. এখন overlap হলে সেটা শুধু ফলাফলের শেষ খণ্ডের সাথেই হতে পারে — কারণ আগের খণ্ডগুলো আরও আগে শেষ হয়েছে। O(n log n).
• সেরা (খ): তালিকা আগে থেকেই সাজানো, তাই তিন ভাগ: নতুনটির পুরো বাঁয়ে, overlap করা (জোড়া লাগান), পুরো ডানে। O(n), sort লাগে না।

vector<pair<int, int>> mergeIntervals(vector<pair<int, int>> v) {
    sort(v.begin(), v.end());
    vector<pair<int, int>> out;
    for (auto [s, e] : v) {
        if (!out.empty() && s <= out.back().second) out.back().second = max(out.back().second, e);
        else out.push_back({s, e});
    }
    return out;
}

vector<pair<int, int>> insertInterval(const vector<pair<int, int>>& v, pair<int, int> x) {
    vector<pair<int, int>> out; size_t i = 0;
    while (i < v.size() && v[i].second < x.first) out.push_back(v[i++]);      // fully left
    while (i < v.size() && v[i].first <= x.second) {                          // overlapping
        x.first = min(x.first, v[i].first); x.second = max(x.second, v[i].second); ++i;
    }
    out.push_back(x);
    while (i < v.size()) out.push_back(v[i++]);                               // fully right
    return out;
}

চালিয়ে যাচাই: [9, 11], [1, 3], [2, 6], [8, 10], [15, 18], [6, 7] জোড়া লাগালে [1,7] [8,11] [15,18]; [1, 4], [4, 5] → [1,5] (ছুঁয়ে থাকা খণ্ডও জোড়া লাগে, কারণ শর্ত s <= end). [1, 2], [3, 5], [6, 7], [8, 10], [12, 16]-এ [4, 8] ঢোকালে [1,2] [3,10] [12,16]; খালি তালিকায় [5, 7] → [5,7]; [1, 5]-এ [6, 8] → [1,5] [6,8].

• সাধারণ বাগ: জোড়া লাগানোর সময় out.back().second = e লেখা, max ছাড়া — [1, 10]-এর পরে [2, 3] এলে শেষ সময় ছোট হয়ে যায়।
• সাধারণ বাগ ২: sort না করা, বা শেষ সময় অনুযায়ী sort করা — merge-এর জন্য শুরু অনুযায়ী সাজাতে হয়।

৬ · Linked list আর tree — pointer আর recursion

প্যাটার্ন ৯ · Linked list-এর কৌশল — উল্টানো, মাঝখান আর চক্র

রিভিশন: পর্ব ১২ · Linked list

সমাধান-করা সমস্যা · ট্রেনের বগি (মাঝারি): “একটি ট্রেনের বগিগুলো linked list-এর মতো একটির পর একটি জোড়া। (ক) মাঝের বগিটি খুঁজুন। (খ) পুরো ট্রেনটি উল্টো দিকে সাজান। (গ) কোনো ভুলে শেষ বগি যদি আগের কোনো বগির সাথে জুড়ে যায় (চক্র), তা ধরুন আর বলুন চক্রটি কোন বগি থেকে শুরু।” সবগুলোই O(1) বাড়তি মেমরিতে।

• Brute force: (ক) একবার গুনে n, তারপর n/2 ধাপ — দুবার হাঁটা, তবু O(n). (গ) দেখা node-গুলো একটি unordered_set-এ রাখা — সময় O(n), কিন্তু মেমরি O(n).
• মাঝখান: slow এক ধাপ, fast দুই ধাপ; fast শেষে পৌঁছালে slow ঠিক মাঝে। জোড় দৈর্ঘ্যে এই কোড দ্বিতীয় মাঝেরটি দেয় — কোনটি চাই, জিজ্ঞেস করুন।
• চক্র (Floyd-এর পদ্ধতি): চক্র থাকলে fast একসময় slow-কে ধরে ফেলে — প্রতি ধাপে তাদের ব্যবধান চক্রের ভেতরে ১ করে কমে। দেখা হওয়ার পর একটিকে head-এ ফিরিয়ে দুজনকেই এক ধাপ করে চালালে তারা চক্রের শুরুতে মেলে।

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Node { int val; Node* next; };

Node* reverseList(Node* head) {               // three pointers: prev, cur, next
    Node* prev = nullptr;
    while (head) { Node* nxt = head->next; head->next = prev; prev = head; head = nxt; }
    return prev;
}
Node* middle(Node* head) {                // slow 1 step, fast 2 steps
    Node *slow = head, *fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    return slow;                          // even length: the second middle
}
Node* cycleEntry(Node* head) {            // Floyd: meet, then restart one pointer
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) {
            for (slow = head; slow != fast; slow = slow->next, fast = fast->next) {}
            return slow;
        }
    }
    return nullptr;
}

int main() {
    vector<Node> pool(6);                 // nodes live in a vector: no new/delete needed
    for (int i = 0; i < 6; ++i) pool[i] = {i + 1, i + 1 < 6 ? &pool[i + 1] : nullptr};
    Node* head = &pool[0];
    cout << "middle of 1..6: " << middle(head)->val << '\n';
    cout << "reversed:";
    for (Node* p = head = reverseList(head); p; p = p->next) cout << ' ' << p->val;
    Node* e = cycleEntry(head);
    cout << "\ncycle? " << (e ? "yes" : "no") << '\n';
    pool[0].next = &pool[3];              // tail (value 1) now points back to value 4
    e = cycleEntry(head);
    cout << "cycle? " << (e ? "yes, entry value " + to_string(e->val) : "no") << '\n';
}

middle of 1..6: 4
reversed: 6 5 4 3 2 1
cycle? no
cycle? yes, entry value 4

চক্রের শুরু কেন মেলে (প্রমাণ): head থেকে চক্রের শুরু পর্যন্ত দূরত্ব μ, চক্রের দৈর্ঘ্য λ। দেখা হওয়ার সময় slow হেঁটেছে s ধাপ, fast 2s; fast বাড়তি s ধাপে চক্রটি পুরো কয়েকবার ঘুরেছে, তাই s হলো λ-এর গুণিতক। slow চক্রের ভেতরে s − μ ধাপ এগিয়ে আছে। এখন একটি pointer head থেকে আর অন্যটি দেখা হওয়ার জায়গা থেকে μ ধাপ হাঁটলে প্রথমটি চক্রের শুরুতে পৌঁছায়, আর দ্বিতীয়টি চক্রের ভেতরে মোট s ধাপ — λ-এর গুণিতক — এগিয়ে, অর্থাৎ সেও চক্রের শুরুতে। সময় O(μ + λ) = O(n), মেমরি O(1).

• Edge case: খালি list (head == nullptr), এক node, এক node-এর নিজের সাথে চক্র। while (fast && fast->next) — দুটোই যাচাই না করলে null-এর next পড়ে crash.
• উল্টানোর বাগ: head->next = prev লেখার আগে nxt সেভ না করা — তখন বাকি list হারিয়ে যায়।

প্যাটার্ন ১০ · Tree-তে DFS recursion — “বাচ্চাদের কাছ থেকে কী জানতে চাই?”

রিভিশন: পর্ব ২৬ · Tree, পর্ব ২৭ · BST, পর্ব ৪৮ · LCA আর diameter

সমাধান-করা সমস্যা · পারিবারিক বংশতালিকা (মাঝারি): “একটি binary tree দেওয়া আছে। (ক) যেকোনো দুই node-এর মধ্যে সবচেয়ে লম্বা পথ কত edge (diameter)? (খ) দুটি node-এর lowest common ancestor কে — অর্থাৎ সবচেয়ে নিচের যে node দুজনেরই পূর্বপুরুষ? (গ) tree-টি কি বৈধ BST?”

• Diameter: brute force — প্রতিটি node থেকে উচ্চতা নতুন করে হিসাব: O(n²) (একদিকে হেলে থাকা tree-তে)। উন্নতি: একই DFS-এ উচ্চতা ফেরত দিন আর পথে বাঁ উচ্চতা + ডান উচ্চতা দিয়ে সেরা হালনাগাদ করুন — O(n). সবচেয়ে লম্বা পথ root দিয়ে যেতেই হবে, এমন নয় — এটাই সাধারণ ভুল।
• LCA: node-টি p বা q হলে নিজেকে ফেরত দিন; দুই দিক থেকেই কিছু ফিরলে আপনিই মিলনস্থল। O(n).
• Valid BST: শুধু “বাঁ সন্তান < আমি < ডান সন্তান” যাচাই করা ভুল — নাতি-নাতনিও শর্ত ভাঙতে পারে। প্রতিটি node-কে একটি অনুমোদিত পরিসর (lo, hi) দিন। (বিকল্প: inorder traversal কঠোরভাবে বাড়তে হবে।)

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct T { int val; T *l = nullptr, *r = nullptr; };

int height(T* n, int& diam) {             // returns height in nodes; updates diameter
    if (!n) return 0;
    int a = height(n->l, diam), b = height(n->r, diam);
    diam = max(diam, a + b);              // longest path THROUGH n, counted in edges
    return 1 + max(a, b);
}
bool validBST(T* n, long long lo, long long hi) {   // every key strictly inside (lo, hi)
    if (!n) return true;
    if (n->val <= lo || n->val >= hi) return false;
    return validBST(n->l, lo, n->val) && validBST(n->r, n->val, hi);
}
T* lca(T* n, int p, int q) {              // both p and q are assumed to be in the tree
    if (!n || n->val == p || n->val == q) return n;
    T *a = lca(n->l, p, q), *b = lca(n->r, p, q);
    return a && b ? n : (a ? a : b);      // found on both sides -> n is the meeting point
}

int main() {
    // tree: 8 -> (3, 10); 3 -> (1, 6); 10 -> right 14; 6 -> right 7
    int vals[] = {8, 3, 10, 1, 6, 14, 7};
    vector<T> t(7);
    for (int i = 0; i < 7; ++i) t[i].val = vals[i];
    t[0].l = &t[1]; t[0].r = &t[2]; t[1].l = &t[3]; t[1].r = &t[4];
    t[2].r = &t[5]; t[4].r = &t[6];
    int diam = 0; height(&t[0], diam);
    cout << "diameter (edges) = " << diam << '\n';
    cout << "valid BST? " << validBST(&t[0], LLONG_MIN, LLONG_MAX) << '\n';
    cout << "lca(7,1) = " << lca(&t[0], 7, 1)->val << ", lca(7,14) = " << lca(&t[0], 7, 14)->val << '\n';
    t[6].val = 9;                         // 9 > 6 is fine locally, but it is left of root 8
    cout << "after 7 -> 9, valid BST? " << validBST(&t[0], LLONG_MIN, LLONG_MAX) << '\n';
}

diameter (edges) = 5
valid BST? 1
lca(7,1) = 3, lca(7,14) = 8
after 7 -> 9, valid BST? 0

• জটিলতা: তিনটিই প্রতিটি node একবার দেখে — সময় O(n); মেমরি O(h) call stack, যেখানে h উচ্চতা (ভারসাম্যপূর্ণ tree-তে O(log n), একদিকে হেলে থাকলে O(n)).
• Recursion-এর ঝুঁকি: দশ লাখ node-এর একটি সরলরেখার মতো tree-তে recursion stack overflow ঘটাতে পারে। ইন্টারভিউতে ঝুঁকিটা বলুন, আর দরকার হলে নিজের stack দিয়ে iterative লিখুন (পর্ব ০৭)।

৭ · Graph আর union-find — সংযোগ, ক্রম আর গ্রুপ

প্যাটার্ন ১১ · Graph — grid-এ BFS আর topological sort

রিভিশন: পর্ব ৩৯ · গ্রাফ, পর্ব ৪০ · BFS, পর্ব ৪১ · DFS, পর্ব ৪২ · Topological sort

সমাধান-করা সমস্যা ১ · নদীর চর গোনা (মাঝারি): “একটি নদীর মানচিত্র grid-এ দেওয়া — '#' মানে চর (মাটি), '.' মানে পানি। ওপর-নিচ-ডান-বাঁ জুড়ে থাকা মাটির ঘরগুলো একটি চর। কয়টি চর আছে?” প্রতিটি নতুন মাটির ঘর পেলে গণনা বাড়ান আর সেখান থেকে flood fill (BFS) চালিয়ে পুরো চরটি “দেখা হয়েছে” চিহ্ন দিন। প্রতিটি ঘর একবারই queue-তে ঢোকে।

সমাধান-করা সমস্যা ২ · কোর্সের ক্রম (মাঝারি): “একটি কোর্সে n টি বিষয়, আর কিছু শর্ত ‘a পড়ার আগে b পড়তে হবে’। সব বিষয় পড়ার একটি বৈধ ক্রম দিন, অথবা বলুন অসম্ভব।” Kahn-এর অ্যালগরিদম: যাদের কোনো বাকি শর্ত নেই (in-degree 0), তাদের queue-তে রাখুন; একটি বের করে পড়ুন, তার ওপর নির্ভরশীলদের in-degree কমান। শেষে সবাইকে পড়া না গেলে চক্র আছে — অসম্ভব।

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int countIslands(vector<string> g) {           // '#' = land (char), '.' = water
    int R = g.size(), C = R ? g[0].size() : 0, islands = 0;
    queue<pair<int, int>> q;
    auto visit = [&](int r, int c) {           // mark when PUSHED, not when popped
        if (r >= 0 && r < R && c >= 0 && c < C && g[r][c] == '#') { g[r][c] = '.'; q.push({r, c}); }
    };
    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c) {
            if (g[r][c] != '#') continue;
            ++islands; visit(r, c);            // a new island: flood it with BFS
            while (!q.empty()) {
                auto [x, y] = q.front(); q.pop();
                visit(x + 1, y); visit(x - 1, y); visit(x, y + 1); visit(x, y - 1);
            }
        }
    return islands;
}

vector<int> courseOrder(int n, const vector<pair<int, int>>& pre) {   // {a, b}: b before a
    vector<vector<int>> adj(n); vector<int> indeg(n), order; queue<int> q;
    for (auto [a, b] : pre) { adj[b].push_back(a); ++indeg[a]; }
    for (int v = 0; v < n; ++v) if (indeg[v] == 0) q.push(v);
    while (!q.empty()) {
        int v = q.front(); q.pop(); order.push_back(v);
        for (int w : adj[v]) if (--indeg[w] == 0) q.push(w);
    }
    if ((int)order.size() < n) order.clear();  // someone never reached in-degree 0: cycle
    return order;
}

int main() {
    cout << "islands = " << countIslands({"##..#", "#...#", "..#..", "....#", "##.##"}) << '\n';
    vector<vector<pair<int, int>>> tests{{{1, 0}, {2, 0}, {3, 1}, {3, 2}, {4, 3}, {5, 4}}, {{1, 0}, {2, 1}, {0, 2}}};
    for (auto& pre : tests) {
        auto order = courseOrder(6, pre);
        if (order.empty()) cout << "impossible: cycle";
        for (int v : order) cout << v << ' ';
        cout << '\n';
    }
}

islands = 5
0 1 2 3 4 5
impossible: cycle

• জটিলতা: চর গোনা — R × C grid-এ প্রতিটি ঘর একবার ঢোকে, ৪টি প্রতিবেশী দেখা হয়: সময় O(R · C), মেমরি O(R · C) (queue সবচেয়ে খারাপ ক্ষেত্রে)। Kahn — সময় O(V + E), মেমরি O(V + E).
• DFS না BFS? শুধু গোনার জন্য দুটোই চলে। কিন্তু বিশাল grid-এ recursive DFS-এর গভীরতা R · C পর্যন্ত হতে পারে — stack overflow-এর ঝুঁকি। সবচেয়ে কম ধাপ চাইলে BFS ছাড়া উপায় নেই।
• ইনপুট বদলানো: কোডটি grid-এর একটি কপি নিয়ে সেটাতেই চিহ্ন দেয় (vector<string> g মান হিসেবে)। কলকারীর ডেটা বদলানো চলবে কি না, জিজ্ঞেস করুন।

প্যাটার্ন ১২ · Union-find — “এরা কি একই দলে?”

রিভিশন: পর্ব ৩৩ · Disjoint set union, পর্ব ৪৫ · Kruskal

সমাধান-করা সমস্যা · গ্রামের রাস্তা (মাঝারি): “একটি উপজেলার ৫টি গ্রাম। একটি একটি করে রাস্তা তৈরি হচ্ছে। প্রতিটি নতুন রাস্তার পরে বলুন কয়টি আলাদা অঞ্চল আছে, আর রাস্তাটি অপ্রয়োজনীয় (redundant) কি না — অর্থাৎ দুই প্রান্তের গ্রাম আগে থেকেই কোনো পথে জোড়া ছিল কি না।” Brute force: প্রতিটি রাস্তার পরে পুরো graph-এ BFS — মোট O(m · (n + m)). DSU-তে প্রতিটি কাজ প্রায় O(1).

#include <iostream>
#include <vector>
#include <numeric>
#include <utility>
using namespace std;

struct DSU {
    vector<int> parent, size;
    int components;
    DSU(int n) : parent(n), size(n, 1), components(n) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }  // path compression
    bool unite(int a, int b) {                       // false if already connected
        a = find(a); b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);           // union by size
        parent[b] = a; size[a] += size[b]; --components;
        return true;
    }
};

int main() {
    // villages 1..5, roads added one by one; the road that closes a cycle is redundant
    vector<pair<int, int>> roads{{1, 2}, {2, 3}, {4, 5}, {1, 3}, {3, 4}, {2, 5}};
    DSU d(6);                                        // index 0 unused
    for (auto [a, b] : roads) {
        bool merged = d.unite(a, b);
        cout << "road " << a << "-" << b << (merged ? " joins two groups" : " is REDUNDANT")
             << ", groups now = " << d.components - 1 << '\n';
    }
}

road 1-2 joins two groups, groups now = 4
road 2-3 joins two groups, groups now = 3
road 4-5 joins two groups, groups now = 2
road 1-3 is REDUNDANT, groups now = 2
road 3-4 joins two groups, groups now = 1
road 2-5 is REDUNDANT, groups now = 1

• জটিলতা: path compression আর union by size একসাথে থাকলে m টি কাজে মোট O(m · α(n)), যেখানে α হলো inverse Ackermann — বাস্তবের যেকোনো n-এ ৪-এর বেশি নয়। মেমরি O(n). দুটির একটিও না থাকলে tree লম্বা সরলরেখা হয়ে প্রতিটি find O(n) পর্যন্ত যেতে পারে।
• Recursion: path compression-এর recursive find প্রথমবার লম্বা শিকলে গভীর হতে পারে; union by size থাকলে উচ্চতা O(log n), তাই নিরাপদ।

৮ · Backtracking আর DP — সব সম্ভাবনা, তারপর মনে রাখা

প্যাটার্ন ১৩ · Backtracking — বাছুন, এগোন, ফিরিয়ে নিন

রিভিশন: পর্ব ০৭ · রিকার্শন, পর্ব ৫৬ · Backtracking

Pseudocode — the backtracking skeleton
SOLVE(state):
    if state is a complete answer: record it; return
    for each choice c allowed in state:
        if c cannot lead to an answer: skip      // prune
        apply c            // choose
        SOLVE(state)       // explore
        undo c             // un-choose

সমাধান-করা সমস্যা · ঠিক বাজেটে কেনাকাটা (মাঝারি): “একটি দোকানে কয়েক রকম চকলেট, দাম [2, 3, 6, 7] টাকা; একই চকলেট যতবার খুশি কেনা যায়। ঠিক 7 টাকা খরচ করার সব আলাদা উপায় দিন (ক্রম বদলালে নতুন উপায় নয়)।” সাথে একটি ছোট উষ্ণতা-অনুশীলন: [1, 2, 3]-এর সব উপসেট।

• ডুপ্লিকেট এড়ানো: [2, 2, 3] আর [3, 2, 2] একই উপায়। তাই প্রতিটি ধাপে শুধু বর্তমান index থেকে ডানের চকলেট বাছুন (start) — তাহলে প্রতিটি উপায় একবারই, অ-কমা ক্রমে তৈরি হয়।
• পুনর্ব্যবহার: একই চকলেট আবার নেওয়া যায়, তাই পরের ডাকে i, i + 1 নয়।
• Pruning: দাম সাজানো থাকলে c[i] > left হওয়ামাত্র লুপ থামান — ডানের সবাই আরও দামি।

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void print(const vector<int>& v) {
    cout << '[';
    for (size_t i = 0; i < v.size(); ++i) cout << (i ? "," : "") << v[i];
    cout << "] ";
}

void subsets(const vector<int>& a, size_t i, vector<int>& cur) {    // 2^n leaves
    if (i == a.size()) { print(cur); return; }
    cur.push_back(a[i]); subsets(a, i + 1, cur); cur.pop_back();   // take a[i]
    subsets(a, i + 1, cur);                                         // skip a[i]
}

// choose -> explore -> un-choose; a candidate may be reused
void combo(const vector<int>& c, int start, int left, vector<int>& cur, int& calls) {
    ++calls;
    if (left == 0) { print(cur); return; }
    for (int i = start; i < (int)c.size() && c[i] <= left; ++i) {   // sorted: prune
        cur.push_back(c[i]);                   // choose
        combo(c, i, left - c[i], cur, calls);  // explore (i, not i+1: reuse allowed)
        cur.pop_back();                        // un-choose
    }
}

int main() {
    vector<int> cur;
    subsets({1, 2, 3}, 0, cur);
    cout << '\n';
    for (auto [cand, target] : vector<pair<vector<int>, int>>{{{2, 3, 6, 7}, 7}, {{5, 3, 2}, 8}, {{4}, 3}}) {
        sort(cand.begin(), cand.end());
        int calls = 0;
        combo(cand, 0, target, cur, calls);
        cout << "calls=" << calls << '\n';
    }
}

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []
[2,2,3] [7] calls=10
[2,2,2,2] [2,3,3] [3,5] calls=13
calls=1

• জটিলতা: উপসেট — 2ⁿ টি, প্রতিটি ছাপাতে O(n): Θ(n · 2ⁿ). বিন্যাস — Θ(n · n!)। Combination sum — ডাকের সংখ্যা সর্বোচ্চ শাখা-সংখ্যা^{T / ক্ষুদ্রতম দাম}-এর মতো বাড়ে; আউটপুট-সংবেদী, কোনো সরল বহুপদী সীমা নেই। মেমরি O(T / ক্ষুদ্রতম দাম) recursion গভীরতা।
• সাধারণ বাগ: “un-choose” ভুলে যাওয়া — তখন আগের শাখার উপাদান পরের শাখায় থেকে যায়। আর ফল রেকর্ড করার সময় cur-এর রেফারেন্স রেখে দেওয়া — পরে বদলে যায়; কপি রাখুন।

প্যাটার্ন ১৪ · Dynamic programming — একই ছোট প্রশ্ন বারবার

রিভিশন: পর্ব ৫২ · DP-র ভিত্তি, পর্ব ৫৩ · Knapsack, coin change, LIS, পর্ব ৫৪ · LCS, edit distance

Recipe — five questions before writing any DP
1. State:      dp[i] (or dp[i][j]) means exactly WHAT?
2. Transition: how is dp[i] built from smaller states?
3. Base case:  the smallest states, written by hand
4. Order:      fill so every state you read is already computed
5. Answer:     which cell (or max over cells) is the final answer?

সমাধান-করা সমস্যা — চারটি ক্লাসিক এক জায়গায়:

• ১D · পাশাপাশি নয় (মাঝারি): “একজন বিক্রয়কর্মী একটি গলির বাড়িগুলোতে যান, প্রতিটিতে সম্ভাব্য বিক্রি জানা। পাশাপাশি দুই বাড়িতে একই দিনে যাওয়া যাবে না। সর্বোচ্চ বিক্রি কত?” dp[i] = প্রথম i টি বাড়ি থেকে সর্বোচ্চ; dp[i] = max(dp[i−1], dp[i−2] + a[i]). শুধু শেষ দুটি মান লাগে, তাই মেমরি O(1).
• ১D · সবচেয়ে কম কয়েন (মাঝারি): “কয়েন {1, 7, 10}, যতবার খুশি। ঠিক 14 টাকা বানাতে কমপক্ষে কয়টি কয়েন?” Greedy (সবচেয়ে বড়টি আগে) দেয় 10 + 1 + 1 + 1 + 1 = ৫টি; আসল উত্তর 7 + 7 = ২টি। dp[v] = min(dp[v − c] + 1). এটাই coin change.
• ২D · LCS (মাঝারি): “একটি ফাইলের দুই সংস্করণের মধ্যে সবচেয়ে লম্বা অভিন্ন subsequence কত?” — diff টুলের ভিত্তি। dp[i][j] = a-র প্রথম i আর b-র প্রথম j অক্ষরের LCS.
• ২D · grid-এর পথ (সহজ): “একটি এলাকার রাস্তার grid-এ বাঁ-ওপর থেকে ডান-নিচে শুধু ডানে বা নিচে গিয়ে কত উপায়ে যাওয়া যায়, যদি কিছু মোড় পানিতে ডুবে বন্ধ থাকে?” dp[r][c] = ওপর থেকে + বাঁ থেকে; বন্ধ ঘরে 0. একটি সারি রাখলেই চলে (rolling array).

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int robber(const vector<int>& a) {               // dp[i] = max(dp[i-1], dp[i-2] + a[i])
    int take = 0, skip = 0;                       // best ending with / without a[i-1]
    for (int x : a) { int t = skip + x; skip = max(skip, take); take = t; }
    return max(take, skip);
}
int coinChange(const vector<int>& coins, int amount) {   // fewest coins, -1 if impossible
    const int INF = 1e9;
    vector<int> dp(amount + 1, INF); dp[0] = 0;
    for (int v = 1; v <= amount; ++v)
        for (int c : coins) if (c <= v && dp[v - c] + 1 < dp[v]) dp[v] = dp[v - c] + 1;
    return dp[amount] >= INF ? -1 : dp[amount];
}
int lcs(const string& a, const string& b) {      // dp[i][j] = LCS of a[0..i), b[0..j)
    vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));
    for (size_t i = 1; i <= a.size(); ++i)
        for (size_t j = 1; j <= b.size(); ++j)
            dp[i][j] = a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
    return dp[a.size()][b.size()];
}
long long gridPaths(const vector<string>& g) {   // right/down moves, '#' = blocked
    vector<long long> dp(g[0].size(), 0); dp[0] = 1;
    for (const string& row : g)
        for (size_t c = 0; c < row.size(); ++c)
            dp[c] = row[c] == '#' ? 0 : dp[c] + (c ? dp[c - 1] : 0);   // from above + from left
    return dp.back();
}

int main() {
    cout << "robber [2,7,9,3,1] = " << robber({2, 7, 9, 3, 1}) << '\n';
    cout << "coins {1,7,10} -> 14 = " << coinChange({1, 7, 10}, 14) << ", {4} -> 6 = " << coinChange({4}, 6) << '\n';
    cout << "lcs(AGGTAB, GXTXAYB) = " << lcs("AGGTAB", "GXTXAYB") << '\n';
    cout << "grid paths = " << gridPaths({"...", ".#.", "..."}) << '\n';
}

robber [2,7,9,3,1] = 12
coins {1,7,10} -> 14 = 2, {4} -> 6 = -1
lcs(AGGTAB, GXTXAYB) = 4
grid paths = 2

• জটিলতা: robber — সময় O(n), মেমরি O(1). Coin change — সময় O(A · k) (A = টাকার অঙ্ক, k = কয়েনের ধরন), মেমরি O(A); এটি pseudo-polynomial, কারণ A-র মান বড় হলে ধীর। LCS — সময় O(n · m), মেমরি O(n · m), শুধু দৈর্ঘ্য চাইলে দুটি সারিতে O(min(n, m)). Grid — সময় O(R · C), মেমরি O(C).
• Top-down না bottom-up? Memoization লেখা সহজ আর শুধু দরকারি state ছোঁয়; tabulation-এ recursion-এর গভীরতার ঝুঁকি নেই আর rolling array সহজ। ইন্টারভিউতে আগে recursion + memo বলুন, তারপর টেবিলে রূপান্তর দেখান — দুটোই জানা ভালো সংকেত।

৯ · প্যাটার্ন চেনার চিটশিট আর ভাবনার প্রশ্ন

নিচের টেবিলটি ইন্টারভিউর আগের রাতের রিভিশনের জন্য। বাঁ কলামের শব্দ বা অবস্থা সমস্যার বিবরণে দেখলে মাঝের প্যাটার্নটি প্রথমে ভাবুন। মনে রাখবেন, এটি নিশ্চিত নিয়ম নয়, শুরুর ইঙ্গিত — একটি সমস্যায় প্রায়ই দুটি প্যাটার্ন একসাথে লাগে (যেমন sort + two pointer, BFS + bitmask, binary search + greedy).

ভাবনার প্রশ্ন

কোড লেখার পরে ইন্টারভিউয়ার প্রায়ই জিজ্ঞেস করেন, “এটা কেন এভাবে করলেন?” — আর কিছু প্রশ্ন প্রস্তুতির ধরনটাই ঠিক করে দেয়। প্রতিটি আগে নিজে ভাবুন, তারপর খুলুন।

১০ · AI দিয়ে প্রস্তুতি — সৎ ব্যবহার আর brute force দিয়ে যাচাই

প্রস্তুতির সময় অবশ্য AI হতে পারে চমৎকার mock interview-এর সঙ্গী — শর্ত একটাই: উত্তর নয়, প্রশ্ন আর মূল্যায়ন চাইবেন। আর মনে রাখবেন, DSA-তে AI-এর ভুলগুলো প্রায়ই আত্মবিশ্বাসী শোনায়:

নিজের লেখা বা AI-এর দেওয়া সমাধান যাচাই করতে এই পাতার কোডগুলোর কৌশলটাই ব্যবহার করুন: একটি ধীর কিন্তু নিশ্চিতভাবে সঠিক brute force লিখুন, তারপর ছোট এলোমেলো ইনপুটে দুটির ফল মেলান — প্যাটার্ন ৪-এর ৫০০টি ইনপুটের মতো। brute force সহজে ঠিক লেখা যায়, তাই সে-ই বিচারক। ছোট মান-পরিসর (−3 থেকে 3, বা "abc") ইচ্ছা করে নিন — এতে ডুপ্লিকেট, শূন্য আর ফাঁদের কেস নিজে থেকেই তৈরি হয়। নিজের seed দেওয়া generator রাখুন, যাতে ভুল পেলে একই ইনপুট আবার বানানো যায়। এই পদ্ধতির বিস্তারিত অনুশীলন পর্ব ৬৮-এ আর কনটেস্টের প্রসঙ্গে পর্ব ৭২-এ।

AI দিয়ে অনুশীলনের চেকলিস্ট

• সমাধান দেখার আগে নিজে অন্তত ২০ মিনিট চেষ্টা করেছি, আর খাতায় সাত ধাপ লিখেছি
• AI-এর বলা জটিলতা নিজে গুনে মিলিয়েছি — প্রতিটি pointer মোট কতবার সরে, প্রতিটি উপাদান কতবার push/pop হয়
• greedy থাকলে একটি পাল্টা উদাহরণ খুঁজেছি, না পেলে exchange argument লিখেছি
• খালি, এক উপাদান, ডুপ্লিকেট, ঋণাত্মক, সব শূন্য আর সীমার সবচেয়ে বড় মান দিয়ে চালিয়েছি
• একটি brute force লিখে কয়েকশো এলোমেলো ছোট ইনপুটে ফল মিলিয়েছি
• একদিন পরে AI ছাড়া একই সমস্যা আবার শূন্য থেকে সমাধান করতে পেরেছি, আর পাঁচ মিনিটে জোরে ব্যাখ্যা করতে পারি