Hash Maps #️⃣ - intervyu kaliti 🔑

HashMap Data Structure tech intervyularda eng ko'p so'raladigan agoritmlardan biri.

Lekin ajoyib hushxabar bor 🤩

HashMapni eng ko'p uchraydigan 2ta holatda ishlatishni o'rganib olsangiz yetarli!

Ushbu post davomida ikkala holatni ham misollar yordami o'rganib olasiz.

1. Element mavjudligini aniqlash.

Array ichida element bor/yo'qligini tekshirish linear \(O(N)\) vaqt talab etadi. Ya'ni array ichidagi $N$ta elementlarni tekshirib chiqish kerak.

HashMap esa shu operatsiyani constant \(O(1)\) vaqt ichida bajaradi.

Tasavvur qiling sizda shu tekshirish operatsiyasini \(M\) marta takrorlashingiz kerak. Array ustida bu \(O(NM)\) vaqt talab qilsa, HashMap ustida \(O(M)\) vaqt oladi.

Bu nazariyani quyidagi LeetCode misollari orqali isbotlaymiz.

Two Sum

int array nums va int target berilgan bo'lsa, array ichidan yig'indisi targetga teng 2ta elementlar indexlarini qaytarish kerak.

👉 Masalaga havola

public class Solution 
{
    public int[] TwoSum(int[] nums, int target)
    {
        var juftlar = new Dictionary<int, int>();

        for(int i = 0; i < nums.Length; i++)
            if(juftlar.ContainsKey(target - nums[i]))
                return new int[] { i, juftlar[target - nums[i]]};
            else
                juftlar.TryAdd(nums[i], i);

        return new int[] { };
    }
}

Tip

Yuqoridagi yechimda HashMapga asoslangan Dictionary ishlatilgan.

• Qisqacha, arraydagi har bir elementni juftini Dictionarydan qidiramiz.
• Agar jufti yo'q bo'lsa, shu elementni Dictionaryga qo'shamiz.

Dictionarydan qidirish \(O(1)\) vaqt talab qiladi. Bu amal for loop ichida \(N\) marta takrorlangani uchun yechim umumiy \(O(N)\) vaqt talab qiladi.

Counting Elements

Berilgan array ichida x + 1 jufti mavjud bo'lgan x qiymatli elementlar sonini qaytarish kerak. Agar shunday sonlar bir nechta bo'lsa, hammasi alohida sanalsin.

👉 Masalaga havola

public class Solution
{
    public int CountElements(int[] nums)
    {
        var frequency = new Dictionary<int, int>();
        foreach(var num in nums)
        {
            frequency.TryGetValue(num, out var value);
            frequency[num] = value + 1;
        }

        var count = 0;
        foreach(var num in nums)
            if(frequency.ContainsKey(num + 1))
                count++;
            
        return count;
    }
}

Tip

Bu yechimda ham HashMap sifatida **C#**ning Dictionary classi ishlatilgan.

• Array elementlari necha marta takrorlanishini Dictionaryga saqlab olamiz.
• Keyingi loopda shu map ichidan \(x+1\) qiymatli elementlarni qidiramiz.

Ikkala loop ham \(O(N)\) vaqt sarflagani uchun umumiy algoritm \(O(N)\) vaqt oladi.

First Letter to Appear Twice

Kichik lotin harflaridan iborat string berilganda ikki marta takrorlanuvchi birinchi harfni qaytaring.

👉 Masalaga havola

Warning

Ushbu yechimni mashq sifatida o'zingiz bajarib ko'ring.

Savollar va mulohazalaringizni o'zingizga o'xshagan qiziquvchan dasturchilar bilan Telegram Kanalimizda ulashing ✍️.

---

2. Takrorlanishlar sonini sanash

HashMap yordamida istalgan elementni to'plamdagi chastotasini aniqlash juda ham oson.

Masalan, string ichidagi belgilar chastotasi bir xil yoki yo'qligini aniqlash.

