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

১ · টেকনিক্যাল ইন্টারভিউ আসলে কীভাবে হয়

পর্ব ৫৫-এ দেখেছেন লিখিত ও মৌখিক পরীক্ষায় কীভাবে উত্তর গোছাতে হয়। সফটওয়্যার কোম্পানির technical interview আরেকটু আলাদা। এখানে শুধু “উত্তর জানেন কি না” দেখা হয় না। দেখা হয়, অচেনা একটি সমস্যা পেলে আপনি কীভাবে ভাবেন, কীভাবে কথা বলেন, আর কতটা নির্ভরযোগ্য কোড লেখেন।

দেশি স্টার্টআপ, সফটওয়্যার ফার্ম, ব্যাংকের আইটি বিভাগ বা বহুজাতিক কোম্পানি — প্রতিষ্ঠানভেদে ধাপের নাম ও সংখ্যা আলাদা। তবে সারা বিশ্বেই কাঠামোটা মোটামুটি এক রকম। সাধারণত যে ধাপগুলো দেখা যায়:

ইন্টারভিউয়ার শুধু শেষ কোড দেখেন না

অনেকে ভাবেন, “সঠিক কোড লিখলেই পাস।” বাস্তবে একটি ইন্টারভিউর মূল্যায়ন-পত্রে সাধারণত কয়েকটি আলাদা ঘর থাকে। ঠিক কোড লিখেও কেউ বাদ পড়তে পারেন, আবার কোড শেষ না করেও কেউ ভালো নম্বর পেতে পারেন — যদি বাকি ঘরগুলোতে তিনি ভালো করেন।

এই পাতার ১৬টি সমস্যা

২ · সমস্যা থেকে সমাধান — সাত ধাপের পদ্ধতি

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

আন্তর্জাতিকভাবে এ ধরনের পদ্ধতি নানা নামে পরিচিত, যেমন UMPIRE (Understand, Match, Plan, Implement, Review, Evaluate). আমরা সহজ বাংলায় সাতটি ধাপ নিই:

এবার পদ্ধতিটি একটি বিখ্যাত সমস্যায় প্রয়োগ করি — Two sum: “একটি int অ্যারে আর একটি target দেওয়া আছে। এমন দুটি ভিন্ন index বের করুন, যাদের মানের যোগফল target.” নিচের ডায়াগ্রামে “পরে” চাপুন:

- ঠিক একটি জোড়া থাকবে, নাকি নাও থাকতে পারে?
- একই index দুবার নেওয়া যাবে? (না)
- অ্যারে কি সাজানো? (না)
- n কত বড়? মান কত বড়? ঋণাত্মক আছে?
- index ফেরত দেব, নাকি মান?

[2, 7, 11, 15], target 9  ->  (0, 1)
[3, 3],         target 6  ->  (0, 1)   একই মান, ভিন্ন index
[-3, 4, 3, 90], target 0  ->  (0, 2)   ঋণাত্মক
[1, 2, 3],      target 7  ->  জোড়া নেই
[5],            target 10 ->  জোড়া নেই  5+5 নেওয়া যাবে না

ক) Brute force: প্রতিটি জোড়া (i, j) যাচাই
খ) সাজিয়ে দুই দিক থেকে দুই পয়েন্টার
   (আসল index মনে রাখতে হবে)
গ) Hash table: প্রতিটি a[j]-এর জন্য খুঁজি
   "target - a[j] কি আগে দেখেছি?"

              সময়          বাড়তি মেমরি
ক) Brute      O(n²)         O(1)
খ) Sort + 2p  O(n log n)    O(n)  (index জোড়া রাখতে)
গ) Hash       O(n) গড়ে     O(n)

for j = 0 .. n-1:
    need = target - a[j]
    if need আছে hash-এ:  return (hash[need], j)
    hash[a[j]] = j          // আগে খুঁজি, পরে রাখি
return "জোড়া নেই"

j=0: need=3, hash-এ নেই    -> hash{3:0}
j=1: need=3, hash-এ আছে(0) -> (0, 1)
যদি আগে রাখতাম, পরে খুঁজতাম: [5], target 10
-> নিজের সাথেই জোড়া (0, 0) — ভুল!

- অ্যারে আগে থেকেই সাজানো হলে?  -> দুই পয়েন্টার, O(1) মেমরি
- সব জোড়া চাই?  -> ডুপ্লিকেট সামলানো
- তিনটি সংখ্যা (3-sum)?  -> সাজিয়ে + দুই পয়েন্টার, O(n²)
- target - a[j] কি overflow করতে পারে?

C-তে কোনো তৈরি hash table নেই — এটাই C-ইন্টারভিউর বিশেষত্ব। ছোট ইনপুটের জন্য নিচের মতো একটি open addressing টেবিল নিজেই লিখে ফেলা যায়। অনেক ইন্টারভিউয়ার বলেন, “ধরে নিন একটি hash map আছে।” তখন শুধু মূল যুক্তিটি লিখলেই চলে।

#include <stdio.h>
#include <string.h>
#define CAP 64                          /* power of two, more than 2 * n */
static int keys[CAP], idx[CAP], used[CAP];

static unsigned slot(int key) {         /* linear probing */
    unsigned h = (unsigned)key & (CAP - 1);
    while (used[h] && keys[h] != key) h = (h + 1) & (CAP - 1);
    return h;
}

int two_sum(const int *a, int n, int target, int *i_out, int *j_out) {
    memset(used, 0, sizeof used);
    for (int j = 0; j < n; j++) {
        unsigned h = slot(target - a[j]);   /* seen the partner before? */
        if (used[h]) { *i_out = idx[h]; *j_out = j; return 1; }
        h = slot(a[j]);
        if (!used[h]) { used[h] = 1; keys[h] = a[j]; idx[h] = j; }
    }
    return 0;
}

