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

১ · Java কোডিং ইন্টারভিউ কেমন হয়

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

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

ইন্টারভিউয়ারের মূল্যায়নে কী থাকে

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

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

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

পর্ব ৫৪-এ এই ধরনের অনেক কৌশল কনটেস্টের দৃষ্টিতে দেখেছেন — দ্রুত I/O, constraints পড়ে পদ্ধতি বাছা, Dijkstra. এখানে দৃষ্টি আলাদা: ইন্টারভিউতে ব্যাখ্যা, পরিষ্কার কোড আর ফলো-আপ গুরুত্বপূর্ণ, গতির শর্টকাট নয়। তাই একই কৌশল এলেও সমস্যাগুলো ভিন্ন, আর প্রতিটির সাথে আছে ইন্টারভিউয়ারের সম্ভাব্য পরের প্রশ্ন।

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

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

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

- উত্তর সবসময় থাকবে, নাকি নাও থাকতে পারে?
- একই index দুবার নেওয়া যাবে? (না)
- array কি সাজানো? (না)
- 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)  ঋণাত্মক
[5],            target 10 ->  নেই     5+5 চলবে না

for i in 0..n-1:
    for j in i+1..n-1:
        if a[i] + a[j] == target: return (i, j)
সময় O(n²), বাড়তি মেমরি O(1)

ভেতরের লুপ শুধু একটা প্রশ্ন করে:
  "target - a[j] কি আগে দেখেছি?"
-> দেখা মানগুলো HashMap-এ রাখি
   (মান -> index), খোঁজা গড়ে O(1)

for j in 0..n-1:
    i = seen.get(target - a[j])
    if i != null: return Pair(i, j)
    seen.putIfAbsent(a[j], j)  // আগে খুঁজি, পরে রাখি
return Optional.empty()         // "নেই" টাইপেই বলা

j=0: need=3, seen-এ নেই    -> seen{3=0}
j=1: need=3, seen-এ আছে(0) -> Pair[i=0, j=1]
উল্টো ক্রমে (আগে রাখি, পরে খুঁজি) [5], 10
-> নিজের সাথেই জোড়া (0, 0) — ভুল!

HashMap: সময় গড়ে O(n), মেমরি O(n)
- array সাজানো হলে? -> two pointers, O(1) মেমরি
- সব জোড়া চাই? 3-sum? -> sort + two pointers, O(n²)
- target - a[j] কি overflow করতে পারে?

import java.util.*;

class Main {
    record Pair(int i, int j) {}                            // two indices, no int[] guessing

    static Optional<Pair> twoSum(int[] a, int target) {
        Map<Integer, Integer> seen = new HashMap<>();       // value -> index
        for (int j = 0; j < a.length; j++) {
            Integer i = seen.get(target - a[j]);            // look first ...
            if (i != null) return Optional.of(new Pair(i, j));
            seen.putIfAbsent(a[j], j);                      // ... then insert
        }
        return Optional.empty();
    }

    public static void main(String[] args) {
        int[][] tests = {{2, 7, 11, 15}, {3, 3}, {-3, 4, 3, 90}, {5}};
        int[] targets = {9, 6, 0, 10};
        for (int t = 0; t < tests.length; t++) {
            String out = twoSum(tests[t], targets[t]).map(Pair::toString).orElse("no pair");
            System.out.println(out);
        }
    }
}

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

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

• শুরুতে: “আমি ধরে নিচ্ছি array খালি হতে পারে, আর উত্তর না থাকলে খালি Optional দেব — ঠিক আছে?”
• পদ্ধতি বাছাইয়ে: “দুটি লুপে O(n²) হয়; n এক লাখ হলে সেটা ধীর। তাই HashMap ভাবছি — মেমরি বাড়বে, সময় কমবে।”
• লেখার মাঝে: “এখানে আগে খুঁজছি, পরে রাখছি, যাতে একই উপাদান নিজের সাথে না মেলে।”
• আটকে গেলে: “এই অংশে একটু আটকেছি — প্রথমে ছোট একটি উদাহরণ হাতে চালিয়ে দেখি।” নীরবতার চেয়ে এটা অনেক ভালো সংকেত।
• শেষে: “সময় গড়ে O(n), মেমরি O(n). খারাপ ক্ষেত্রে hash collision বেশি হলে ধীর হতে পারে।”

৩ · Java-তে ইন্টারভিউর কোড — ঠিক collection আর চেনা ফাঁদ

অ্যালগরিদম যেকোনো ভাষায় একই। কিন্তু Java-তে লিখলে ইন্টারভিউয়ার Java-র নিজস্ব কয়েকটি বিষয়ও খেয়াল করেন: ঠিক collection বাছাই, boxing-এর ফাঁদ, আর আধুনিক Java ব্যবহার। প্রথমে সবচেয়ে কাজের টেবিল — JDK collection-গুলোর মূল কাজের জটিলতা (পর্ব ৩০–৩২):

আটটি অভ্যাস, যা Java-কোডকে “ইন্টারভিউ-মানের” করে

1. Interface দিয়ে ঘোষণা: Map<String, Integer> freq = new HashMap<>(); — পরে TreeMap-এ বদলাতে এক জায়গায় হাত দিলেই চলে (পর্ব ২১)।
2. জোড়া বা ত্রয়ীর জন্য record: record Cell(int r, int c) {} এক লাইনে equals, hashCode, toString দেয় — HashSet-এর key হিসেবেও নিরাপদ। int[] key হিসেবে চলে না, কারণ array-এর equals ঠিকানা তুলনা করে।
3. Integer-এ == নয়: Integer cache-এর কারণে −128 থেকে 127-এ == “কাজ করে”, তার বাইরে করে না (reference equality). Map থেকে আনা মান তুলনায় equals বা int-এ নামিয়ে তুলনা।
4. Overflow আগে ভাবুন: যোগফল, গুণফল, (lo + hi) / 2 — integer overflow চুপচাপ ভুল মান দেয়। long, lo + (hi - lo) / 2, বা Math.addExact/multiplyExact, যা overflow-এ exception ছোড়ে।
5. লুপে String জোড়া নয়: String immutable, তাই লুপে s += x প্রতিবার নতুন String বানায় — মোট O(n²) পর্যন্ত। StringBuilder ব্যবহার করুন (পর্ব ০৮)।
6. Stack নয়, Deque: পুরোনো java.util.Stack Vector-এর ওপর বানানো, প্রতিটি method synchronized; Java-র documentation নিজেই ArrayDeque ব্যবহার করতে বলে। push/pop/peek একই নাম।
7. PriorityQueue-এ Comparator: Java-র PriorityQueue ডিফল্টে min-heap — সবচেয়ে ছোট আগে (C++-এর উল্টো)। বড় আগে চাইলে Comparator.reverseOrder(); record-এ Comparator.comparingInt(Task::priority). (a, b) -> a - b লিখবেন না — বড় মানে বিয়োগ overflow করে; Integer.compare নিরাপদ।
8. Stream না লুপ: গণনা বা রূপান্তরে stream পরিষ্কার; index, আগেভাগে থামা বা জটিল অবস্থা লাগলে সাধারণ লুপ। ইন্টারভিউতে যেটা আপনি নির্ভুল লিখতে ও ব্যাখ্যা করতে পারেন, সেটাই লিখুন (অংশ ৮-এর প্রশ্ন ৪)।

