DEV Community

Cover image for Using HashMaps, Coding Interview Pattern
Harsh Mishra
Harsh Mishra

Posted on

Using HashMaps, Coding Interview Pattern

Hashmaps

Hashmaps are a versatile data structure essential for many coding interview problems due to their average-case (O(1)) time complexity for insertions, deletions, and lookups. They allow you to efficiently store and retrieve key-value pairs by leveraging a hash function to distribute keys across an array. In interviews, hashmaps are frequently used to solve problems related to frequency counting, finding pairs that sum to a target value, grouping anagrams, and detecting subarrays with specific sums. Their ability to handle large datasets with minimal computational overhead makes them a valuable tool in optimizing solutions and tackling complex algorithmic challenges.

Valid Anagram

This question is part of Leetcode problems, question no. 242.

Here’s the Solution class for the "Valid Anagram" problem in C++:

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;

        unordered_map<char, int> countMap;

        // Count frequency of each character in string s
        for (char c : s) {
            countMap[c]++;
        }

        // Subtract frequency of each character in string t
        for (char c : t) {
            countMap[c]--;
            if (countMap[c] < 0) {
                return false;
            }
        }

        return true;
    }
};
Enter fullscreen mode Exit fullscreen mode

Top K Frequent Elements

This question is part of Leetcode problems, question no. 347.

Here’s the Solution class for the "Top K Frequent Elements" problem in C++:

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int> frequencyMap;

        // Count the frequency of each number
        for (int num : nums) {
            frequencyMap[num]++;
        }

        // Use a max-heap (priority queue) to keep track of top k frequent elements
        priority_queue<pair<int,int>, vector<pair<int,int>>, less<pair<int,int>>> maxHeap;

        for (const auto& entry : frequencyMap) {
            maxHeap.push({entry.second, entry.first});
        }

        // Extract the top k frequent elements from the heap
        vector<int> result;
        for(int i = 0; i < k; ++i) {
            result.push_back(maxHeap.top().second);
            maxHeap.pop();
        }

        return result;
    }
};
Enter fullscreen mode Exit fullscreen mode

Top K Frequent Words

This question is part of Leetcode problems, question no. 692.

Here’s the Solution class for the "Top K Frequent Words" problem in C++:

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        // Step 1: Count the frequency of each word
        map<string, int> frequency;
        for (const string& word : words) {
            frequency[word]++;
        }

        // Step 2: Create a min-heap using a priority queue
        auto cmp = [](const pair<int, string>& a, const pair<int, string>& b) {
            if (a.first != b.first) {
                return a.first > b.first; // Min-heap based on frequency (reversed for min-heap)
            }
            return a.second < b.second; // Lexicographical order for tie
        };
        priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(cmp)> minHeap(cmp);

        // Step 3: Insert elements into the min-heap
        for (const auto& entry : frequency) {
            minHeap.push({entry.second, entry.first});
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }

        // Step 4: Extract elements from the heap and store in the result vector
        vector<string> result;
        while (!minHeap.empty()) {
            result.push_back(minHeap.top().second);
            minHeap.pop();
        }

        // Since we want the result in lexicographical order, reverse the vector
        reverse(result.begin(), result.end());

        return result;

    }
};
Enter fullscreen mode Exit fullscreen mode

Sort Characters by Frequency

This question is part of Leetcode problems, question no. 451.

Here’s the Solution class for the "Sort Characters by Frequency" problem in C++:

class Solution {
public:
    string frequencySort(string s) {
        // Step 1: Count the frequency of each character
        map<char, int> frequencyMap;
        for (char c : s) {
            frequencyMap[c]++;
        }

        // Step 2: Create a max-heap using a priority queue
        auto comp = [](const auto& a, const auto& b) {
            if (a.first != b.first) {
                return a.first < b.first; // Max-heap based on frequency
            }
            return a.second < b.second; // Lexicographical order for tie
        };
        priority_queue<pair<int, char>, vector<pair<int, char>>, decltype(comp)> maxHeap(comp);

        // Step 3: Insert elements into the max-heap
        for (const auto& entry : frequencyMap) {
            maxHeap.push({entry.second, entry.first});
        }

        // Step 4: Construct the result string
        string result;
        while (!maxHeap.empty()) {
            int freq = maxHeap.top().first;
            char ch = maxHeap.top().second;
            for (int i = 0; i < freq; ++i) {
                result += ch;
            }
            maxHeap.pop();
        }

        return result;
    }
};
Enter fullscreen mode Exit fullscreen mode

Contains Duplicate

This question is part of Leetcode problems, question no. 217.

Here’s the Solution class for the "Contains Duplicate" problem in C++:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // Step 1: Use a map to track the frequency of each number
        map<int, int> frequencyMap;
        for (int num : nums) {
            frequencyMap[num]++;
            // Step 2: If any number appears more than once, return true
            if (frequencyMap[num] > 1) {
                return true;
            }
        }

        // Step 3: If no duplicates are found, return false
        return false;
    }
};
Enter fullscreen mode Exit fullscreen mode

Contains Duplicate II

This question is part of Leetcode problems, question no. 219.

Here’s the Solution class for the "Contains Duplicate II" problem in C++:

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> indexMap;

        for (int i = 0; i < nums.size(); ++i) {
            int num = nums[i];

            // Check if the number exists in the map and the distance is within k
            if (indexMap.find(num) != indexMap.end() && i - indexMap[num] <= k) {
                return true;
            }

            // Update the index of the current number
            indexMap[num] = i;
        }

        return false;
    }
};
Enter fullscreen mode Exit fullscreen mode

Intersection of Two Arrays

This question is part of Leetcode problems, question no. 349.

Here’s the Solution class for the "Intersection of Two Arrays" problem in C++:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> resultSet;

        for (int num : nums2) {
            if (set1.find(num) != set1.end()) {
                resultSet.insert(num);
            }
        }

        return vector<int>(resultSet.begin(), resultSet.end());
    }
};
Enter fullscreen mode Exit fullscreen mode

Intersection of Two Arrays II

This question is part of Leetcode problems, question no. 350.

Here’s the Solution class for the "Intersection of Two Arrays II" problem in C++:

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> countMap;
        vector<int> result;

        // Count the occurrences of each number in nums1
        for (int num : nums1) {
            countMap[num]++;
        }

        // Find the intersection with nums2
        for (int num : nums2) {
            if (countMap[num] > 0) {
                result.push_back(num);
                countMap[num]--;
            }
        }

        return result;
    }
};
Enter fullscreen mode Exit fullscreen mode

Ransom Note

This question is part of Leetcode problems, question no. 383.

Here’s the Solution class for the "Ransom Note" problem in C++:

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> charCount;

        // Count the frequency of each character in the magazine
        for (char c : magazine) {
            charCount[c]++;
        }

        // Check if the ransom note can be constructed
        for (char c : ransomNote) {
            if (charCount[c] == 0) {
                return false;
            }
            charCount[c]--;
        }

        return true;
    }
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)