int main(void) {
    int a[] = {2, 7, 11, 15}, b[] = {3, 3}, c[] = {-3, 4, 3, 90}, d[] = {1, 2, 3}, i, j;
    if (two_sum(a, 4, 9, &i, &j)) printf("%d %d\n", i, j);
    if (two_sum(b, 2, 6, &i, &j)) printf("%d %d\n", i, j);
    if (two_sum(c, 4, 0, &i, &j)) printf("%d %d\n", i, j);
    if (!two_sum(d, 3, 7, &i, &j)) printf("no pair\n");
    return 0;
}

৩ · অ্যারে ও স্ট্রিং — প্রথম সারির প্রশ্ন

প্রায় প্রতিটি ইন্টারভিউর প্রথম প্রশ্ন এই গোত্রের। দেখতে সহজ, কিন্তু C-তে null terminator, size_t-এর underflow আর সীমার বাইরে পড়ার ফাঁদ এখানেই সবচেয়ে বেশি। রিভিশন: পর্ব ১৬ · অ্যারে, পর্ব ১৯ · স্ট্রিং।

সমস্যা ১ · স্ট্রিং উল্টানো, বাড়তি মেমরি ছাড়া (সহজ)

প্রশ্ন: একটি C স্ট্রিং in-place উল্টে দিন — নতুন অ্যারে না বানিয়ে।

জিজ্ঞেস করে নিন: স্ট্রিংটি কি পরিবর্তনযোগ্য মেমরিতে আছে, নাকি string literal? NULL আসতে পারে? শুধু ASCII, নাকি UTF-8-এর বাংলা অক্ষরও? (বাংলা অক্ষর একাধিক byte-এ থাকে, byte উল্টালে অক্ষর ভেঙে যায়।)

পদ্ধতি ও জটিলতা: দুই প্রান্তে দুটি পয়েন্টার রাখুন, অদলবদল করে মাঝের দিকে আসুন। সময় O(n), বাড়তি মেমরি O(1). এটাই two-pointer কৌশলের সবচেয়ে সরল রূপ।

#include <stdio.h>
#include <string.h>

void reverse(char *s) {
    if (s == NULL) return;              /* defensive: NULL input */
    size_t n = strlen(s);
    if (n < 2) return;                  /* "" and "x" need no work */
    char *l = s, *r = s + n - 1;
    while (l < r) {
        char t = *l;
        *l++ = *r;
        *r-- = t;
    }
}

int main(void) {
    char a[] = "Dhaka", b[] = "ab", c[] = "x", d[] = "";
    reverse(a); reverse(b); reverse(c); reverse(d);
    printf("[%s] [%s] [%s] [%s]\n", a, b, c, d);
    reverse(NULL);
    printf("NULL ok\n");
    return 0;
}

সমস্যা ২ · Palindrome যাচাই, যতিচিহ্ন বাদ দিয়ে (সহজ)

প্রশ্ন: একটি বাক্য palindrome কি না বলুন — শুধু অক্ষর ও অঙ্ক গুনবেন, বড়-ছোট হাতের পার্থক্য উপেক্ষা করবেন। “A man, a plan, a canal: Panama” হলো palindrome.

জিজ্ঞেস করে নিন: অঙ্কও গোনা হবে, নাকি শুধু অক্ষর? খালি স্ট্রিং বা শুধু যতিচিহ্ন থাকলে উত্তর কী? (সাধারণ রীতি: palindrome.)

পদ্ধতি ও জটিলতা: নতুন “পরিষ্কার” স্ট্রিং বানালে O(n) বাড়তি মেমরি লাগে। তার বদলে দুই পয়েন্টার অপ্রয়োজনীয় অক্ষর লাফিয়ে যায়। সময় O(n), মেমরি O(1).

#include <ctype.h>
#include <stdio.h>
#include <string.h>

int is_pal(const char *s) {
    size_t i = 0, j = strlen(s);        /* half-open: compare s[i], s[j-1] */
    while (i < j) {
        unsigned char a = (unsigned char)s[i];
        unsigned char b = (unsigned char)s[j - 1];
        if (!isalnum(a)) { i++; continue; }
        if (!isalnum(b)) { j--; continue; }
        if (tolower(a) != tolower(b)) return 0;
        i++;
        j--;
    }
    return 1;
}

int main(void) {
    const char *t[] = { "A man, a plan, a canal: Panama", "race a car",
                        "", ".,!", "No 'x' in Nixon", "ab" };
    for (int k = 0; k < 6; k++)
        printf("%d \"%s\"\n", is_pal(t[k]), t[k]);
    return 0;
}

সমস্যা ৩ · প্রথম অপুনরাবৃত্ত অক্ষর ও ডুপ্লিকেট খোঁজা (সহজ)

প্রশ্ন: স্ট্রিংয়ে যে অক্ষর ঠিক একবার আছে, তার মধ্যে প্রথমটির index দিন; না থাকলে -1. একই কৌশলে “কোন অক্ষর বা সংখ্যা একাধিকবার আছে” প্রশ্নেরও উত্তর হয়।

জিজ্ঞেস করে নিন: শুধু ছোট হাতের ইংরেজি অক্ষর, নাকি যেকোনো byte? বড়-ছোট হাত কি আলাদা?

পদ্ধতি ও জটিলতা: প্রতিটি অক্ষরের জন্য আবার পুরো স্ট্রিং গুনলে O(n²)। তার বদলে একটি frequency array — ২৫৬টি ঘরের একটি গোনার অ্যারে — দুবার পার হলেই হয়: সময় O(n), মেমরি O(1) (২৫৬ একটি ধ্রুবক)।

#include <stdio.h>

int first_unique(const char *s) {
    int cnt[256] = {0};                 /* one counter per byte value */
    for (const char *p = s; *p; p++)
        cnt[(unsigned char)*p]++;
    for (int i = 0; s[i]; i++)
        if (cnt[(unsigned char)s[i]] == 1) return i;
    return -1;
}

int main(void) {
    const char *t[] = { "leetcode", "loveleetcode", "aabb", "", "z" };
    for (int k = 0; k < 5; k++)
        printf("%-14s -> %d\n", t[k], first_unique(t[k]));
    return 0;
}

সমস্যা ৪ · Two sum (মাঝারি)

