Array ও hash map: interview-এর অবশ্যজ্ঞাতব্য প্যাটার্ন

অনেক coding সমস্যা আলাদা দেখালেও কয়েকটি প্যাটার্নে নেমে আসে। প্রথম ও সবচেয়ে কাজের হলো hash map (dictionary, object বা map-ও বলে)। এটি key-value জোড়া রাখে এবং গড়ে একটি key খোঁজা, যোগ ও সরানো O(1) সময়ে করে। Hash set শুধু key রাখে এবং "এটি কি আগে দেখেছি?" প্রশ্নের উত্তর O(1)-এ দেয়।

নিচের উদাহরণ JavaScript ধাঁচের, তবে ধারণা যেকোনো ভাষায় খাটে।

প্যাটার্ন ১: "আগে কি দেখেছি?" (set)

সমস্যা: array-তে কি ডুপ্লিকেট আছে?

Brute force প্রতিটি জোড়া তুলনা করে: O(n²)। Set দিয়ে এক পাসে হয়:

function hasDuplicate(nums) {
  const seen = new Set();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}
// সময় O(n), space O(n)

এটি space দিয়ে সময় কেনা, খুব প্রচলিত কৌশল।

প্যাটার্ন ২: পরিপূরক খোঁজা (Two Sum)

সমস্যা: সংখ্যা ও একটি target দেওয়া, যাদের মান যোগ করলে target হয় এমন দুটি index খুঁজুন।

Brute force O(n²)। প্রতিটি সংখ্যার জন্য শুধু জানা দরকার target - number আগে দেখা গেছে কি না:

function twoSum(nums, target) {
  const indexOf = new Map();          // value -> index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (indexOf.has(need)) return [indexOf.get(need), i];
    indexOf.set(nums[i], i);
  }
  return [];
}
// সময় O(n), space O(n)

বসানোর আগে যাচাই করুন, যাতে একটি element নিজের সাথে জোড়া না হয়।

প্যাটার্ন ৩: frequency গণনা

সমস্যা: দুটি string কি anagram? কোন element সবচেয়ে বেশি আসে?

Map দিয়ে সংখ্যা গুনুন:

function isAnagram(a, b) {
  if (a.length !== b.length) return false;
  const count = {};
  for (const ch of a) count[ch] = (count[ch] || 0) + 1;
  for (const ch of b) {
    if (!count[ch]) return false;
    count[ch]--;
  }
  return true;
}
// সময় O(n), space O(k), k হলো বর্ণমালার আকার

শুধু ছোট হাতের অক্ষর হলে ২৬টি counter-এর নির্দিষ্ট array আরও সরল এবং O(1) space দেয়।

প্যাটার্ন ৪: key দিয়ে দল করা

সমস্যা: পরস্পরের anagram এমন শব্দ দল করুন।

একটি canonical key (যেমন সাজানো অক্ষর) ব্যবহার করে প্রতিটি শব্দ সেই key-র তালিকায় রাখুন:

function groupAnagrams(words) {
  const groups = new Map();
  for (const w of words) {
    const key = [...w].sort().join("");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(w);
  }
  return [...groups.values()];
}

Item দল বা ডুপ্লিকেট-মুক্ত করতে হলে জিজ্ঞেস করুন: কোন key সমান জিনিসকে একই দেখায়?

প্যাটার্ন ৫: prefix sum

সমস্যা: "index i থেকে j পর্যন্ত element-এর যোগফল" ধরনের অনেক প্রশ্নের দ্রুত উত্তর, বা নির্দিষ্ট যোগফলের subarray গোনা।

আগে হিসাব করুন prefix[k] = প্রথম k টি element-এর যোগফল। তখন i থেকে j পর্যন্ত যোগফল O(1)-এ prefix[j + 1] - prefix[i]।

"যোগফল K এমন subarray গোনা"-তে প্রতিটি prefix sum কতবার এসেছে তার map রাখুন:

function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]);     // prefix sum -> count
  let sum = 0, count = 0;
  for (const n of nums) {
    sum += n;
    count += seen.get(sum - k) || 0;
    seen.set(sum, (seen.get(sum) || 0) + 1);
  }
  return count;
}
// সময় O(n), space O(n)

এটি ঋণাত্মক সংখ্যাতেও কাজ করে, যেখানে sliding window করে না।

প্যাটার্ন ৬: in-place array কৌশল

কখনো memory সীমিত, বা array নিজেই স্টোরেজ হিসেবে পুনর্ব্যবহার করা যায়:

• অনুমতি থাকলে array-কেই চিহ্ন হিসেবে ব্যবহার করুন (যেমন মান ঋণাত্মক করে visited index চিহ্নিত)।
• Read ও write pointer দিয়ে scan করার সময় element swap বা overwrite করুন।

Input বদলালে এবং তা গ্রহণযোগ্য কি না স্পষ্ট বলুন।

এই সমস্যা কীভাবে চিনবেন

যখন দেখবেন, hash map ভাবুন:

• "জোড়া/পরিপূরক খুঁজুন", "গুনুন", "সবচেয়ে ঘন ঘন", "প্রথম অ-পুনরাবৃত্ত"।
• "ডুপ্লিকেট", "অনন্য", "anagram", "group by"।
• কিছু খোঁজার জন্য nested loop-সহ brute force। Map ভেতরের খোঁজাকে O(1) করে।

সাধারণ ভুল

• Loop-এর ভেতরে array খোঁজা (includes, indexOf), যা O(n²) লুকায়।
• ফাঁকা ইনপুট বা একক-element ক্ষেত্র ভুলে যাওয়া।
• ভুলে mutable object বা array-কে map key বানানো।
• মান ঋণাত্মক, পুনরাবৃত্ত বা অতি বড় হতে পারে কি না স্পষ্ট না করা।
• সবচেয়ে খারাপ ক্ষেত্রে hash collision উপেক্ষা। গড় O(1) সাধারণত গ্রহণযোগ্য, তবে উল্লেখ করতে পারেন।

অনুশীলনের সমস্যা

Contains Duplicate, Valid Anagram, Two Sum, Group Anagrams, Top K Frequent Elements, Longest Consecutive Sequence, Subarray Sum Equals K, Product of Array Except Self।

মূল কথা: দ্রুত খোঁজা, গোনা বা দল করা দরকার হলে hash map বা set নিন। সামান্য memory দিয়ে O(n²) থেকে O(n)-এ নামুন, এবং range-sum প্রশ্নে prefix sum ব্যবহার করুন।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ১ (মূল প্যাটার্ন): 2 নম্বর (মোট 5)। আগের লেখা: Big-O সহজ ভাষায়: time ও space complexity.