এর কয়েকটি একসাথে চালিয়ে দেখুন — বিশেষ করে Integer-এর তুলনা আর PriorityQueue-এর ক্রম:

import java.util.*;

class Main {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        Integer a = 127, b = 127, c = 1000, d = 1000;
        System.out.println((a == b) + " " + (c == d) + " " + c.equals(d));
        int x = 100_000;
        System.out.println(x * x + " " + (long) x * x);
        try {
            Math.multiplyExact(x, x);
        } catch (ArithmeticException e) {
            System.out.println("caught: " + e.getMessage());
        }
        Deque<Character> stack = new ArrayDeque<>();        // not java.util.Stack
        for (char ch : "abc".toCharArray()) stack.push(ch);
        System.out.println(stack.pop() + " " + stack);

        PriorityQueue<Task> pq = new PriorityQueue<>(
                Comparator.comparingInt(Task::priority).reversed().thenComparing(Task::name));
        pq.add(new Task("deploy", 2));
        pq.add(new Task("bugfix", 5));
        pq.add(new Task("docs", 2));
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) sb.append(pq.poll().name()).append(' ');
        System.out.println(sb.toString().strip());
    }
}

৪ · অ্যারে, স্ট্রিং ও hashing

ইন্টারভিউর প্রথম সারির প্রশ্ন প্রায়ই এই গোত্রের। মূল প্রশ্ন একটাই: “কোন তথ্য মনে রাখলে বারবার খুঁজতে হয় না?” রিভিশনের জন্য: পর্ব ০৮ · String, পর্ব ১৩ · array, পর্ব ৩১ · Set আর Map, পর্ব ৩২ · PriorityQueue.

সমস্যা ২ · পুনরাবৃত্তিহীন দীর্ঘতম substring (মাঝারি)

প্রশ্ন: একটি String-এর এমন দীর্ঘতম টানা অংশের দৈর্ঘ্য বের করুন, যেখানে কোনো অক্ষর দুবার নেই। “abcabcbb” → 3 (“abc”), “pwwkew” → 3 (“wke”).

জিজ্ঞেস করে নিন: substring (টানা অংশ) নাকি subsequence (মাঝে বাদ দেওয়া চলে)? অক্ষর কি শুধু ইংরেজি, নাকি বাংলা বা emoji-ও? খালি String-এ উত্তর 0 তো?

Brute force: প্রতিটি শুরু থেকে যতদূর ডুপ্লিকেট ছাড়া যাওয়া যায় — একটি Set দিয়ে O(n²). উন্নত: sliding window. একটি জানালা [left, right] ডানে বাড়ান; নতুন অক্ষরটি জানালার ভেতরে আগে থাকলে left-কে তার আগের অবস্থানের ঠিক পরে সরান। প্রতিটি অক্ষরের শেষ দেখা index একটি Map-এ রাখুন। সময় O(n), মেমরি O(ভিন্ন অক্ষরের সংখ্যা). নিচে “abba” দিয়ে ধাপে ধাপে দেখুন — এখানে একটি সূক্ষ্ম ফাঁদ আছে:

1int longestUnique(String s) {2  var last = new HashMap<Character, Integer>();3  int best = 0, left = 0;4  for (int right = 0; right < s.length(); right++) {5    char c = s.charAt(right);6    Integer prev = last.get(c);7    if (prev != null) left = Math.max(left, prev + 1);8    last.put(c, right);9    best = Math.max(best, right - left + 1);10  }11  return best;12}

import java.util.*;

class Main {
    static int longestUnique(String s) {
        Map<Character, Integer> last = new HashMap<>();      // char -> last index seen
        int best = 0, left = 0;                               // window = s[left..right]
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            Integer prev = last.get(c);
            if (prev != null) left = Math.max(left, prev + 1); // left never moves back
            last.put(c, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        for (String s : List.of("abcabcbb", "bbbbb", "pwwkew", "", "abba"))
            System.out.println("\"" + s + "\" -> " + longestUnique(s));
    }
}

সমস্যা ৩ · Group anagrams (মাঝারি)

প্রশ্ন: শব্দের একটি তালিকা থেকে anagram-গুলো (একই অক্ষর, ভিন্ন ক্রম) এক দলে রাখুন। [eat, tea, tan, ate, nat, bat] → [eat, tea, ate], [tan, nat], [bat].

জিজ্ঞেস করে নিন: শুধু ছোট হাতের ইংরেজি অক্ষর? দলগুলোর ক্রম কি গুরুত্বপূর্ণ? খালি String থাকতে পারে?

Brute force: প্রতিটি জোড়া শব্দ anagram কি না যাচাই — O(n² · k), k = শব্দের দৈর্ঘ্য। উন্নত: প্রতিটি শব্দের একটি “পরিচয়” বানান — অক্ষরগুলো সাজালে সব anagram-এর পরিচয় একই (“tea” → “aet”). সেই পরিচয়কে key করে Map<String, List<String>>-এ রাখুন। সময় O(n · k log k), মেমরি O(n · k).

import java.util.*;

class Main {
    static Collection<List<String>> groupAnagrams(List<String> words) {
        Map<String, List<String>> groups = new TreeMap<>();   // TreeMap only for a fixed print order
        for (String w : words) {
            char[] cs = w.toCharArray();
            Arrays.sort(cs);                                  // "tea" -> "aet"
            groups.computeIfAbsent(new String(cs), k -> new ArrayList<>()).add(w);
        }
        return groups.values();
    }

    public static void main(String[] args) {
        groupAnagrams(List.of("eat", "tea", "tan", "ate", "nat", "bat"))
                .forEach(System.out::println);
        System.out.println(groupAnagrams(List.of()));
        System.out.println(groupAnagrams(List.of("ab", "ba", "abc")));
    }
}

সমস্যা ৪ · সবচেয়ে বেশি আসা k টি শব্দ (মাঝারি)

প্রশ্ন: শব্দের তালিকা থেকে সবচেয়ে বেশিবার আসা k টি শব্দ, বেশি থেকে কম ক্রমে। সমান হলে বর্ণানুক্রমে আগেরটি আগে।

জিজ্ঞেস করে নিন: সমান গণনায় কী হবে? k কি ভিন্ন শব্দের সংখ্যার চেয়ে বড় হতে পারে? তালিকা কি এত বড় যে মেমরিতে ধরে না?

Brute force: গুনে সব (শব্দ, গণনা) জোড়া সাজানো — O(n + m log m), m = ভিন্ন শব্দ। উন্নত: k আকারের min-heap — heap-এর মাথায় “সবচেয়ে দুর্বল”; আকার k ছাড়ালে মাথা ফেলে দিন। সময় O(n + m log k), মেমরি O(m). আরেক পথ bucket: গণনা কখনো n-এর বেশি নয়, তাই List[n+1]-এ গণনা অনুযায়ী রাখলে O(n) — ফলো-আপে বলুন। এটাই ক্লাসিক top-k ছাঁচ।

import java.util.*;

class Main {
    record WordCount(String word, int count) {}