অংশ ২-এ পুরো সাত ধাপে সমাধান করা হয়েছে। ইন্টারভিউর আগে নিজে খাতায় তিনটি পদ্ধতিই আবার লিখুন, আর প্রতিটির জটিলতা মুখে বলুন। এর আত্মীয় সমস্যা: 3-sum, “যোগফল k এমন উপ-অ্যারে কয়টি” (prefix sum + hash), আর দুই পয়েন্টারের sliding window — যেমন “ধনাত্মক অ্যারেতে যোগফল অন্তত S এমন সবচেয়ে ছোট টানা অংশ”।

সমস্যা ৫ · সাজানো অ্যারে থেকে ডুপ্লিকেট বাদ, আর শূন্যগুলো শেষে পাঠানো (সহজ)

প্রশ্ন: (ক) সাজানো অ্যারে থেকে ডুপ্লিকেট in-place বাদ দিয়ে নতুন দৈর্ঘ্য ফেরত দিন। (খ) অ্যারের সব শূন্য শেষে পাঠান, বাকিদের ক্রম না বদলে।

জিজ্ঞেস করে নিন: অ্যারের শেষাংশে কী থাকল, তা কি গুরুত্বপূর্ণ? ক্রম ধরে রাখা কি বাধ্যতামূলক?

পদ্ধতি ও জটিলতা: একটি “পড়ার” পয়েন্টার আর একটি “লেখার” পয়েন্টার। পড়ার পয়েন্টার সব ঘর দেখে; রাখার মতো মান পেলে লেখার পয়েন্টারের জায়গায় বসায়। সময় O(n), মেমরি O(1).

#include <stdio.h>

int dedup(int *a, int n) {              /* a is sorted; returns new length */
    if (n == 0) return 0;
    int w = 1;                          /* write position */
    for (int r = 1; r < n; r++)         /* read position */
        if (a[r] != a[w - 1]) a[w++] = a[r];
    return w;
}

void move_zeros(int *a, int n) {        /* keep order of non-zeros */
    int w = 0;
    for (int r = 0; r < n; r++)
        if (a[r] != 0) a[w++] = a[r];
    while (w < n) a[w++] = 0;
}

void show(const int *a, int n) {
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("| n=%d\n", n);
}

int main(void) {
    int a[] = {1, 1, 2, 3, 3, 3, 7};
    int b[] = {0, 1, 0, 3, 12};
    show(a, dedup(a, 7));
    move_zeros(b, 5);
    show(b, 5);
    return 0;
}

সমস্যা ৬ · অ্যারে k ঘর ঘোরানো, আর ম্যাট্রিক্স ৯০° ঘোরানো (মাঝারি)

প্রশ্ন: n আকারের অ্যারেকে ডানে k ঘর ঘোরান — [1 2 3 4 5], k = 2 হলে [4 5 1 2 3]. বাড়তি অ্যারে ছাড়া।

জিজ্ঞেস করে নিন: k কি n-এর চেয়ে বড় হতে পারে? ঋণাত্মক? n = 0?

পদ্ধতি ও জটিলতা: একবারে এক ঘর ঘোরানো k বার করলে O(n·k). নতুন অ্যারেতে কপি করলে O(n) মেমরি। সুন্দর কৌশল: পুরো অ্যারে উল্টান, তারপর প্রথম k ঘর, তারপর বাকিটা — সময় O(n), মেমরি O(1).

static void rev(int *a, int i, int j) {
    while (i < j) { int t = a[i]; a[i++] = a[j]; a[j--] = t; }
}

void rotate_right(int *a, int n, int k) {   /* [1 2 3 4 5], k=2 -> [4 5 1 2 3] */
    if (n <= 1) return;
    k %= n;
    if (k < 0) k += n;                  /* negative k = rotate left */
    rev(a, 0, n - 1);                   /* 5 4 3 2 1 */
    rev(a, 0, k - 1);                   /* 4 5 3 2 1 */
    rev(a, k, n - 1);                   /* 4 5 1 2 3 */
}

k %= n না করলে k = 7, n = 5-এ rev(a, 0, 6) অ্যারের বাইরে লিখত। আর n = 0-এ k %= n নিজেই শূন্য দিয়ে ভাগ — তাই n <= 1 পরীক্ষাটি আগে।

ম্যাট্রিক্স ৯০° ঘড়ির কাঁটার দিকে: n×n matrix-কে আগে transpose করুন (a[i][j] ↔ a[j][i], শুধু j > i ঘরগুলোতে), তারপর প্রতিটি সারি উল্টান। সময় O(n²), মেমরি O(1). উল্টো দিকে ঘোরাতে transpose-এর পর সারির বদলে কলাম উল্টান। রিভিশন: পর্ব ২১। ফলো-আপ: ম্যাট্রিক্স বর্গাকার না হলে in-place করা যায় কি? (সাধারণভাবে না — আকারই বদলে যায়, নতুন অ্যারে লাগে।)

৪ · C-এর প্রিয় প্রশ্ন — লাইব্রেরি ফাংশন নিজে লিখুন

C-ইন্টারভিউর একটি বিশেষ গোত্র: “strlen, strcpy, memcpy, memmove বা atoi নিজে লিখুন।” এখানে অ্যালগরিদম সহজ — পরীক্ষা হয় খুঁটিনাটির: const, size_t, overlap, overflow. রিভিশন: পর্ব ১৮, পর্ব ৪৫, পর্ব ২৬।

সমস্যা ৭ · strlen, strcpy, memcpy আর memmove (মাঝারি)

প্রশ্ন: এই চারটি ফাংশন standard library ছাড়া লিখুন। তারপর ব্যাখ্যা করুন memcpy আর memmove-এর পার্থক্য কী।

জিজ্ঞেস করে নিন: standard-এর মতো একই signature চাই? (void *memmove(void *dst, const void *src, size_t n)) — হ্যাঁ ধরে নিন।

পদ্ধতি: memcpy-তে উৎস আর গন্তব্য একে অপরের ওপর পড়তে (overlap) পারবে না — পড়লে undefined behavior. memmove-কে overlap সামলাতে হয়: গন্তব্য উৎসের আগে থাকলে সামনে থেকে কপি, পরে থাকলে পেছন থেকে। সব ক্ষেত্রে সময় O(n).

