ভূমিকা

এই পোস্টে আমরা HashMap সম্পর্কিত ৫টি মিডিয়াম লেভেলের কোডিং সমস্যা দেখব এবং Java ব্যবহার করে সেগুলোর বিস্তারিত সমাধান করব। HashMap হলো Java-এর সবচেয়ে গুরুত্বপূর্ণ data structure গুলোর একটি, যা key-value pair সংরক্ষণ করে O(1) সময়ে।

সমস্যা ১: Two Sum (দুটি সংখ্যার যোগফল)

সমস্যার বিবরণ

একটি integer array nums এবং একটি target সংখ্যা দেওয়া আছে। Array-এর এমন দুটি সংখ্যার index খুঁজে বের করতে হবে যাদের যোগফল target-এর সমান। একই element দুইবার ব্যবহার করা যাবে না।

উদাহরণ:

• Input: nums = [2, 7, 11, 15], target = 9
• Output: [0, 1]
• কারণ: nums[0] + nums[1] = 2 + 7 = 9

চিন্তার পদ্ধতি

HashMap ব্যবহার করে প্রতিটি element-এর জন্য complement = target - nums[i] বের করব। যদি এই complement HashMap-এ আগে থেকে থাকে, তাহলে উত্তর পেয়ে গেছি। এটি O(n) সময়ে কাজ করে, Brute Force-এর O(n²) এর চেয়ে অনেক ভালো।

সমাধান (Java)

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        // number -> index সংরক্ষণের জন্য HashMap
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            // complement আগে দেখা গিয়েছে কিনা চেক করি
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }

            // বর্তমান number HashMap-এ রাখি
            map.put(nums[i], i);
        }

        return new int[]{}; // কোনো সমাধান না থাকলে
    }

    public static void main(String[] args) {
        TwoSum solution = new TwoSum();

        int[] result1 = solution.twoSum(new int[]{2, 7, 11, 15}, 9);
        System.out.println("[" + result1[0] + ", " + result1[1] + "]"); // [0, 1]

        int[] result2 = solution.twoSum(new int[]{3, 2, 4}, 6);
        System.out.println("[" + result2[0] + ", " + result2[1] + "]"); // [1, 2]
    }
}

সময় জটিলতা: O(n) | স্থান জটিলতা: O(n)

---

সমস্যা ২: Subarray Sum Equals K

সমস্যার বিবরণ

একটি integer array nums এবং একটি integer k দেওয়া আছে। এমন সব contiguous subarray-এর সংখ্যা বের করতে হবে যাদের যোগফল k-এর সমান।

উদাহরণ:

• Input: nums = [1, 1, 1], k = 2
• Output: 2
• কারণ: [1,1] দুইবার পাওয়া যায় — index (0,1) এবং (1,2)
• Input: nums = [1, 2, 3], k = 3
• Output: 2
• কারণ: [1,2] এবং [3] — দুটি subarray যাদের যোগফল 3

চিন্তার পদ্ধতি

Prefix Sum এবং HashMap ব্যবহার করব। যদি prefixSum[j] - prefixSum[i] = k হয়, তাহলে index i থেকে j পর্যন্ত subarray-এর যোগফল k। HashMap-এ প্রতিটি prefix sum কতবার দেখা গেছে তা সংরক্ষণ করব।

সমাধান (Java)

import java.util.HashMap;
import java.util.Map;

public class SubarraySumEqualsK {
    public int subarraySum(int[] nums, int k) {
        // prefixSum -> কতবার দেখা গেছে
        Map<Integer, Integer> prefixCount = new HashMap<>();
        prefixCount.put(0, 1); // শূন্য যোগফলের জন্য base case

        int count = 0;
        int currentSum = 0;

        for (int num : nums) {
            currentSum += num;

            // (currentSum - k) আগে কতবার দেখা গিয়েছে?
            int needed = currentSum - k;
            if (prefixCount.containsKey(needed)) {
                count += prefixCount.get(needed);
            }

            // বর্তমান prefix sum HashMap-এ আপডেট করি
            prefixCount.put(currentSum, prefixCount.getOrDefault(currentSum, 0) + 1);
        }

        return count;
    }