    static List<String> topK(List<String> words, int k) {
        Map<String, Integer> freq = new HashMap<>();
        for (String w : words) freq.merge(w, 1, Integer::sum);
        // head of the heap = weakest: lower count, or same count but later in A-Z
        Comparator<WordCount> weakestFirst = Comparator.comparingInt(WordCount::count)
                .thenComparing(WordCount::word, Comparator.reverseOrder());
        PriorityQueue<WordCount> heap = new PriorityQueue<>(weakestFirst);
        for (var e : freq.entrySet()) {
            heap.offer(new WordCount(e.getKey(), e.getValue()));
            if (heap.size() > k) heap.poll();                 // keep only the best k
        }
        List<String> result = new ArrayList<>();
        while (!heap.isEmpty()) result.add(heap.poll().word());
        Collections.reverse(result);                          // strongest first
        return result;
    }

    public static void main(String[] args) {
        List<String> words = List.of("java", "go", "java", "python", "go", "java", "rust");
        System.out.println(topK(words, 2));
        System.out.println(topK(words, 3));
        System.out.println(topK(words, 10));
        System.out.println(topK(List.of(), 2));
    }
}

সমস্যা ৫ · সর্বোচ্চ যোগফলের subarray (মাঝারি)

প্রশ্ন: একটি int array-এর টানা অংশগুলোর মধ্যে সর্বোচ্চ যোগফল কত? [−2, 1, −3, 4, −1, 2, 1, −5, 4] → 6 ([4, −1, 2, 1]).

জিজ্ঞেস করে নিন: অন্তত একটি উপাদান নিতেই হবে, নাকি খালি অংশ (যোগফল 0) চলে? সব সংখ্যা ঋণাত্মক হলে উত্তর কী? যোগফল int-এ ধরবে?

Brute force: সব শুরু-শেষ জোড়া, চলমান যোগফলে — O(n²). উন্নত: Kadane’s algorithm. প্রতিটি ঘরে একটাই সিদ্ধান্ত: “আগের অংশটা টেনে নিলে লাভ, নাকি এখান থেকে নতুন শুরু?” আগের যোগফল ঋণাত্মক হলে সেটা বোঝা — ফেলে দিন। সময় O(n), মেমরি O(1). এটি আসলে ছোট একটি dynamic programming: cur = “এই ঘরে শেষ হওয়া সেরা যোগফল”।

static long maxSubarray(int[] a) {          // a.length >= 1 (ask first!)
    long best = a[0], cur = a[0];            // long: the sum may not fit in int
    for (int i = 1; i < a.length; i++) {
        cur = Math.max(a[i], cur + a[i]);    // extend, or start fresh at i
        best = Math.max(best, cur);
    }
    return best;
}

Test ও edge case: উপরের উদাহরণে 6; [−3, −1, −2]-এ −1 (সবচেয়ে কম ঋণাত্মকটি — best শুরু 0 থেকে করলে ভুলভাবে 0 আসত); [5]-এ 5 (চালিয়ে যাচাই করা)। ফলো-আপ: অংশটির শুরু-শেষ index-ও চাই — নতুন শুরুর সময় একটি start মনে রাখুন। গোলাকার (circular) array হলে উত্তর = max(সাধারণ Kadane, মোট যোগফল − সর্বনিম্ন subarray), তবে সব ঋণাত্মক হলে সাবধান।

৫ · Stack, linked list, binary search আর interval

এই গোত্রে দুটি জিনিস একসাথে যাচাই হয়: ঠিক data structure চেনা, আর সীমানায় (প্রথম ঘর, শেষ ঘর, খালি ইনপুট) নির্ভুল থাকা। রিভিশনের জন্য: পর্ব ৩০ · List, পর্ব ৩২ · Queue ও Deque, পর্ব ৩৩ · Comparator, পর্ব ২৫ · record.

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

প্রশ্ন: (), [], {} মেশানো একটি String-এ প্রতিটি খোলা বন্ধনী কি সঠিক ক্রমে সঠিক ধরনের বন্ধনী দিয়ে বন্ধ হয়েছে? “([]{})” → true, “([)]” → false.

জিজ্ঞেস করে নিন: অন্য অক্ষর থাকবে কি (যেমন একটি গাণিতিক রাশি)? থাকলে উপেক্ষা করব তো? খালি String-কে balanced ধরব?

পদ্ধতি ও জটিলতা: শুধু গণনা রাখলে “([)]” ধরা পড়ে না — ক্রম দরকার। সবার শেষে খোলা বন্ধনীটিকেই সবার আগে বন্ধ হতে হয়: এটাই LIFO, তাই stack. খোলা পেলে push, বন্ধ পেলে pop করে মিলিয়ে দেখুন। সময় O(n), মেমরি O(n).

static boolean isBalanced(String s) {
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') stack.push(c);
        else if (pairs.containsKey(c)) {
            if (stack.isEmpty()) return false;           // ")(" : nothing to close
            char open = stack.pop();                     // unbox to char, then compare
            if (open != pairs.get(c)) return false;
        }                                                // other characters: ignore
    }
    return stack.isEmpty();                              // "((" : something left open
}