char *my_strcpy(char *dst, const char *src) {
    char *d = dst;
    while ((*d++ = *src++) != '\0')
        ;                               /* copies the '\0' too */
    return dst;
}

void *my_memcpy(void *dst, const void *src, size_t n) {
    unsigned char *d = dst;             /* byte by byte through unsigned char */
    const unsigned char *s = src;
    while (n--) *d++ = *s++;
    return dst;                         /* overlap is undefined for memcpy */
}

#include <stdio.h>
#include <stddef.h>

size_t my_strlen(const char *s) {
    const char *p = s;
    while (*p) p++;
    return (size_t)(p - s);
}

void *my_memmove(void *dst, const void *src, size_t n) {
    unsigned char *d = dst;
    const unsigned char *s = src;
    if (d == s || n == 0) return dst;
    if (d < s) {                        /* dst before src: copy forward */
        for (size_t i = 0; i < n; i++) d[i] = s[i];
    } else {                            /* dst after src: copy backward */
        for (size_t i = n; i > 0; i--) d[i - 1] = s[i - 1];
    }
    return dst;
}

int main(void) {
    char buf[16] = "abcdefgh";
    printf("len=%zu\n", my_strlen(buf));
    my_memmove(buf + 2, buf, 6);        /* overlapping, shift right */
    printf("%s\n", buf);
    my_memmove(buf, buf + 2, 6);        /* overlapping, shift left */
    printf("%s\n", buf);
    return 0;
}

সমস্যা ৮ · atoi লিখুন — overflow সামলে (মাঝারি)

প্রশ্ন: স্ট্রিং থেকে int বানান: শুরুর ফাঁকা জায়গা বাদ, ঐচ্ছিক +/-, তারপর যতক্ষণ অঙ্ক। মান int-এর সীমা ছাড়ালে INT_MAX বা INT_MIN ফেরত দিন।

জিজ্ঞেস করে নিন: overflow হলে কী চাই — সীমায় আটকানো, নাকি error জানানো? অঙ্ক না পেলে কী? (এখানে ০।) "+-12" বৈধ? (না।)

পদ্ধতি ও জটিলতা: আসল চ্যালেঞ্জ v * 10 + d করার আগেই বোঝা যে এটি overflow করবে কি না — কারণ signed overflow ঘটে গেলে আর ধরা যায় না, সেটি undefined behavior. সময় O(n).

#include <ctype.h>
#include <limits.h>
#include <stdio.h>

int my_atoi(const char *s) {            /* clamps to INT_MIN / INT_MAX */
    while (isspace((unsigned char)*s)) s++;
    int sign = 1;
    if (*s == '+' || *s == '-') {
        if (*s == '-') sign = -1;
        s++;
    }
    int v = 0;
    while (isdigit((unsigned char)*s)) {
        int d = *s - '0';
        if (v > (INT_MAX - d) / 10)     /* v * 10 + d would overflow */
            return sign == 1 ? INT_MAX : INT_MIN;
        v = v * 10 + d;
        s++;
    }
    return sign * v;
}

int main(void) {
    const char *t[] = { "42", "   -42", "4193 words", "words 987",
                        "-91283472332", "2147483648", "+-12", "" };
    for (int k = 0; k < 8; k++)
        printf("%-14s -> %d\n", t[k], my_atoi(t[k]));
    return 0;
}

৫ · লিংকড লিস্ট, স্ট্যাক ও হিপ

পয়েন্টার নিয়ে আপনার আরাম কতটা, ইন্টারভিউয়ার সেটা সবচেয়ে ভালো বোঝেন linked list-এর প্রশ্নে। এখানে খাতায় বাক্স আর তীর আঁকা প্রায় বাধ্যতামূলক অভ্যাস। রিভিশন: পর্ব ৩৩, পর্ব ৩৪, পর্ব ৩৬।

সমস্যা ৯ · লিংকড লিস্ট উল্টানো, লুপ দিয়ে (সহজ, কিন্তু সবচেয়ে বেশি জিজ্ঞাসিত)

প্রশ্ন: একমুখী লিংকড লিস্টের head দেওয়া আছে। লিস্টটি উল্টে নতুন head ফেরত দিন।

জিজ্ঞেস করে নিন: নতুন node বানানো চলবে? (না — শুধু তীর ঘোরাতে হবে।) খালি লিস্ট আসতে পারে?

পদ্ধতি ও জটিলতা: তিনটি পয়েন্টার — prev, cur, nxt. প্রতিটি node-এ তীর উল্টো দিকে ঘোরান। সময় O(n), মেমরি O(1). নিচে ধাপে ধাপে দেখুন:

1struct node *reverse(struct node *head) {2    struct node *prev = NULL, *cur = head;3    while (cur) {4        struct node *nxt = cur->next;5        cur->next = prev;6        prev = cur;7        cur = nxt;8    }9    return prev;10}

#include <stdio.h>

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

struct node *reverse(struct node *head) {
    struct node *prev = NULL, *cur = head;
    while (cur) {
        struct node *nxt = cur->next;   /* save the rest of the list */
        cur->next = prev;               /* turn the arrow around */
        prev = cur;
        cur = nxt;
    }
    return prev;                        /* new head */
}

void print(const struct node *h) {
    for (; h; h = h->next) printf("%d ", h->val);
    printf("|\n");
}

int main(void) {
    struct node n[5], one = {9, NULL};
    for (int i = 0; i < 5; i++)         /* build 1 -> 2 -> 3 -> 4 -> 5 */
        n[i] = (struct node){ i + 1, (i < 4) ? &n[i + 1] : NULL };
    print(reverse(&n[0]));
    print(reverse(NULL));
    print(reverse(&one));
    return 0;
}

সমস্যা ১০ · লিস্টে cycle আছে কি না (মাঝারি)

প্রশ্ন: কোনো node-এর next কি আগের কোনো node-এ ফিরে গেছে? থাকলে সাধারণ traversal কখনো শেষ হবে না।