    public static void main(String[] args) {
        SubarraySumEqualsK solution = new SubarraySumEqualsK();
        System.out.println(solution.subarraySum(new int[]{1, 1, 1}, 2)); // Output: 2
        System.out.println(solution.subarraySum(new int[]{1, 2, 3}, 3)); // Output: 2
        System.out.println(solution.subarraySum(new int[]{-1, -1, 1}, 0)); // Output: 1
    }
}

সময় জটিলতা: O(n) | স্থান জটিলতা: O(n)

---

সমস্যা ৩: Longest Consecutive Sequence

সমস্যার বিবরণ

একটি unsorted integer array nums দেওয়া আছে। সবচেয়ে দীর্ঘ consecutive elements-এর sequence-এর দৈর্ঘ্য বের করতে হবে। Algorithm-এর সময় জটিলতা O(n) হতে হবে।

উদাহরণ:

• Input: nums = [100, 4, 200, 1, 3, 2]
• Output: 4
• কারণ: [1, 2, 3, 4] হলো সবচেয়ে দীর্ঘ consecutive sequence
• Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
• Output: 9

চিন্তার পদ্ধতি

সব numbers একটি HashSet-এ রাখব। তারপর প্রতিটি number-এর জন্য check করব সে কোনো sequence-এর শুরু কিনা (num - 1 HashSet-এ নেই)। যদি শুরু হয়, তাহলে সেখান থেকে সামনে গিয়ে sequence-এর দৈর্ঘ্য বের করব।

সমাধান (Java)

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LongestConsecutiveSequence {
    public int longestConsecutive(int[] nums) {
        // সব numbers HashSet-এ রাখি O(1) lookup-এর জন্য
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int maxLength = 0;

        for (int num : numSet) {
            // শুধু sequence-এর শুরুতে থাকা number-গুলো process করি
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;

                // সামনে যতদূর consecutive আছে যাই
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }

                maxLength = Math.max(maxLength, currentLength);
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestConsecutiveSequence solution = new LongestConsecutiveSequence();
        System.out.println(solution.longestConsecutive(new int[]{100, 4, 200, 1, 3, 2})); // Output: 4
        System.out.println(solution.longestConsecutive(new int[]{0, 3, 7, 2, 5, 8, 4, 6, 0, 1})); // Output: 9
        System.out.println(solution.longestConsecutive(new int[]{})); // Output: 0
    }
}

সময় জটিলতা: O(n) | স্থান জটিলতা: O(n)

---

সমস্যা ৪: Top K Frequent Elements

সমস্যার বিবরণ

একটি integer array nums এবং একটি integer k দেওয়া আছে। Array-এ সবচেয়ে বেশিবার আসা kটি element বের করতে হবে। উত্তর যেকোনো ক্রমে দেওয়া যাবে।

উদাহরণ:

• Input: nums = [1, 1, 1, 2, 2, 3], k = 2
• Output: [1, 2]
• কারণ: 1 তিনবার এবং 2 দুইবার এসেছে — এরা top 2
• Input: nums = [1], k = 1
• Output: [1]

চিন্তার পদ্ধতি

প্রথমে HashMap দিয়ে প্রতিটি element-এর frequency count করব। তারপর Bucket Sort ব্যবহার করব — index হলো frequency, value হলো সেই frequency-র elements। এটি O(n) সময়ে কাজ করে।

সমাধান (Java)

import java.util.*;