Test: “([]{})” → true, “([)]” → false, “((” → false, “” → true, “a(b)c” → true, “)(” → false (চালিয়ে যাচাই করা)। Java-র লুকানো ফাঁদ: stack.pop() != pairs.get(c) লিখলে দুটি Character object-এর ঠিকানা তুলনা হয়। ASCII অক্ষর cache থেকে আসে বলে এখানে “কাজ করে” — ঠিক অংশ ৩-এর Integer ফাঁদের মতো, কিন্তু নির্ভরযোগ্য নয়। char-এ নামিয়ে তুলনা করলে নিশ্চিন্ত। ফলো-আপ: শুধু এক ধরনের বন্ধনী হলে stack-ও লাগে না — একটি গণনা যথেষ্ট, যা কখনো ঋণাত্মক হবে না।

সমস্যা ৭ · Linked list উল্টানো (সহজ, কিন্তু খুব জনপ্রিয়)

প্রশ্ন: একটি singly linked list-এর মাথা দেওয়া আছে। নতুন node না বানিয়ে list-টি উল্টে নতুন মাথা ফেরত দিন। 1→2→3→4 → 4→3→2→1.

জিজ্ঞেস করে নিন: নিজের Node class লিখব, নাকি java.util.LinkedList? (প্রায় সবসময় নিজের — LinkedList-এর node বাইরে থেকে ধরা যায় না।) খালি list-এ null ফেরত দেব?

পদ্ধতি ও জটিলতা: brute force: মানগুলো একটি ArrayList-এ তুলে উল্টো ক্রমে লেখা — O(n) বাড়তি মেমরি। উন্নত: তিনটি pointer (prev, cur, next) দিয়ে প্রতিটি তীর উল্টানো — সময় O(n), মেমরি O(1).

class Main {
    static final class Node {                      // mutable: a record could not flip next
        int val; Node next;
        Node(int val, Node next) { this.val = val; this.next = next; }
    }
    static Node reverse(Node head) {
        Node prev = null, cur = head;
        while (cur != null) {
            Node next = cur.next;                  // 1. remember the rest
            cur.next = prev;                       // 2. flip the arrow
            prev = cur;                            // 3. move both one step
            cur = next;
        }
        return prev;                               // old tail is the new head
    }
    static Node of(int... xs) {
        Node head = null;
        for (int i = xs.length - 1; i >= 0; i--) head = new Node(xs[i], head);
        return head;
    }
    static String show(Node h) {
        StringBuilder sb = new StringBuilder("[");
        for (Node n = h; n != null; n = n.next) sb.append(n.val).append(n.next != null ? " -> " : "");
        return sb.append(']').toString();
    }
    public static void main(String[] args) {
        System.out.println(show(reverse(of(1, 2, 3, 4))));
        System.out.println(show(reverse(of(7))) + " " + show(reverse(of())));
    }
}

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

প্রশ্ন: দুটি ছোট-থেকে-বড় সাজানো int[] থেকে একটি সাজানো array বানান। [1, 4, 9] আর [2, 3, 10, 11] → [1, 2, 3, 4, 9, 10, 11].

পদ্ধতি ও জটিলতা: brute force: দুটি জুড়ে Arrays.sort — O((n+m) log(n+m)). উন্নত: two pointers — দুই array-এর সামনের ছোটটি নিন, সেই pointer এগোন। সময় O(n+m). এটাই merge sort-এর merge ধাপ।

static int[] mergeSorted(int[] a, int[] b) {
    int[] out = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length)
        out[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];   // <= keeps equal values stable
    while (i < a.length) out[k++] = a[i++];              // leftovers of a
    while (j < b.length) out[k++] = b[j++];              // leftovers of b
    return out;
}

Edge case ও ফলো-আপ: একটি খালি হলে অন্যটির কপি; শেষের দুটি লুপ ভুলে যাওয়া সবচেয়ে চেনা বাগ। ফলো-আপ: (১) প্রথম array-এর শেষে যথেষ্ট খালি জায়গা আছে, বাড়তি মেমরি ছাড়া জুড়ুন — পেছন থেকে ভরুন, তাহলে কিছু মুছে যায় না। (২) দুটি সাজানো linked list — একই যুক্তি, একটি নকল মাথা (dummy node) রাখলে প্রথম node-এর আলাদা কেস লাগে না। (৩) k টি সাজানো list — PriorityQueue-এ প্রতিটির মাথা রাখুন, O(N log k).

সমস্যা ৯ · সাজানো array-এ একটি মানের প্রথম ও শেষ অবস্থান (মাঝারি)

প্রশ্ন: সাজানো array-এ x প্রথম আর শেষ কোন index-এ আছে? না থাকলে [−1, −1]. [1, 2, 2, 2, 5, 7, 7]-এ 2 → [1, 3].

জিজ্ঞেস করে নিন: array কি সত্যিই সাজানো, আর ছোট থেকে বড়? খালি হতে পারে? প্রত্যাশিত সময় কত — O(log n)?

পদ্ধতি ও জটিলতা: brute force: রৈখিক খোঁজ — O(n), সব মান একই হলে binary search-এ পেয়ে দুপাশে ছড়ালেও O(n). উন্নত: দুবার binary search — “প্রথম যে ঘর ≥ x” আর “প্রথম যে ঘর > x”. দুটিই O(log n). এই দুটি ছাঁচ (lower bound আর upper bound) মুখস্থ নয়, বুঝে রাখুন — অনেক সমস্যা এর ওপর দাঁড়ায়।

import java.util.Arrays;

class Main {
    // first index whose value is >= x (upper=false) or > x (upper=true); a.length if none
    static int bound(int[] a, int x, boolean upper) {
        int lo = 0, hi = a.length;                 // the answer is always in [lo, hi]
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;          // (lo + hi) / 2 can overflow
            boolean goRight = upper ? a[mid] <= x : a[mid] < x;
            if (goRight) lo = mid + 1; else hi = mid;
        }
        return lo;
    }

    static int[] firstAndLast(int[] a, int x) {
        int first = bound(a, x, false);
        if (first == a.length || a[first] != x) return new int[]{-1, -1};
        return new int[]{first, bound(a, x, true) - 1};
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 2, 2, 5, 7, 7};
        for (int x : new int[]{2, 7, 1, 3, 9})
            System.out.println(x + " -> " + Arrays.toString(firstAndLast(a, x)));
        System.out.println(Arrays.toString(firstAndLast(new int[0], 4)));
        System.out.println(Arrays.binarySearch(a, 2) >= 0);   // found, but WHICH 2 is unspecified
    }
}

সমস্যা ১০ · Interval জোড়া লাগানো (মাঝারি)

প্রশ্ন: সময়ের কয়েকটি ব্যবধান (meeting room-এর বুকিংয়ের মতো) দেওয়া আছে। যেগুলো একটি আরেকটির ওপর পড়ে, সেগুলো জুড়ে দিন। [8,10], [1,3], [2,6], [15,18] → [1,6], [8,10], [15,18].

জিজ্ঞেস করে নিন: ইনপুট কি সাজানো? [1,4] আর [4,5] — শুধু ছুঁয়ে থাকলে জুড়ব? মূল তালিকা বদলানো চলবে?

পদ্ধতি ও জটিলতা: brute force: প্রতিটি জোড়া মিলিয়ে বারবার জোড়া — O(n²) বা তার বেশি। উন্নত: শুরুর সময় অনুযায়ী Comparator দিয়ে sort; তারপর একবার পার হয়ে প্রতিটিকে ফলাফলের শেষটির সাথে মেলান — ওভারল্যাপ হলে শেষটি বাড়ান, না হলে নতুন যোগ করুন। সময় O(n log n), মেমরি O(n).

import java.util.*;

class Main {
    record Interval(int start, int end) {
        @Override public String toString() { return "[" + start + "," + end + "]"; }
    }