পদ্ধতি ও জটিলতা: দেখা node-গুলোর ঠিকানা hash set-এ রাখলে O(n) মেমরি। Floyd-এর cycle detection (“কচ্ছপ ও খরগোশ”): একটি পয়েন্টার এক ঘর, অন্যটি দুই ঘর করে চলে। cycle থাকলে দ্রুতটি একসময় ধীরটিকে পেছন থেকে ধরে ফেলবে — বৃত্তাকার ট্র্যাকে দুজন দৌড়বিদের মতো। সময় O(n), মেমরি O(1).

int has_cycle(const struct node *head) {
    const struct node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;              /* 1 step */
        fast = fast->next->next;        /* 2 steps */
        if (slow == fast) return 1;     /* met inside the cycle */
    }
    return 0;                           /* fast fell off the end */
}

কেন ধরবেই? দুজনেই cycle-এ ঢোকার পর প্রতি ধাপে তাদের দূরত্ব ঠিক ১ করে কমে, তাই লাফিয়ে পার হয়ে যাওয়া অসম্ভব। Edge case: খালি লিস্ট, এক node যার next নিজেই, দুই node-এর cycle. fast->next যাচাই না করলে fast->next->next-এ NULL dereference. ফলো-আপ: cycle কোন node থেকে শুরু? (মিলনের পর একটি পয়েন্টার head-এ ফিরিয়ে দুজনকেই এক ঘর করে চালান — যেখানে মিলবে, সেটাই শুরু।) cycle-এর দৈর্ঘ্য? (মিলনবিন্দু থেকে এক পাক ঘুরে গুনুন।)

সমস্যা ১১ · দুটি সাজানো লিস্ট জোড়া লাগানো (সহজ)

প্রশ্ন: দুটি ছোট-থেকে-বড় সাজানো লিস্ট মিলিয়ে একটি সাজানো লিস্ট বানান — নতুন node না বানিয়ে।

পদ্ধতি ও জটিলতা: merge sort-এর merge ধাপ (পর্ব ৪০)। একটি dummy node রাখলে “প্রথম node কোনটা” — এই আলাদা ক্ষেত্রটি আর লাগে না। সময় O(n + m), মেমরি O(1).

struct node *merge(struct node *a, struct node *b) {
    struct node dummy = {0, NULL};      /* dummy head: no special case for first node */
    struct node *t = &dummy;
    while (a != NULL && b != NULL) {
        if (a->val <= b->val) { t->next = a; a = a->next; }   /* <= keeps it stable */
        else                  { t->next = b; b = b->next; }
        t = t->next;
    }
    t->next = (a != NULL) ? a : b;      /* attach whatever is left */
    return dummy.next;
}

Edge case: একটি বা দুটি লিস্টই খালি, সমান মান, একটি লিস্ট অন্যটির চেয়ে অনেক লম্বা। ফলো-আপ: k-টি সাজানো লিস্ট জোড়া লাগান — min-heap দিয়ে O(N log k), যেখানে N মোট node (k-way merge, পর্ব ৩৬)।

সমস্যা ১২ · বন্ধনী ঠিকঠাক মেলানো কি না (সহজ)

প্রশ্ন: ()[]{} দিয়ে গঠিত একটি স্ট্রিং বৈধ কি না — প্রতিটি খোলা বন্ধনী একই ধরনের বন্ধনী দিয়ে, সঠিক ক্রমে বন্ধ হতে হবে।

জিজ্ঞেস করে নিন: অন্য অক্ষর থাকতে পারে? সর্বোচ্চ দৈর্ঘ্য কত?

পদ্ধতি ও জটিলতা: সবচেয়ে শেষে খোলা বন্ধনীটিই আগে বন্ধ হতে হবে — এটাই LIFO, অর্থাৎ stack (পর্ব ৩৪)। সময় O(n), মেমরি O(n).

#include <stdio.h>

int valid(const char *s) {
    char st[128];                       /* stack of open brackets */
    int top = 0;
    for (; *s; s++) {
        char c = *s;
        if (c == '(' || c == '[' || c == '{') {
            if (top == (int)sizeof st) return 0;    /* too deep */
            st[top++] = c;
        } else if (c == ')' || c == ']' || c == '}') {
            char want = (c == ')') ? '(' : (c == ']') ? '[' : '{';
            if (top == 0 || st[top - 1] != want) return 0;
            top--;
        }                               /* other characters are ignored */
    }
    return top == 0;                    /* nothing left open */
}

int main(void) {
    const char *t[] = { "()[]{}", "([{}])", "(]", "([)]", "((", ")(", "", "a(b)c" };
    for (int k = 0; k < 8; k++)
        printf("%-8s -> %s\n", t[k], valid(t[k]) ? "valid" : "invalid");
    return 0;
}

সমস্যা ১৩ · k-তম বৃহত্তম সংখ্যা (মাঝারি)

প্রশ্ন: n টি সংখ্যার মধ্যে k-তম বৃহত্তমটি বের করুন। যেমন [3 2 1 5 6 4], k = 2 → 5.

জিজ্ঞেস করে নিন: ডুপ্লিকেট থাকলে আলাদা গোনা হবে? সংখ্যাগুলো কি একসাথে আসে, নাকি স্ট্রিমে একটা একটা করে?

পদ্ধতি ও জটিলতা: তিনটি উত্তর, প্রতিটির জায়গা আছে:

• সাজিয়ে নেওয়া: O(n log n) — সবচেয়ে সহজ, প্রথমে এটা বলুন।
• k আকারের min-heap: heap-এ সবসময় এ পর্যন্ত দেখা বৃহত্তম k টি থাকে, আর শীর্ষে থাকে তাদের মধ্যে ছোটটি। সময় O(n log k), মেমরি O(k). স্ট্রিমের জন্য এটাই সেরা (পর্ব ৩৬)।
• Quickselect: quicksort-এর partition, কিন্তু শুধু একদিকে নামা — গড়ে O(n), খারাপ ক্ষেত্রে O(n²)।

