হ্যাশ টেবিলপড়তে ৬ মিনিট লাগবে

ফ্রিকোয়েন্সি প্যাটার্ন (Frequency Patterns)

একবার গোনো, বারবার উত্তর দিন — হ্যাশ ম্যাপের জাদুকরী সুপারপাওয়ার

count all: O(n)lookup count: O(1)space: O(k) যেখানে k=আলাদা বা ইউনিক আইটেমের সংখ্যা

কোডিং ইন্টারভিউতে হ্যাশ ম্যাপের (Hash Map) সবচেয়ে বেশি ব্যবহৃত এবং হিট ট্রিকটার নামই হলো ফ্রিকোয়েন্সি প্যাটার্ন (Frequency pattern)। এর মূল কারসাজিটা হলো: মাত্র একবার O(n) সময় খরচ করে সবকিছুর একটা লিস্ট বা ম্যাপ বানিয়ে ফেলা, এরপর যতবার খুশি ওই লিস্ট থেকে O(1) স্পিডে বা চোখের পলকে যেকোনো ফ্রিকোয়েন্সি বা হিসাবাকিতাবের উত্তর দেওয়া।

এটাকে ঠিক নির্বাচনের সময় ভোট গণনার বোর্ডের মতো ভাবতে পারেন। যখনই কেউ জিজ্ঞেস করে "অমুক ক্যান্ডিডেট কত ভোট পেয়েছে?", তখন তো আর নতুন করে সব ব্যালট পেপার গনা হয় না। বরং একবার গোনার সময় বোর্ডে ট্যালি বা হিসাব করে রাখা হয়। ব্যস, একবারের পরিশ্রমে বোর্ড রেডি, এরপর সারাজীবন যেকোনো প্রশ্নের ওখান থেকেই ইনস্ট্যান্ট উত্তর দেওয়া যায়।

অ্যানাগ্রাম বা শব্দজট মেটানো (Anagram Detection)

দুটো শব্দকে তখনই অ্যানাগ্রাম বলা হয়, যখন দুটোতে হুবহু একই অক্ষর একই সংখ্যকবার থাকে। এদের মেলানোর বোকা উপায় হলো: দুটো শব্দকে ছোট থেকে বড় সাজানেন (sort) → যাতে O(n log n) সময় লাগে। এরচেয়ে ফ্রিকোয়েন্সি ম্যাপ বা ডিকশনারি দিয়ে কাজটা কত সহজে হয় দেখুন:

pseudocode

def is_anagram(s, t):
    if len(s) != len(t): return False
    count = {}
    for c in s: 
        count[c] = count.get(c, 0) + 1  # প্রথম শব্দের অক্ষরগুলো গুনছি
    for c in t:
        if c not in count or count[c] == 0:
            return False  # হিসেবে গড়মিল পেলো
        count[c] -= 1
    return True  # একদম খাপে খাপে মিলেছে! (O(n) সময়, O(k) স্পেস)

ডুপ্লিকেট বা নকল বের করা (Duplicate Detection)

"কোনো জিনিস কি একের বেশিবার এসেছে?" — এই প্রশ্নের সহজ সমাধান হলো: প্রতিটা জিনিসকে ধরে ধরে একটা সেটে (Set) ঢোকাতে থাকুন। যেই মুহূর্তে দেখবেন কোনো জিনিস সেটে আগে থেকেই বসে আছে, বুঝে নেবেননন ওটাই ডুপ্লিকেট। এর জন্য সময় ও জায়গা দুটোই লাগে O(n)। এটা দুটো লুপ (nested loop) চালানোর চেয়ে অনেক অনেক ফাস্ট।

◈ Watch frequency counting

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

সবচেয়ে বেশি আসা টপ-কে (Top-K) আইটেম বের করা

ধরুন আপনাকে বলা হলো একটা লিস্ট থেকে সবচেয়ে বেশিবার আসা k-টা জিনিস বের করতে। সাধারণ বুদ্ধি বলবে: ফ্রিকোয়েন্সি বের করে ছোট থেকে বড় হিসেবে সাজান → স্পিড হবে O(n log n)। কিন্তু এর চেয়েও স্মার্ট উপায় আছে:

প্রথমে ফ্রিকোয়েন্সি ম্যাপ বানান: সময় লাগবে O(n)।
এরপর k সাইজের একটা মিন-হিপ (min-heap) ব্যবহার করুন: ম্যাপের প্রতিটা (ফ্রিকোয়েন্সি, আইটেম)-কে হিপের ভেতর ঢুকিয়ে দিন। হিপের সাইজ k-এর বেশি হলেই সবচেয়ে ছোটটাকে বের করে দিন। মোট সময় লাগবে: O(n log k)।
আর সবচেয়ে জোস উপায় হলো বাকেট সর্ট (Bucket sort): ফ্রিকোয়েন্সি অনুযায়ী বাকেট বা বালতি বানান (সর্বোচ্চ ফ্রিকোয়েন্সি হতে পারে n), এরপর এলিমেন্টগুলোকে তাদের নিজ নিজ বালতিতে ফেলে পেছন থেকে টপ-কে আইটেমগুলো পড়ে নিন। সময় লাগবে মাত্র O(n)!

স্লাইডিং উইন্ডো + ফ্রিকোয়েন্সি ম্যাপ (Sliding Window + Frequency)

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

pseudocode

def longest_k_distinct(s, k):
    freq, left, best = {}, 0, 0
    for right, c in enumerate(s):
        freq[c] = freq.get(c, 0) + 1
        while len(freq) > k:  # লিমিট ক্রস করেছে
            l = s[left]
            freq[l] -= 1
            if freq[l] == 0: del freq[l]  # শূন্য হলে ম্যাপ থেকে বিদায়
            left += 1
        best = max(best, right - left + 1)
    return best

দ্রষ্টব্য: কোডিং প্রশ্নে যখনই 'count (গণনা)', 'frequency (ফ্রিকোয়েন্সি)', 'most common (সবচেয়ে বেশি)', 'duplicate (ডুপ্লিকেট)', বা 'anagram (অ্যানাগ্রাম)'-এর মতো শব্দ দেখবেন — বিন্দুমাত্র চিন্তা না করে সাথে সাথে একটা ফ্রিকোয়েন্সি ম্যাপ বানিয়ে ফেলবেন। এটি আপনাকে ৯৯% সময়ে সবচেয়ে বেস্ট সমাধানের রাস্তা দেখিয়ে দেবে।