    static List<Interval> merge(List<Interval> input) {
        List<Interval> sorted = new ArrayList<>(input);          // never modify the caller's list
        sorted.sort(Comparator.comparingInt(Interval::start));
        List<Interval> out = new ArrayList<>();
        for (Interval cur : sorted) {
            if (out.isEmpty() || cur.start() > out.getLast().end()) {
                out.add(cur);                                    // gap: start a new block
            } else {                                             // overlap (touching counts)
                Interval last = out.getLast();
                out.set(out.size() - 1, new Interval(last.start(), Math.max(last.end(), cur.end())));
            }
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(merge(List.of(new Interval(8, 10), new Interval(1, 3),
                new Interval(2, 6), new Interval(15, 18))));
        System.out.println(merge(List.of(new Interval(1, 4), new Interval(4, 5))));
        System.out.println(merge(List.of(new Interval(1, 10), new Interval(2, 3))));
        System.out.println(merge(List.of()));
    }
}

৬ · গ্রাফ আর dynamic programming

পর্ব ৫৪-এ adjacency list-এ BFS, DFS, Dijkstra আর কয়েন দিয়ে টাকা দেওয়ার উপায়ের সংখ্যা দেখেছেন। ইন্টারভিউতে গ্রাফ প্রায়ই লুকিয়ে থাকে একটি গ্রিডে — প্রতিটি ঘর একটি node, পাশের ঘর তার প্রতিবেশী। আর DP আসে “সবচেয়ে কম/বেশি” বা “কয়টি উপায়” প্রশ্নে। রিভিশনের জন্য: পর্ব ৫৪ · অ্যালগরিদম ও কনটেস্টে Java, পর্ব ৩২ · Queue, পর্ব ১২ · recursion.

সমস্যা ১১ · গ্রিডে S থেকে E-তে সবচেয়ে ছোট পথ (মাঝারি)

প্রশ্ন: একটি গ্রিডে S শুরু, E গন্তব্য, # দেয়াল, . খালি ঘর। উপর-নিচ-ডান-বামে এক ধাপে এক ঘর যাওয়া যায়। সবচেয়ে কম কয় ধাপে E-তে পৌঁছানো যায়? না গেলে −1.

জিজ্ঞেস করে নিন: কোনাকুনি যাওয়া চলে? প্রতিটি ধাপের খরচ কি সমান? গ্রিড কত বড়? S কি সবসময় আছে?

পদ্ধতি ও জটিলতা: brute force: সব পথ DFS দিয়ে খুঁজে ছোটটি — পথের সংখ্যা সূচকীয় হারে বাড়ে। উন্নত: BFS. queue থেকে ঘরগুলো দূরত্বের ক্রমে বের হয় — আগে সব ১-ধাপের ঘর, তারপর সব ২-ধাপের — তাই সমান খরচের ধাপে প্রথম যখন E পাই, সেটাই সবচেয়ে ছোট। সময় ও মেমরি O(R × C). এখানে S-এর অবস্থান parameter হিসেবে দেওয়া হলো, যাতে কোড ছোট থাকে।

import java.util.*;

class Main {
    record Cell(int r, int c) {}
    static int shortestPath(String[] grid, Cell start) {
        int rows = grid.length, cols = grid[0].length();
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) Arrays.fill(row, -1);              // -1 = not visited yet
        Deque<Cell> queue = new ArrayDeque<>();
        dist[start.r()][start.c()] = 0; queue.add(start);
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            Cell cur = queue.poll();
            if (grid[cur.r()].charAt(cur.c()) == 'E') return dist[cur.r()][cur.c()];
            for (int[] d : dirs) {
                int nr = cur.r() + d[0], nc = cur.c() + d[1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (grid[nr].charAt(nc) == '#' || dist[nr][nc] != -1) continue;
                dist[nr][nc] = dist[cur.r()][cur.c()] + 1;        // mark when added, not when taken
                queue.add(new Cell(nr, nc));
            }
        }
        return -1;                                                // E not reachable
    }
    public static void main(String[] args) {
        Cell s = new Cell(0, 0);                                  // S is at the top-left in these tests
        System.out.println(shortestPath(new String[]{"S.#.", "..#E", "...."}, s));
        System.out.println(shortestPath(new String[]{"S#E"}, s) + " " + shortestPath(new String[]{"SE"}, s));
    }
}

সমস্যা ১২ · দ্বীপের সংখ্যা (মাঝারি)

প্রশ্ন: '1' (মাটি) আর '0' (পানি)-র একটি গ্রিডে কয়টি দ্বীপ? উপর-নিচ-ডান-বামে লাগোয়া মাটি একই দ্বীপ।

জিজ্ঞেস করে নিন: কোনাকুনি লাগোয়া কি একই দ্বীপ? ইনপুট গ্রিড বদলানো চলবে, নাকি আলাদা visited রাখব?

পদ্ধতি ও জটিলতা: প্রতিটি ঘর দেখুন; একটি না-দেখা মাটি পেলে গণনা এক বাড়ান, আর DFS দিয়ে পুরো দ্বীপটা “ডুবিয়ে” দিন (০ করে দিন), যাতে আবার গোনা না হয়। প্রতিটি ঘর সর্বোচ্চ একবার ডোবে — সময় O(R × C). recursive DFS সুন্দর, কিন্তু ১০০০ × ১০০০ মাটির গ্রিডে গভীরতা দশ লাখ হতে পারে; তাই নিজের ArrayDeque stack:

static int countIslands(char[][] g) {               // modifies g: ask first!
    int rows = g.length, cols = g[0].length, islands = 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    Deque<int[]> stack = new ArrayDeque<>();
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) {
            if (g[r][c] != '1') continue;
            islands++;
            g[r][c] = '0';                            // sink when pushed
            stack.push(new int[]{r, c});
            while (!stack.isEmpty()) {
                int[] p = stack.pop();
                for (int[] d : dirs) {
                    int nr = p[0] + d[0], nc = p[1] + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && g[nr][nc] == '1') {
                        g[nr][nc] = '0';
                        stack.push(new int[]{nr, nc});
                    }
                }
            }
        }
    return islands;
}

Test: “11000 / 11000 / 00100 / 00011” → 3 (চালিয়ে যাচাই করা); সব পানি → 0; সব মাটি → 1. ফলো-আপ: সবচেয়ে বড় দ্বীপের আয়তন; একটি একটি করে মাটি যোগ হচ্ছে আর প্রতিবার দ্বীপ গুনতে হবে — তখন Union-Find (disjoint set) নিয়ে আলোচনা। একই ছাঁচে আসে directed গ্রাফে চক্র খোঁজা: DFS-এ তিন রং (না-দেখা, পথে আছে, শেষ) — “পথে আছে” এমন node-এ আবার পৌঁছালে চক্র। এর আরেক রূপ course prerequisite বা build order, যা পর্ব ৪৬-এর Gradle-এর task DAG-এর সাথে মেলে।

সমস্যা ১৩ · সিঁড়ি বেয়ে ওঠা আর সবচেয়ে কম কয়েন (সহজ → মাঝারি)

প্রশ্ন ক: n ধাপের সিঁড়ি, একবারে ১ বা ২ ধাপ ওঠা যায়। কত ভাবে ওপরে ওঠা যায়? প্রশ্ন খ: কয়েনের মান দেওয়া (প্রতিটি অসীম সংখ্যক), একটি টাকার অঙ্ক বানাতে সবচেয়ে কম কয়টি কয়েন লাগে? না গেলে −1.

জিজ্ঞেস করে নিন: n বা অঙ্ক কত বড়? উত্তর কি int-এ ধরবে? অঙ্ক 0 হলে উত্তর 0 তো?