static void sift_down(int *h, int k, int i) {     /* min-heap of size k */
    for (;;) {
        int s = i, l = 2 * i + 1, r = l + 1;
        if (l < k && h[l] < h[s]) s = l;
        if (r < k && h[r] < h[s]) s = r;
        if (s == i) return;
        int t = h[i]; h[i] = h[s]; h[s] = t;
        i = s;
    }
}

/* k-th largest of a[0..n-1]; 1 <= k <= n; h has room for k ints */
int kth_largest(const int *a, int n, int k, int *h) {
    for (int i = 0; i < k; i++) h[i] = a[i];
    for (int i = k / 2 - 1; i >= 0; i--) sift_down(h, k, i);   /* heapify */
    for (int i = k; i < n; i++)
        if (a[i] > h[0]) { h[0] = a[i]; sift_down(h, k, 0); }  /* replace smallest */
    return h[0];                        /* smallest of the k largest */
}

Edge case: k = 1 (সর্বোচ্চ), k = n (সর্বনিম্ন), সব মান সমান। ফলো-আপ: সংখ্যা এত বেশি যে মেমরিতে ধরে না? (heap-এ শুধু k টি রাখুন, ফাইল থেকে পড়ে যান।) চলমান median? (দুটি heap — পর্ব ৩৬-এর running median.)

৬ · সার্চিং, বিট ও DP

এই তিন গোত্রে একটি করে “চাবির ধারণা” আছে: binary search-এ সীমানা, বিটে x & (x - 1), DP-তে state. চাবিটা ধরতে পারলে সমস্যার বড় অংশ সমাধান। রিভিশন: পর্ব ৪১, পর্ব ৯, পর্ব ৪২, পর্ব ৪৩।

সমস্যা ১৪ · Binary search-এর রূপভেদ — প্রথম অবস্থান, গণনা (মাঝারি)

প্রশ্ন: সাজানো অ্যারেতে x-এর প্রথম অবস্থান দিন (না থাকলে -1). তারপর x কতবার আছে বলুন।

জিজ্ঞেস করে নিন: ডুপ্লিকেট আছে? অ্যারে খালি হতে পারে? ছোট থেকে বড়, নাকি উল্টো?

পদ্ধতি ও জটিলতা: সাধারণ binary search মান পেলেই থামে — কিন্তু সেটা যেকোনো একটি কপি হতে পারে। তার বদলে lower bound লিখুন: “প্রথম যে ঘরে মান x-এর সমান বা বড়।” এই একটি ফাংশন দিয়েই সব রূপভেদ হয়। সময় O(log n).

#include <stdio.h>

