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;
}
};
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;
}
};
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;
}
};
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;
}
};
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;
}
};
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;
}
};
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());
}
};
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;
}
};
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;
}
};