পদ্ধতি ও জটিলতা: ক-এর brute force recursion ways(n) = ways(n-1) + ways(n-2) — একই উপ-সমস্যা বারবার, O(2ⁿ)-এর কাছাকাছি। Memoization বা নিচ থেকে ওপরে হিসাব করলে O(n), আর শুধু শেষ দুটি মান রাখলে মেমরি O(1). খ-তে লোভী পদ্ধতি (সবসময় বড় কয়েন আগে) সব কয়েন-সেটে ঠিক নয় — তাই dp[x] = x বানাতে সবচেয়ে কম কয়েন; প্রতিটি x-এর জন্য প্রতিটি কয়েন চেষ্টা। সময় O(অঙ্ক × কয়েনের সংখ্যা).

import java.util.Arrays;

class Main {
    // ways to climb n stairs taking 1 or 2 steps at a time
    static long climbWays(int n) {
        long a = 1, b = 1;                          // ways(0), ways(1)
        for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
        return b;
    }

    // fewest coins that make 'amount' (unlimited supply); -1 if impossible
    static int minCoins(int[] coins, int amount) {
        final int INF = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];             // dp[x] = fewest coins for x
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int x = 1; x <= amount; x++)
            for (int coin : coins)
                if (coin <= x && dp[x - coin] != INF)   // guard: INF + 1 would overflow
                    dp[x] = Math.min(dp[x], dp[x - coin] + 1);
        return dp[amount] == INF ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(climbWays(1) + " " + climbWays(5) + " " + climbWays(50));
        System.out.println(minCoins(new int[]{1, 2, 5}, 11) + " " + minCoins(new int[]{2}, 3));
        System.out.println(minCoins(new int[]{1, 3, 4}, 6) + " " + minCoins(new int[]{7}, 0));
    }
}

৭ · ডিজাইনের প্রশ্ন — LRU cache, concurrency আর OOP

Java পদের ইন্টারভিউতে প্রায়ই এমন প্রশ্ন আসে, যেখানে অ্যালগরিদমের চেয়ে ঠিক কাঠামো বাছা আর ভাষার জ্ঞান বড়: একটি cache, একটি thread-safe কাঠামো, বা কয়েকটি class দিয়ে একটি ছোট সিস্টেমের নকশা। রিভিশনের জন্য: পর্ব ৩১, পর্ব ৪০ · thread, পর্ব ৪১ · Executor, পর্ব ২৬ · sealed, পর্ব ৪৮ · design pattern.

সমস্যা ১৪ · LRU cache — get আর put দুটোই O(1) (মাঝারি → কঠিন)

প্রশ্ন: নির্দিষ্ট ধারণক্ষমতার একটি cache বানান। ভরে গেলে সবচেয়ে আগে ব্যবহৃত (least recently used) key বাদ যাবে। get আর put দুটোই O(1).

জিজ্ঞেস করে নিন: put দিয়ে মান বদলালে কি সেটাও “ব্যবহার”? key না থাকলে get কী দেবে? একাধিক thread থেকে ব্যবহার হবে? JDK-র class ব্যবহার করা চলবে, নাকি নিজে বানাতে হবে?

পদ্ধতি: দুটি চাহিদা — key দিয়ে দ্রুত খোঁজা (HashMap) আর ব্যবহারের ক্রম রাখা, যেখানে মাঝখান থেকে একটি উপাদান তুলে সামনে আনা যায় (doubly linked list). Java-তে দুটো একসাথেই আছে: LinkedHashMap-এর access order মোড আর removeEldestEntry hook. প্রথমে এটা বলুন — তারপর ইন্টারভিউয়ার সাধারণত বলেন, “এবার নিজে বানান।”

import java.util.*;

class Main {
    static final class LruCache<K, V> extends LinkedHashMap<K, V> {
        private final int capacity;

        LruCache(int capacity) {
            super(16, 0.75f, true);                 // true = access order, not insertion order
            this.capacity = capacity;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity;               // drop the least recently used
        }
    }

    public static void main(String[] args) {
        LruCache<String, Integer> cache = new LruCache<>(2);
        cache.put("a", 1);
        cache.put("b", 2);
        cache.get("a");                             // "a" becomes most recent
        cache.put("c", 3);                          // full: evicts "b"
        System.out.println(cache + " " + cache.get("b"));
        cache.put("a", 10);                         // an update is also a use
        cache.put("d", 4);                          // evicts "c"
        System.out.println(cache);
    }
}

“নিজে বানান” বললে: HashMap<Integer, Node> + নিজের doubly linked list, দুই প্রান্তে দুটি নকল (sentinel) node, যাতে খালি list বা প্রথম/শেষ node-এর আলাদা কেস না লাগে:

final class LruCache {
    private static final class Node {
        int key, value; Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0), tail = new Node(0, 0);   // sentinels

    LruCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; }

    int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        unlink(n); addFront(n);                       // most recent goes to the front
        return n.value;
    }
    void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) { n.value = value; unlink(n); addFront(n); return; }
        if (map.size() == capacity) {                 // evict from the back
            Node lru = tail.prev;
            unlink(lru); map.remove(lru.key);         // that is why Node stores its key
        }
        n = new Node(key, value);
        map.put(key, n); addFront(n);
    }
    private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void addFront(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
}

Test: ধারণক্ষমতা ২; put(1,1), put(2,2), get(1) → 1, put(3,3) [2 বাদ], get(2) → −1, put(4,4) [1 বাদ], get(1) → −1, get(3) → 3, get(4) → 4 (চালিয়ে যাচাই করা)। প্রতিটি কাজে কয়েকটি pointer বদল আর একটি HashMap কাজ — গড়ে O(1). ইন্টারভিউয়ার প্রায়ই জিজ্ঞেস করেন, “Node-এ key কেন রাখলেন?” — উত্তর: পেছন থেকে বাদ দেওয়ার সময় map থেকেও মুছতে হয়, আর তখন key ছাড়া উপায় নেই। ধারণক্ষমতা 0 হলে কী হবে — সেটাও জিজ্ঞেস করে নিন।

সমস্যা ১৫ · Thread-safe counter আর producer-consumer (মাঝারি → কঠিন)

প্রশ্ন: (ক) চারটি thread একটি counter দশ হাজার বার করে বাড়ায় — শেষে যেন ঠিক ৪০০০০ হয়। (খ) একটি thread কাজ বানায়, আরেকটি খায়; মাঝের queue-এর আকার সীমিত — ভরে গেলে উৎপাদক অপেক্ষা করবে, খালি হলে ভোক্তা।

আলোচনা (এখানেই আসল নম্বর): count++ একটি কাজ নয়, তিনটি — পড়া, যোগ, লেখা (read-modify-write). দুটি thread একসাথে ৫ পড়লে দুজনেই ৬ লেখে — একটি বৃদ্ধি হারায়; এটাই race condition (পর্ব ৪০)। volatile দৃশ্যমানতা দেয়, কিন্তু তিন ধাপকে অবিভাজ্য করে না — তাই যথেষ্ট নয়। সমাধান তিনটি: synchronized method (সহজ, একটি তালা), AtomicInteger (তালা ছাড়া, CPU-র compare-and-swap দিয়ে), আর অনেক thread খুব ঘন ঘন বাড়ালে LongAdder. (খ)-এর জন্য নিজে wait/notify লেখা যায়, কিন্তু ভুল করা সহজ (spurious wakeup-এর জন্য while, notifyAll…); JDK-র BlockingQueue ঠিক এই কাজের জন্যই বানানো।