/* first index i with a[i] >= x, or n if there is none */
int lower_bound(const int *a, int n, int x) {
    int lo = 0, hi = n;                 /* half-open range [lo, hi) */
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;   /* not (lo + hi) / 2: no overflow */
        if (a[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int first_occ(const int *a, int n, int x) {
    int i = lower_bound(a, n, x);
    return (i < n && a[i] == x) ? i : -1;
}

int main(void) {
    int a[] = {1, 3, 3, 3, 5, 8};
    int n = 6, q[] = {3, 4, 1, 8, 0, 9};
    for (int k = 0; k < 6; k++)
        printf("x=%d first=%d lb=%d\n", q[k], first_occ(a, n, q[k]),
               lower_bound(a, n, q[k]));
    printf("count(3)=%d\n", lower_bound(a, n, 4) - lower_bound(a, n, 3));
    return 0;
}

সমস্যা ১৫ · Set bit গোনা, আর সংখ্যাটি ২-এর ঘাত কি না (সহজ)

প্রশ্ন: একটি unsigned সংখ্যায় কয়টি বিট ১, আর সংখ্যাটি ২-এর ঘাত কি না বলুন।

জিজ্ঞেস করে নিন: signed নাকি unsigned? কত বিট? শূন্যকে কী ধরা হবে?

পদ্ধতি ও জটিলতা: প্রতিটি বিট সরিয়ে দেখলে ৩২ ধাপ। Brian Kernighan-এর নামে পরিচিত কৌশল: x &= x - 1 সবচেয়ে ডানের ১-কে মুছে দেয়, তাই লুপ চলে ঠিক যতগুলো ১ আছে ততবার। ২-এর ঘাতে ঠিক একটি বিট ১, তাই x & (x - 1) শূন্য হয় (পর্ব ৯)।

#include <stdio.h>

int popcount(unsigned x) {
    int c = 0;
    while (x) {
        x &= x - 1;                     /* clears the lowest set bit */
        c++;
    }
    return c;
}

int is_pow2(unsigned x) {
    return x != 0 && (x & (x - 1)) == 0;
}

int main(void) {
    unsigned t[] = {0u, 1u, 6u, 8u, 255u, 1024u, 0xFFFFFFFFu};
    for (int k = 0; k < 7; k++)
        printf("%10u bits=%2d pow2=%d\n", t[k], popcount(t[k]), is_pow2(t[k]));
    return 0;
}

সমস্যা ১৬ · সিঁড়ি বেয়ে ওঠা ও কয়েন চেঞ্জ (মাঝারি)

প্রশ্ন: (ক) n ধাপের সিঁড়িতে একবারে ১ বা ২ ধাপ উঠতে পারেন — কত উপায়ে চূড়ায় পৌঁছাবেন? (খ) কিছু নোটের মান দেওয়া আছে, প্রতিটি যতবার খুশি নেওয়া যায় — নির্দিষ্ট টাকা বানাতে সবচেয়ে কম কয়টি নোট লাগবে? সম্ভব না হলে -1.

জিজ্ঞেস করে নিন: n বা টাকার পরিমাণ কত বড়? উত্তর কি int-এ ধরবে? (সিঁড়ির উত্তর Fibonacci-র মতো দ্রুত বাড়ে।)

পদ্ধতি ও জটিলতা: দুটোই dynamic programming (পর্ব ৪২)। সিঁড়ি: ways(n) = ways(n-1) + ways(n-2) — দুটি ভ্যারিয়েবলেই হয়, সময় O(n), মেমরি O(1). কয়েন: dp[x] = x টাকা বানানোর সর্বনিম্ন নোট; প্রতিটি নোট c-এর জন্য dp[x - c] + 1 যাচাই। সময় O(amount × k).

#include <limits.h>
#include <stdio.h>

long long stairs(int n) {               /* ways to climb with 1 or 2 steps */
    long long a = 1, b = 1;             /* ways(0), ways(1) */
    for (int i = 2; i <= n; i++) { long long c = a + b; a = b; b = c; }
    return b;
}

int min_coins(const int *coin, int k, int amount) {   /* amount <= 100 */
    int dp[101];
    dp[0] = 0;
    for (int x = 1; x <= amount; x++) {
        dp[x] = INT_MAX;                /* INT_MAX = not reachable yet */
        for (int j = 0; j < k; j++)
            if (coin[j] <= x && dp[x - coin[j]] != INT_MAX && dp[x - coin[j]] + 1 < dp[x])
                dp[x] = dp[x - coin[j]] + 1;
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main(void) {
    printf("stairs: %lld %lld %lld %lld\n", stairs(0), stairs(1), stairs(5), stairs(50));
    int c1[] = {1, 5, 10, 20}, c2[] = {2}, c3[] = {1, 3, 4};
    printf("coins: %d %d %d %d\n", min_coins(c1, 4, 37), min_coins(c2, 1, 3),
           min_coins(c3, 3, 6), min_coins(c1, 4, 0));
    return 0;
}

৭ · C-নির্দিষ্ট ধারণার প্রশ্ন — সংক্ষিপ্ত, কিন্তু গভীর

C-ভিত্তিক পদে (এমবেডেড, সিস্টেম, firmware, নেটওয়ার্কিং) কোডিং সমস্যার পাশাপাশি এই প্রশ্নগুলো প্রায়ই আসে। উত্তর দেওয়ার ভালো কাঠামো: এক লাইনে সংজ্ঞা → একটি ছোট উদাহরণ → একটি ফাঁদ বা বাস্তব ব্যবহার। প্রতিটি প্রশ্ন আগে নিজে মুখে উত্তর দিন, তারপর খুলুন। রিভিশন: পর্ব ১৪, পর্ব ২০, পর্ব ২২, পর্ব ৩১, পর্ব ৪৫, পর্ব ৪৬।

void f(int arr[10]) { printf("%zu\n", sizeof arr); }   /* 8: pointer */
int main(void) { int a[10]; printf("%zu\n", sizeof a); f(a); }   /* 40, then 8 */

struct a { char c; int i; char d; };   /* 1 + 3 pad + 4 + 1 + 3 pad = 12 */
struct b { int i; char c; char d; };   /* 4 + 1 + 1 + 2 pad = 8 */

#include <stdio.h>

int main(void) {
    unsigned int x = 1;
    unsigned char *p = (unsigned char *)&x;   /* look at the first byte */
    printf("%s-endian\n", *p == 1 ? "little" : "big");
    return 0;
}

int will_overflow(int x) { return x + 1 < x; }   /* meant as overflow check */

int *tmp = realloc(p, new_n * sizeof *p);
if (tmp == NULL) { /* p is still valid: handle error, free(p) later */ }
else p = tmp;

$ gcc -g -fsanitize=address,undefined -Wall -Wextra bug.c -o bug
$ ./bug                    # ASan prints the bad line and the stack
$ gcc -g -O0 bug.c -o bug && gdb ./bug
(gdb) run
(gdb) bt                   # backtrace: which function, which line
(gdb) print p              # inspect the suspicious pointer
$ valgrind ./bug           # second opinion on memory errors

৮ · কথা বলা, আচরণগত প্রশ্ন আর AI

একই সমাধান জানা দুজন প্রার্থীর একজন নির্বাচিত হন, অন্যজন হন না — প্রায়ই পার্থক্যটা যোগাযোগে। এই দক্ষতাও অনুশীলনে বাড়ে, ঠিক কোডের মতো।

ইন্টারভিউর ঘরে পাঁচটি অভ্যাস

• জোরে ভাবুন (think aloud): “আমি প্রথমে brute force ভাবছি… এটা O(n²), n যদি ১০^৫ হয় তাহলে ধীর… তাই hash ভাবছি।” চুপ করে দুই মিনিট ভাবার চেয়ে অর্ধেক-গোছানো ভাবনা বলাও ভালো — ইন্টারভিউয়ার পথ দেখে সাহায্য করতে পারেন।
• প্রশ্ন করুন, ধরে নেবেন না: “ইনপুট কি সাজানো?”, “খালি অ্যারে আসতে পারে?” — এগুলো দুর্বলতা নয়, পেশাদারিত্ব। বাস্তব কাজেও অস্পষ্ট চাহিদা নিয়েই শুরু হয়।
• Hint-কে উপহার ভাবুন: ইন্টারভিউয়ার “যদি অ্যারেটা সাজানো থাকত?” বললে সেটা একটা দরজা। ধন্যবাদ দিয়ে ধরুন, আর বলুন hint থেকে কী বুঝলেন। hint নিয়ে এগোনো সাধারণত hint উপেক্ষা করে আটকে থাকার চেয়ে অনেক ভালো দেখায়।
• ভুল স্বীকার করুন, দ্রুত: dry run-এ নিজের বাগ ধরলে বলুন, “এখানে একটা off-by-one আছে, ঠিক করছি।” নিজের ভুল নিজে ধরা ইন্টারভিউতে খুব ইতিবাচক সংকেত — বাস্তব কাজে এটাই সবচেয়ে দরকারি অভ্যাস।
• না জানলে সৎ থাকুন: “restrict নিয়ে নিশ্চিত নই, তবে যতটুকু জানি…” — বানিয়ে বলা অভিজ্ঞ ইন্টারভিউয়ার সাথে সাথে ধরে ফেলেন।

আচরণগত প্রশ্নে STAR কাঠামো

“এমন একটা সময়ের কথা বলুন যখন…” — এ ধরনের প্রশ্নে STAR কাঠামোয় উত্তর গোছান: Situation (পরিস্থিতি), Task (আপনার দায়িত্ব), Action (আপনি নিজে কী করলেন), Result (ফল, সম্ভব হলে সংখ্যায়, আর কী শিখলেন)।

৪–৫টি এমন গল্প আগে থেকে তৈরি রাখুন: একটি কঠিন বাগ, একটি দলগত মতবিরোধ, একটি ব্যর্থতা ও তা থেকে শেখা, নিজে থেকে নেওয়া একটি উদ্যোগ। বানানো গল্প নয় — পরের প্রশ্নেই ফাঁক বেরিয়ে যায়।

AI-এর যুগে ইন্টারভিউ: নিয়ম আর সততা

কেন মুখস্থ নয়, বোঝা? ইন্টারভিউয়ার জানেন, জনপ্রিয় সমস্যার সমাধান অনলাইনে আছে। তাই আসল পরীক্ষা হয় ফলো-আপে: “এবার মেমরি O(1) করুন”, “ইনপুট স্ট্রিমে এলে?” মুখস্থ সমাধান এখানেই ভেঙে পড়ে, আর বোঝা সমাধান নতুন শর্তে বাঁকানো যায়। এই পাতার প্রতিটি সমস্যায় ফলো-আপ রাখার কারণ এটাই।

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

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

• সমাধান দেখার আগে নিজে অন্তত ২০ মিনিট চেষ্টা করেছি, আর খাতায় পদ্ধতি লিখেছি
• AI-এর বলা জটিলতা নিজে হিসাব করে মিলিয়েছি — AI প্রায়ই ভুল Big-O বলে
• AI-এর C কোড -Wall -Wextra -fsanitize=address দিয়ে চালিয়েছি, আর নিজের edge case-এ পরীক্ষা করেছি
• একদিন পরে AI ছাড়া একই সমস্যা আবার শূন্য থেকে সমাধান করতে পেরেছি
• সমাধানটি অন্য কাউকে (বা নিজেকে, জোরে) পাঁচ মিনিটে ব্যাখ্যা করতে পারি

৯ · চার সপ্তাহের অনুশীলন পরিকল্পনা

প্রতিদিন ১.৫–২ ঘণ্টা ধরে নিচের ছকটি একটি কাঠামো — আপনার হাতে সময় কম-বেশি হলে সপ্তাহগুলো ছোট বা লম্বা করুন। প্রতিটি সপ্তাহে আগে কোর্সের পর্ব রিভিশন, তারপর সেই বিষয়ের সমস্যা। LeetCode, HackerRank, Codeforces আর বাংলাদেশে জনপ্রিয় Toph ও LightOJ-এর মতো প্ল্যাটফর্মে এ ধরনের অনেক সমস্যা পাবেন — বিষয় বা tag ধরে বেছে নিন।

ইন্টারভিউর আগের রাতে নতুন কিছু শিখতে যাবেন না। নিজের ক্যাপস্টোন প্রজেক্ট (পর্ব ৫২) আরেকবার দেখে নিন — “আপনার প্রজেক্টে সবচেয়ে কঠিন অংশ কোনটা ছিল?” প্রশ্নটি প্রায় নিশ্চিত, আর এর উত্তরেই আপনি সবচেয়ে আত্মবিশ্বাসী থাকবেন।

১০ · কোর্স সমাপ্তি — ৫৬টি পর্বের পরে আপনি কোথায়

এটি ৮টি মডিউল আর ৫৬টি পর্বের এই কোর্সের শেষ পর্ব। একবার পেছনে তাকান। পর্ব ১-এ প্রশ্ন ছিল, “C কেন?” পর্ব ৩-এ দেখেছিলেন, একটি .c ফাইল কীভাবে প্রোগ্রাম হয়। আজ আপনি একটি লিংকড লিস্টের তীর ঘোরাতে পারেন, memmove কেন পেছন থেকে কপি করে বোঝাতে পারেন, আর একটি অচেনা সমস্যাকে সাত ধাপে ভাঙতে পারেন।

এখন আপনি যা পারেন

• কম্পিউটারের ভেতরে ডেটা কীভাবে থাকে — বিট, byte, পয়েন্টার, stack আর heap — নিজের ভাষায় ব্যাখ্যা করতে।
• অ্যারে, স্ট্রিং, struct, লিংকড লিস্ট, স্ট্যাক, কিউ, ট্রি, হিপ, হ্যাশ টেবিল আর গ্রাফ নিজ হাতে বানাতে।
• যেকোনো সমাধানের সময় ও মেমরি Big-O-তে মাপতে, আর trade-off বুঝে পদ্ধতি বাছতে।
• header, Makefile, test, sanitizer আর debugger দিয়ে একটি বহু-ফাইলের প্রোগ্রাম নির্ভরযোগ্যভাবে দাঁড় করাতে।
• process, thread, socket আর এমবেডেড হার্ডওয়্যারের সাথে C কীভাবে কথা বলে, তা বুঝতে।
• AI-এর লেখা কোড যাচাই করতে — আর দরকারে তার ভুল ধরতে।

অনুশীলন চালিয়ে যাওয়ার উপায়

• প্রতিদিন অল্প: দিনে একটি সমস্যা, পুরো সাত ধাপে — সপ্তাহে একদিন বড় সেশনের চেয়ে বেশি কাজে দেয়।
• কনটেস্টে নিয়মিত: Codeforces বা Toph-এর কনটেস্ট আর পরে upsolving (পর্ব ৪৪)।
• একটি প্রজেক্ট বড় করুন: ক্যাপস্টোনে নতুন একটি feature যোগ করুন, test লিখুন, GitHub-এ রাখুন — portfolio নিজে থেকেই বড় হবে।
• অন্যকে শেখান: বন্ধুকে একটি পয়েন্টারের সমস্যা বোঝাতে গেলেই বুঝবেন নিজের কোথায় ফাঁক আছে।
• মাঝে মাঝে ফিরে আসুন: পর্ব ৫৩–৫৫-এর প্রশ্নব্যাংক দিয়ে রিভিশন, আর কোর্স হোম থেকে যে পর্ব দুর্বল লাগে সেটি আবার।

এরপর কোন পথে