HashMap yordami berilgan tekst ichidagi har bir belgi chastotasi bir xil yo'qlini bitta loop orqali \(O(N)\) linear vaqt ichida aniqlasa bo'ladi.

Keling yana misollar yordamida isbotlaymiz.

Subarray Sum Equals K

int array nums va int k berilgan bo'lsa, yig'indisi k ga teng bo'lgan subarraylar sonini qaytaring.

Subarray - ketma-ket joylashgan elementlardan tashkil topgan kichi array.

👉 Masalaga havola

public class Solution 
{
    public int SubarraySum(int[] nums, int k) 
    {
        var sumsMap = new Dictionary<long, int>();
        var count = 0;
        long sum = 0;

        foreach(var num in nums)
        {
            sum += num;

            if(sum == k)
                count++;
            
            if(sumsMap.TryGetValue(sum - k, out var frequency))
                count += frequency;
            
            sumsMap.TryGetValue(sum, out var x);
            sumsMap[sum] = x + 1;
        }

        return count;
    } 
}

Tip

Yuqoridagi yechimda barcha subarraylar yig'indisini hisoblab ketish bilan bir vaqtda, shu yig'indini HashMapga joylab, agar mavjud bo'lsa chastotasini oshirib ketamiz.

• Har bir loop iterationda yig'indi \(K\) ga teng bo'lsa sanoqni birga oshiramiz
• Agar HashMap ichida joriy yig'indini jufti \(sum - k\) mavjud bo'lsa, o'sha kalitli elementni chastotasini sanoqqa qo'shamiz.

HashMapdan qidirish \(O(1)\) vaqt olgani va bu operatsiya \(N\) marta takrorlangani uchun umumiy algoritm \(O(N)\) vaqt oladi.

Maximum Number of Balloons

text deb nomlangan string berilgan bo'lsa, undagi balloon takrorlanishlar sonini qaytaring.

👉 Masalaga havola

public class Solution 
{
    public int MaxNumberOfBalloons(string text) 
    {
        var map = new Dictionary<char, int>
        {
            { 'b', 0 },
            { 'a', 0 },
            { 'l', 0 },
            { 'o', 0 },
            { 'n', 0 },
        };

        foreach(var c in text)
            if(map.TryGetValue(c, out var frequency))
                map[c] = ++frequency;
        
        // l va o ikki martadan keladi
        map['l'] /= 2;
        map['o'] /= 2;

        var min = int.MaxValue;
        foreach(var value in map.Values)
            min = Math.Min(min, value);
        
        return min;
    }
}

Tip

Yechimda yana HashMap yordamida harflar chastotasi saqlangan. Keyin esa bu mapdan eng kichik chastota tanlab olingan. Chunki shu eng kam marta takrorlangan harf balloon so'zini ko'pi bilan necha marta hosil qila olishimizni belgilaydi.

• Kod juda ham oddiy, tushinish muammo bo'lmasa kerak.
• Etiborga loyiq jihati 2ta loop ishlatilgan bo'lsa ham algoritm umumiy murakkabligi $O(N)$ligicha qoladi.
• balloon so'zida 'o' va 'l' harflari 2 martadan takrorlangani uchun, ularni chastotatsini 2ga bo'lib qoyganmiz

---

👋 Hulosa

HashMap yoki HashTable Data Structure dasturlashdagi eng muhim va juda ko'p uchraydigan algoritmlar. Ularni o'rganish va mashq qilish orqali nafaqat intervyu savollarida balki injinerlik faoliyatingizda ham sezilarli samara bo'ladi.

HINT

Keyingi maqolada Binary Heap Data Structureni **C#**ni eng zamonaviy featurelarini qo'llagan holda implementatsiya qilamiz.

Shu kabi sifatli o'zbek tilidagi kontentni qo'llab quvvatlash uchun bizni Telegram Kanalimizga obuna bo'ling.

---

Wahid Abduhakimov