import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

class Main {
    public static void main(String[] args) throws InterruptedException {
        // 1) thread-safe counter: 4 tasks x 10_000 increments
        AtomicInteger counter = new AtomicInteger();
        try (ExecutorService pool = Executors.newFixedThreadPool(4)) {
            for (int t = 0; t < 4; t++)
                pool.submit(() -> { for (int i = 0; i < 10_000; i++) counter.incrementAndGet(); });
        }                                           // close() waits for every task (Java 19+)
        System.out.println("counter = " + counter.get());

        // 2) producer-consumer through a bounded queue
        BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(3);
        final int poison = -1;                      // "no more items" signal
        Thread producer = Thread.ofPlatform().start(() -> {
            try {
                for (int i = 1; i <= 10; i++) queue.put(i);   // waits while the queue is full
                queue.put(poison);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });
        long sum = 0;
        for (int x = queue.take(); x != poison; x = queue.take()) sum += x;  // waits while empty
        producer.join();
        System.out.println("sum = " + sum);
    }
}

সমস্যা ১৬ · একটি মোবাইল ওয়ালেটের OOP ডিজাইন (মাঝারি)

প্রশ্ন: “bKash বা Nagad-এর মতো একটি সরল মোবাইল ওয়ালেটের মূল class-গুলো সাজান: টাকা জমা, তোলা, অন্যকে পাঠানো, লেনদেনের ইতিহাস।” এখানে পুরো কোড নয় — কাঠামো আর সিদ্ধান্তের যুক্তি দেখা হয়। একই ধাঁচের প্রশ্ন: parking lot, লাইব্রেরি, টিকিট বুকিং।

জিজ্ঞেস করে নিন: একাধিক মুদ্রা? ব্যালান্স কি ঋণাত্মক হতে পারে? একই অনুরোধ দুবার এলে (নেটওয়ার্ক retry) কী হবে? ইতিহাস কি বদলানো যাবে?

পদ্ধতি — বিশেষ্য থেকে class, ক্রিয়া থেকে method (পর্ব ০২): ওয়ালেট, লেনদেন, ব্যবহারকারী, সেবা। নিচের স্কেচে মূল সিদ্ধান্তগুলো মন্তব্যে:

sealed interface Transaction permits Deposit, Withdrawal, Transfer {}   // closed set of kinds
record Deposit(BigDecimal amount, Instant at) implements Transaction {}
record Withdrawal(BigDecimal amount, Instant at) implements Transaction {}
record Transfer(String toWalletId, BigDecimal amount, Instant at) implements Transaction {}

final class Wallet {
    private final String id;
    private BigDecimal balance = BigDecimal.ZERO;          // money: never double
    private final List<Transaction> history = new ArrayList<>();

    Wallet(String id) { this.id = id; }