public class TopKFrequentElements {
    public int[] topKFrequent(int[] nums, int k) {
        // Step 1: প্রতিটি element-এর frequency বের করি
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Bucket sort — index = frequency
        List<Integer>[] buckets = new List[nums.length + 1];
        for (int key : freqMap.keySet()) {
            int freq = freqMap.get(key);
            if (buckets[freq] == null) {
                buckets[freq] = new ArrayList<>();
            }
            buckets[freq].add(key);
        }

        // Step 3: সবচেয়ে বেশি frequent k টি element collect করি
        int[] result = new int[k];
        int idx = 0;
        for (int i = buckets.length - 1; i >= 0 && idx < k; i--) {
            if (buckets[i] != null) {
                for (int num : buckets[i]) {
                    if (idx < k) {
                        result[idx++] = num;
                    }
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        TopKFrequentElements solution = new TopKFrequentElements();

        int[] result1 = solution.topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2);
        System.out.println(Arrays.toString(result1)); // Output: [1, 2]

        int[] result2 = solution.topKFrequent(new int[]{1}, 1);
        System.out.println(Arrays.toString(result2)); // Output: [1]
    }
}

সময় জটিলতা: O(n) | স্থান জটিলতা: O(n)

---

সমস্যা ৫: LRU Cache Implementation

সমস্যার বিবরণ

একটি LRU (Least Recently Used) Cache implement করতে হবে যেটি capacity অনুযায়ী কাজ করে। Cache-টি দুটি operation support করবে:

• get(key): key যদি cache-এ থাকে তাহলে value return করে, না থাকলে -1 return করে।
• put(key, value): key-value pair cache-এ রাখে। Cache পূর্ণ হলে সবচেয়ে কম recently used item সরিয়ে দেয়।

উদাহরণ:

• LRUCache cache = new LRUCache(2) (capacity = 2)
• cache.put(1, 1) → cache: {1=1}
• cache.put(2, 2) → cache: {1=1, 2=2}
• cache.get(1) → returns 1; cache: {2=2, 1=1}
• cache.put(3, 3) → key 2 evict হয়; cache: {1=1, 3=3}
• cache.get(2) → returns -1 (not found)

চিন্তার পদ্ধতি

HashMap এবং Doubly Linked List একসাথে ব্যবহার করব। HashMap দিয়ে O(1) lookup করব এবং Doubly Linked List দিয়ে LRU order maintain করব। সবচেয়ে recently used item head-এ এবং least recently used item tail-এ থাকবে।

সমাধান (Java)

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    // Doubly Linked List Node
    private class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; }
    }

    private final int capacity;
    private final Map<Integer, Node> map; // key -> Node
    private final Node head, tail;        // dummy head এবং tail

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();

        // Dummy head এবং tail node তৈরি করি
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;

        Node node = map.get(key);
        moveToFront(node); // recently used, তাই head-এ নিয়ে যাই
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // key আছে, শুধু value আপডেট করি
            Node node = map.get(key);
            node.value = value;
            moveToFront(node);
        } else {
            // নতুন node তৈরি করি
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToFront(newNode);

            // Capacity পূর্ণ হলে LRU item সরাই
            if (map.size() > capacity) {
                Node lru = tail.prev;
                removeNode(lru);
                map.remove(lru.key);
            }
        }
    }

    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToFront(Node node) {
        removeNode(node);
        addToFront(node);
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // Output: 1
        cache.put(3, 3);                  // key 2 evict হয়
        System.out.println(cache.get(2)); // Output: -1
        cache.put(4, 4);                  // key 1 evict হয়
        System.out.println(cache.get(1)); // Output: -1
        System.out.println(cache.get(3)); // Output: 3
        System.out.println(cache.get(4)); // Output: 4
    }
}

সময় জটিলতা: get এবং put উভয়ের জন্য O(1) | স্থান জটিলতা: O(capacity)

---

সারসংক্ষেপ

সমস্যা	পদ্ধতি	সময় জটিলতা	স্থান জটিলতা
Two Sum	HashMap (complement lookup)	O(n)	O(n)
Subarray Sum Equals K	Prefix Sum + HashMap	O(n)	O(n)
Longest Consecutive Sequence	HashSet + Sequence counting	O(n)	O(n)
Top K Frequent Elements	HashMap + Bucket Sort	O(n)	O(n)
LRU Cache	HashMap + Doubly Linked List	O(1) per op	O(capacity)

HashMap-এর মূল শক্তি হলো O(1) average সময়ে key-value lookup। এই সমস্যাগুলো থেকে বোঝা যায় যে HashMap কীভাবে Prefix Sum, Frequency Counting, এবং Cache Design-এর মতো বিভিন্ন কৌশলে ব্যবহার করা যায়। Interview-এ HashMap এর এই pattern গুলো ভালোভাবে রপ্ত করলে অনেক জটিল সমস্যাও সহজে সমাধান করা সম্ভব।