    synchronized void withdraw(BigDecimal amount, Instant at) {
        if (amount.signum() <= 0) throw new IllegalArgumentException("amount must be > 0");
        if (balance.compareTo(amount) < 0)                // compareTo, not equals, for BigDecimal
            throw new InsufficientFundsException("wallet " + id + ": balance too low");
        balance = balance.subtract(amount);
        history.add(new Withdrawal(amount, at));
    }
    synchronized List<Transaction> history() { return List.copyOf(history); }  // no outside edits
    // deposit(...) is similar
}

interface WalletRepository { Optional<Wallet> findById(String id); void save(Wallet w); }

final class TransferService {                              // business rule lives here
    private final WalletRepository repo;                   // injected: easy to fake in tests
    TransferService(WalletRepository repo) { this.repo = repo; }
    // transfer(from, to, amount, requestId):
    //  - lock both wallets in a fixed order (by id) to avoid deadlock
    //  - remember requestId so a retried request is not applied twice
}

String describe(Transaction t) {                          // exhaustive: no default needed
    return switch (t) {
        case Deposit d     -> "+" + d.amount();
        case Withdrawal w  -> "-" + w.amount();
        case Transfer tr   -> "-> " + tr.toWalletId() + " " + tr.amount();
    };
}

যে সিদ্ধান্তগুলো মুখে বলবেন: (১) টাকায় BigDecimal, কারণ double-এ 0.1 + 0.2 ঠিক 0.3 নয় (পর্ব ০৬)। (২) লেনদেনের ধরন সীমিত ও জানা — তাই sealed interface আর record; নতুন ধরন যোগ হলে প্রতিটি switch-এ compiler নিজেই মনে করিয়ে দেবে (পর্ব ২৬)। (৩) ব্যালান্স বাইরে থেকে সরাসরি বদলানো যায় না — encapsulation; ইতিহাস ফেরত যায় অপরিবর্তনীয় কপি হিসেবে। (৪) দুটি ওয়ালেটের মধ্যে পাঠাতে দুটি তালা লাগে; সবসময় id-এর ক্রমে তালা নিলে deadlock এড়ানো যায় (lock ordering, পর্ব ৪০)। (৫) একই requestId দুবার এলে একবারই কার্যকর — idempotency (পর্ব ৫১)। (৬) সত্যিকারের সিস্টেমে ব্যালান্স থাকে ডেটাবেসে, আর transaction দিয়ে দুই দিক একসাথে বদলায় (পর্ব ৪৯)। স্কেচের মূল অংশ (জমা, তোলা, অপর্যাপ্ত ব্যালান্সের exception, ইতিহাসের switch) আলাদা করে চালিয়ে যাচাই করা হয়েছে।

৮ · ভাবনার প্রশ্ন — ইন্টারভিউর বড় আলোচনা

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

৯ · AI দিয়ে প্রস্তুতি — mock interview, নিয়ম আর যাচাই

প্রস্তুতির সময় অবশ্য AI হতে পারে চমৎকার mock interview-এর সঙ্গী আর code review-এর সাহায্যকারী — শর্ত একটাই: উত্তর নয়, প্রশ্ন আর মূল্যায়ন চাইবেন। সমাধান সরাসরি চাইলে আপনি পড়ে “বুঝলাম” ভাববেন, কিন্তু নিজে বের করার পেশিটা তৈরি হবে না। নিচের prompt দিয়ে একটি পূর্ণ mock interview চালান:

নিজের লেখা সমাধান যাচাই করাতে আলাদা prompt দিন: “এই Java সমাধানের বাগ, বাদ পড়া edge case আর জটিলতার ভুল খুঁজে দাও; ঠিক করা কোড লিখবে না, শুধু কোন লাইনে কী সমস্যা বলবে।” এতে ঠিক করার কাজটা আপনার হাতেই থাকে। আর AI কোনো সমাধান দিলে সেটা test দিয়ে যাচাই করুন: একটি সরল brute force লিখে দুটির ফল হাজারখানেক এলোমেলো ছোট ইনপুটে মিলিয়ে দেখুন — একে বলে stress testing (পর্ব ৫৪)। brute force ধীর কিন্তু সহজে ঠিক লেখা যায়, তাই সে-ই বিচারক।

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

• সমাধান দেখার আগে নিজে অন্তত ২০ মিনিট চেষ্টা করেছি, আর খাতায় পদ্ধতি লিখেছি
• AI-এর বলা জটিলতা নিজে হিসাব করে মিলিয়েছি — AI প্রায়ই “গড়ে” আর “খারাপ ক্ষেত্রে” গুলিয়ে ফেলে
• AI-এর Java কোড চালিয়ে নিজের edge case দিয়েছি: খালি, এক উপাদান, ডুপ্লিকেট, ঋণাত্মক, সর্বোচ্চ মান
• Integer-এ ==, int overflow, HashMap-এর ক্রমের ওপর নির্ভরতা, বা immutable List বদলানোর চেষ্টা আছে কি না নিজে খুঁজেছি
• একটি brute force দিয়ে এলোমেলো ইনপুটে ফল মিলিয়েছি
• একদিন পরে AI ছাড়া একই সমস্যা আবার শূন্য থেকে সমাধান করতে পেরেছি, আর পাঁচ মিনিটে জোরে ব্যাখ্যা করতে পারি

নিজের প্রজেক্ট কীভাবে ব্যাখ্যা করবেন

“আপনার একটি প্রজেক্টের কথা বলুন” — প্রায় নিশ্চিত প্রশ্ন। পর্ব ৫৫-এর ক্যাপস্টোন বা পর্ব ২২-এর CLI টুল এখানে আপনার বড় সম্পদ। পাঁচ মিনিটের কাঠামো: সমস্যা ও ব্যবহারকারী (৩০ সেকেন্ড) → প্রধান class/layer আর ডেটার পথ (১ মিনিট) → দুটি সিদ্ধান্ত ও তার trade-off, যেমন “TreeMap নিয়েছি কারণ রিপোর্টে সাজানো ক্রম লাগত” (২ মিনিট) → একটি কঠিন বাগ ও কীভাবে খুঁজলেন (১ মিনিট) → আরও সময় পেলে কী বদলাতেন (৩০ সেকেন্ড)। যে অংশ টিউটোরিয়াল, বন্ধু বা AI-এর সাহায্যে লিখেছেন, তা লুকাবেন না — বলুন কোন অংশ নিজে বুঝে বদলেছেন। যে কোড আপনি ব্যাখ্যা করতে পারেন না, তা আপনার পক্ষে নয়, বিপক্ষে কাজ করে।

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

এটি ৮টি মডিউল আর ৫৯টি পর্বের এই কোর্সের শেষ পর্ব। একবার পেছনে তাকান। পর্ব ১-এ প্রশ্ন ছিল, “Java কেন?” পর্ব ৪-এ প্রথম println লিখেছিলেন, পর্ব ৫-এ দেখেছিলেন JVM কীভাবে bytecode চালায়। আজ আপনি একটি LRU cache-এর জন্য ঠিক collection বাছতে পারেন, count++ কেন thread-safe নয় বোঝাতে পারেন, আর একটি অচেনা সমস্যাকে সাত ধাপে ভেঙে সমাধান করতে পারেন। আন্তরিক অভিনন্দন — এটা সত্যিই বড় অর্জন।

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

• ভিত্তি ও মূল ভাষা (পর্ব ০১–১৪): object দিয়ে সমস্যা ভাঙা, JDK আর JVM-এর ভেতরের ছবি, টাইপ, String, লুপ, method, array আর regular expression দিয়ে নির্ভুল প্রোগ্রাম লেখা।
• OOP (পর্ব ১৫–২২): class, constructor, encapsulation, inheritance, polymorphism আর interface দিয়ে নিজের টাইপ নকশা করা।
• আধুনিক টাইপ (পর্ব ২৩–২৯): equals/hashCode, enum, record, sealed আর pattern matching, generics আর exception ঠিকভাবে ব্যবহার করা।
• Collections ও functional Java (পর্ব ৩০–৩৬): ঠিক collection বাছা, Comparator, lambda, Stream আর Optional দিয়ে পরিষ্কার কোড।
• সিস্টেম ও JVM (পর্ব ৩৭–৪৫): ফাইল, তারিখ-সময়, JSON, thread, Executor, virtual thread, নেটওয়ার্কিং, GC আর reflection — প্রোগ্রামের নিচের স্তর বোঝা।
• পেশাদার Java (পর্ব ৪৬–৫৫): Maven/Gradle, JUnit, design pattern, JDBC, Spring Boot-এ REST API, JPA/Hibernate, Spring Security, অ্যালগরিদম আর একটি পূর্ণ ক্যাপস্টোন — আর AI-এর লেখা Java কোড যাচাই করা।

পরীক্ষা ও সার্টিফিকেট

লগইন করলে ড্যাশবোর্ডে শেখার সাতটি মডিউলের (পর্ব ০১–৫৫) প্রতিটির একটি টেস্ট আর একটি ফাইনাল পরীক্ষা পাবেন। শেখার এই সব পর্ব (০১–৫৫) পড়া শেষ করে ফাইনালে ৬০% বা তার বেশি পেলে একটি ফ্রি কোর্স-সমাপ্তির সার্টিফিকেট পাবেন। প্রতিটি পর্বের “পড়েছি” বোতাম চাপা থাকলে আপনার অগ্রগতি সেখানে দেখা যাবে — অগ্রগতি সেভ হয় শুধু লগইন করা অবস্থায়। পরীক্ষার আগে পর্ব ৫৬–৫৮-এর প্রশ্নব্যাংক একবার ঘুরে আসুন।

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

• প্রতিদিন অল্প: দিনে একটি সমস্যা, পুরো সাত ধাপে — সপ্তাহে একদিন বড় সেশনের চেয়ে বেশি কাজে দেয়। LeetCode, HackerRank, Codeforces আর বাংলাদেশে জনপ্রিয় Toph-এর মতো প্ল্যাটফর্মে এ ধরনের অনেক সমস্যা পাবেন।
• একটি ভুলের খাতা: প্রতিটি ভুলের পর তিন লাইন — কোন ধারণা মিস করেছিলাম, কোন edge case ভুলেছিলাম, পরেরবার কোন সংকেত দেখে চিনব।
• ক্যাপস্টোন বড় করুন: নতুন একটি feature, আরও test, একটি পরিষ্কার README — GitHub-এ রাখলে portfolio নিজে থেকেই বড় হয়।
• বন্ধুর সাথে mock interview: একজন প্রশ্ন করবেন, অন্যজন সমাধান করবেন, তারপর ভূমিকা বদল — মানুষের সামনে কথা বলার অভ্যাস AI-এর চেয়েও কাজে দেয়।
• মাঝে মাঝে ফিরে আসুন: কোর্স হোম থেকে যে পর্ব দুর্বল লাগে সেটি আবার পড়ুন।

এরপর কোন পথে