# New Hash Tables Interview Questions

## Introduction

Hash tables are a powerful data structure used to efficiently store and retrieve key-value pairs. Imagine it like a dictionary: you provide a word (the key), and it gives you its corresponding definition (the value). The magic lies in the hash function, which transforms the key into a unique index, allowing quick access to the value. In interviews, you may encounter questions about hash tables, such as how they work, collision resolution strategies, or time complexity analysis. Understanding the basics, like hash functions and collision handling, will help you navigate these questions and demonstrate your grasp of this essential data structure.

## Questions

### 1. What is a hash table? Explain with examples

A hash table is a data structure that stores key-value pairs in a way that allows for efficient retrieval and insertion of data. It uses a hash function to map keys to specific positions in an array, known as buckets or slots. This mapping enables constant-time access to elements, making hash tables an excellent choice for fast lookups.

Example:
Suppose we want to store the ages of individuals using their names. We can use a hash table where the names are keys, and the corresponding ages are values.

``````Hash Table:
{
"Alice": 28,
"Bob": 30,
"Charlie": 22,
"David": 25,
...
}``````

### 2. How does a hash table work?

In a hash table, the key is converted into an index using a hash function. This index is used to determine the bucket where the value associated with the key will be stored or retrieved. Here’s a simple example in C++:

C++
``````#include <iostream>
#include <unordered_map>

int main() {
// Creating a hash table (unordered_map) to store age data
std::unordered_map<std::string, int> ageTable;

// Inserting key-value pairs into the hash table
ageTable["Alice"] = 28;
ageTable["Bob"] = 30;
ageTable["Charlie"] = 22;
ageTable["David"] = 25;

// Accessing the value using the key
std::cout << "Age of Alice: " << ageTable["Alice"] << std::endl;
std::cout << "Age of David: " << ageTable["David"] << std::endl;

return 0;
}``````

### 3. What are the primary operations of a hash table?

The primary operations of a hash table are:

1. Insertion: Adding a new key-value pair to the hash table.
2. Deletion: Removing a key-value pair from the hash table.
3. Lookup/Retrieval: Finding and accessing the value associated with a given key.

### 4. What is a hash function and what is its purpose?

A hash function is a mathematical function that takes an input (or ‘key’) and converts it into a fixed-size string of characters, which is typically a sequence of numbers and letters. The output generated by the hash function is known as the ‘hash value’ or ‘hash code.’ The primary purpose of a hash function is to map data of arbitrary size to a fixed-size string, which serves as a unique identifier or digital fingerprint for the input data.

Purpose of Hash Functions:

1. Data Integrity and Security: Hash functions are widely used in cryptography and data security to ensure data integrity. By generating a unique hash code for a piece of data, any change to the data, even a small one, would result in a completely different hash value. Hashing is often used to verify the integrity of files and ensure they have not been tampered with.
2. Hash Tables and Data Structures: Hash functions are crucial in hash tables, a popular data structure used to implement associative arrays or dictionaries. In hash tables, the hash value serves as an index to store and retrieve data efficiently. A good hash function ensures an even distribution of hash codes, reducing collisions and improving the performance of hash table operations.
3. Data Retrieval and Searching: Hash functions are employed in various search algorithms and data retrieval processes. They help in indexing and locating data quickly, especially when dealing with large datasets.
4. Digital Signatures and Authentication: Hash functions are used to create digital signatures, which are essential in digital authentication and verifying the authenticity of digital documents or messages.
5. Checksums and Error Detection: Hash functions are used to generate checksums for data transmitted over networks. These checksums help detect errors during data transmission and ensure data integrity.
6. Caching and Data Compression: Hash functions play a role in caching data to speed up access times, as well as in data compression algorithms, where repeated patterns can be identified and represented by hash codes to reduce storage requirements.

### 5. What is a collision in a hash table and how can it be handled?

A collision occurs in a hash table when two or more keys are mapped to the same array index by the hash function. Handling collisions is essential to ensure the correct storage and retrieval of data. There are various methods to handle collisions, and two common approaches are separate chaining and open addressing.

Example of separate chaining in C++:

C++
``````#include <iostream>
#include <list>
#include <string>

const int TABLE_SIZE = 10;

class HashTable {
private:
std::list<std::pair<std::string, int>> table[TABLE_SIZE];

// Hash function to calculate the index from the key
int hash(const std::string& key) {
int sum = 0;
for (char c : key) {
sum += c;
}
return sum % TABLE_SIZE;
}

public:
void insert(const std::string& key, int value) {
int index = hash(key);
table[index].push_back(std::make_pair(key, value));
}

int retrieve(const std::string& key) {
int index = hash(key);
for (const auto& entry : table[index]) {
if (entry.first == key) {
return entry.second;
}
}
}
};

int main() {
HashTable ageTable;

ageTable.insert("Alice", 28);
ageTable.insert("Bob", 30);
ageTable.insert("Charlie", 22);
ageTable.insert("David", 25);

std::cout << "Age of Alice: " << ageTable.retrieve("Alice") << std::endl;
std::cout << "Age of David: " << ageTable.retrieve("David") << std::endl;

return 0;
}``````

### 7. What is load factor in a hash table?

The load factor in a hash table is the ratio of the number of stored elements (key-value pairs) to the number of available buckets (or slots). It is expressed as a value between 0 and 1. A high load factor indicates that the hash table is almost full, and this can lead to an increased number of collisions, reducing the efficiency of the hash table.

Load Factor = (Number of stored elements) / (Number of available buckets)

Example:
If a hash table has 50 stored elements and 100 available buckets, the load factor would be 50/100 = 0.5.

### 8. What is rehashing in hash tables and why is it needed?

Rehashing in hash tables is the process of resizing the underlying array (or table) used to store key-value pairs when the load factor exceeds a certain threshold. The load factor is defined as the ratio of the number of elements (keys) in the hash table to the total number of buckets (slots) in the array. When the load factor surpasses a predetermined threshold, it indicates that the hash table is becoming crowded, leading to an increased likelihood of collisions (multiple keys being hashed to the same bucket). Rehashing aims to maintain the efficiency and performance of the hash table by reducing collisions and balancing the distribution of elements.

Why is Rehashing Needed?

1. Avoiding Collisions: As the number of elements in the hash table increases, the probability of two different keys getting the same hash code and colliding in the same bucket also increases. Collisions can lead to degraded performance and slower operations, as additional measures, such as linked lists or binary trees, may be needed to handle collisions. Rehashing helps to redistribute elements across a larger array, reducing the likelihood of collisions.
2. Performance Optimization: Hash tables provide efficient data retrieval, insertion, and deletion operations with an average time complexity of O(1). However, when the load factor increases and collisions become more frequent, the average time complexity can degrade to O(n) due to the linear search in the collided bucket. Rehashing helps maintain a low load factor, which ensures that the average time complexity of hash table operations remains closer to O(1).
3. Space Efficiency: When the hash table becomes crowded with a high load factor, a lot of space in the underlying array remains unused, leading to inefficient memory usage. Rehashing allows for resizing the array, reducing wasted space and improving memory efficiency.

Process of Rehashing:
Rehashing typically involves creating a new larger array (usually double the size of the current array) and reinserting all the elements from the old array into the new one. The hash function is also updated to map the keys to new bucket locations in the resized array. After rehashing, the load factor is recalculated, and future insertions and retrievals are based on the updated hash table.

Rehashing is usually triggered automatically when the load factor exceeds a predefined threshold, ensuring that the hash table continues to perform efficiently as the number of elements increases. By dynamically adjusting the size of the array and redistributing elements, rehashing helps maintain a balanced and efficient hash table.

Example of rehashing in C++:

C++
``````#include <iostream>
#include <unordered_map>

int main() {
// Creating a hash table (unordered_map) to store age data
std::unordered_map<std::string, int> ageTable;

// Setting the load factor threshold (0.7 in this case)

// Inserting key-value pairs into the hash table
ageTable["Alice"] = 28;
ageTable["Bob"] = 30;
ageTable["Charlie"] = 22;
ageTable["David"] = 25;

// Check the current load factor

// Adding more elements to trigger rehashing
ageTable["Eve"] = 24;
ageTable

["Frank"] = 26;
ageTable["Grace"] = 32;

// Check the new load factor after rehashing

return 0;
}``````

### 9. Explain the concept of open addressing in hash table collision resolution.

Open addressing is a collision resolution technique used in hash tables. When a collision occurs, instead of storing multiple elements in the same bucket, open addressing searches for the next available slot (bucket) in the table to place the colliding element. This process continues until an empty slot is found.

Example:
Suppose we have the following hash table, and the hash function maps keys to array indices:

C++
``````Hash Table (Array):
[0: (Alice, 28), 1: (Bob, 30), 2: (David, 25), 3: - , 4: - , 5: (Charlie, 22), ...]``````

Now, when we want to insert a new key-value pair with the key “Elise,” and it maps to index 3, but index 3 is already occupied by another element, we start probing the next available slots sequentially. Suppose index 4 is also occupied; then, we move to index 5, which is empty, and we insert the new element there:

C++
``````After Inserting Elise:
[0: (Alice, 28), 1: (Bob, 30), 2: (David, 25), 3: - , 4: - , 5: (Charlie, 22), 6: (Elise, 29), ...]``````

### 10. Explain the concept of separate chaining in hash table collision resolution.

Separate chaining is another collision resolution technique used in hash tables. In this approach, each bucket of the hash table is a separate data structure, such as a linked list or a binary search tree. When a collision occurs, new elements with the same hash value are simply appended to the linked list or inserted into the binary search tree at the corresponding bucket.

Example:
Suppose we have the following hash table using separate chaining:

C++
``````Hash Table (Array of Linked Lists):
[0: -> (Alice, 28) -> (David, 25), 1: -> (Bob, 30), 2: - , 3: -> (Charlie, 22), ...]``````

When we insert a new key-value pair with the key “Elise,” and it maps to index 3, but index 3 is already occupied, we add the new element to the linked list at index 3:

C++
``````After Inserting Elise:
[0: -> (Alice, 28) -> (David, 25), 1: -> (Bob, 30), 2: - , 3: -> (Charlie, 22) -> (Elise, 29), ...]``````

### 11. What are some common use cases of hash tables?

Hash tables are widely used in various applications due to their efficient lookup and insertion capabilities. Some common use cases of hash tables include:

• Caching mechanisms: To store frequently accessed data, like caching the results of expensive computations.
• Databases and indexing: To implement indexing structures for quick data retrieval.
• Counting occurrences: To count the frequency of elements in a dataset or text.
• Symbol tables: To build interpreters, compilers, and lexical analyzers for programming languages.
• Cryptography: To store and retrieve cryptographic keys and values securely.

### 12. What is a hash map? How is it different from a hash table?

In practice, the terms “hash map” and “hash table” are often used interchangeably, and there is no strict distinction between them. Both refer to data structures that use a hash function to map keys to values. In C++, the standard library provides an implementation of a hash map as `std::unordered_map`, which is commonly used.

Example of a hash map in C++:

C++
``````#include <iostream>
#include <unordered_map>

int main() {
// Creating a hash map (unordered_map) to store age data
std::unordered_map<std::string, int> ageMap;

// Inserting key-value pairs into the hash map
ageMap["Alice"] = 28;
ageMap["Bob"] = 30;
ageMap["Charlie"] = 22;
ageMap["David"] = 25;

// Accessing the value using the key
std::cout << "Age of Alice: " << ageMap["Alice"] << std::endl;
std::cout << "Age of David: " << ageMap["David"] << std::endl;

return 0;
}``````

As seen in the example above, a hash map uses a hash function to map keys to values, just like a hash table.

### 13. What is the time complexity of operations in a hash table?

The time complexity of operations in a hash table depends on the efficiency of the hash function and the collision resolution method used. In general, assuming a good hash function and minimal collisions, the time complexities are as follows:

• Insertion: O(1) on average (constant time), O(n) in the worst case due to rehashing.
• Deletion: O(1) on average (constant time), O(n) in the worst case for similar reasons as insertion.
• Lookup/Retrieval: O(1) on average (constant time), O(n) in the worst case due to probing in open addressing or traversing linked lists in separate chaining.

Example in C++:

C++
``````#include <iostream>
#include <unordered_map>

int main() {
// Creating a hash table (unordered_map) to store age data
std::unordered_map<std::string, int> ageTable;

// Inserting key-value pairs into the hash table
ageTable["Alice"] = 28;
ageTable["Bob"] = 30;
ageTable["Charlie"] = 22;
ageTable["David"] = 25;

// Accessing the value using the key (Lookup)
std::cout << "Age of Alice: " << ageTable["Alice"] << std::endl;

// Deletion
ageTable.erase("Charlie");

return 0;
}``````

### 14. Why are prime numbers used in hash functions?

Prime numbers are commonly used in hash functions because they help reduce the number of collisions. When using a prime number as the size of the hash table (the number of available buckets), it is less likely that multiple keys will hash to the same index, leading to better distribution of data.

Example of using a prime number as the size of the hash table in C++:

C++
``````#include <iostream>
#include <unordered_map>

int main() {
// Using a prime number (11) as the size of the hash table
std::unordered_map<std::string, int> ageTable(11);

// Inserting key-value pairs

into the hash table
ageTable["Alice"] = 28;
ageTable["Bob"] = 30;
ageTable["Charlie"] = 22;
ageTable["David"] = 25;

// Accessing the value using the key
std::cout << "Age of Alice: " << ageTable["Alice"] << std::endl;

return 0;
}``````

### 15. What are the characteristics of a good hash function?

A good hash function should have the following characteristics:

1. Deterministic: The same input should always produce the same hash value.
2. Fast to compute: The hash function should be computationally efficient to minimize the time taken to compute the hash value.
3. Uniform distribution: The hash values should be evenly distributed across the hash table to minimize collisions and ensure efficient use of memory.
4. Minimal collisions: It should produce as few collisions as possible for the data being hashed.
5. Avalanche effect: A small change in the input should result in a significantly different hash value to spread out the data more uniformly.

### 16. What are the advantages and disadvantages of using hash tables?

• Fast retrieval and insertion: Hash tables offer constant-time access to elements, making them efficient for lookups and insertions.
• Flexible key types: Hash tables can handle various data types as keys, making them versatile in different scenarios.
• Efficient memory usage: Hash tables can dynamically grow or shrink, utilizing memory efficiently based on the number of elements.

• Hash collisions: Collisions can reduce the efficiency of hash tables, requiring additional techniques like separate chaining or open addressing for resolution.
• Memory overhead: Hash tables may consume more memory compared to other data structures due to the overhead of maintaining buckets and pointers.
• Unordered: Hash tables do not maintain the order of elements, which can be a disadvantage in some applications that require ordered data.

### 17. Explain how hash tables can be used to implement caches.

Hash tables are often used to implement caches, which are used to store frequently accessed data to improve performance. In a cache, the hash table acts as a quick lookup for data, and when a cache miss occurs (the data is not in the cache), the data is retrieved from the main storage and added to the cache.

Example of a simple cache implementation using a hash table in C++:

C++
``````#include <iostream>
#include <unordered_map>

class Cache {
private:
std::unordered_map<std::string, std::string> data;

public:
// Retrieve data from the cache
std::string get(const std::string& key) {
if (data.find(key) != data.end()) {
return data[key];
}
}

// Add data to the cache
void put(const std::string& key, const std::string& value) {
data[key] = value;
}
};

int main() {
Cache cache;

// Inserting data into the cache
cache.put("key1", "value1");
cache.put("key2", "value2");
cache.put("key3", "value3");

// Retrieving data from the cache
std::cout << "Data for key2: " << cache.get("key2") << std::endl;
std::cout << "Data for key4: " << cache.get("key4") << std::endl;

return 0;
}``````

### 18. How are hash tables implemented in your preferred programming language?

In C++, hash tables are implemented using the `std::unordered_map` class from the Standard Template Library (STL). The `std::unordered_map` uses a hash function to map keys to values, and it handles collisions using separate chaining.

Example of using `std::unordered_map` in C++:

C++
``````#include <iostream>
#include <unordered_map>

int main() {
// Creating a hash table (unordered_map) to store age data
std::unordered_map<std::string, int> ageTable;

// Inserting key-value pairs into the hash table
ageTable["Alice"] = 28;
ageTable["Bob"] = 30;
ageTable["Charlie"] = 22;
ageTable["David"] = 25;

// Accessing the value using the key
std::cout << "Age of Alice: " << ageTable["Alice"] << std::endl;

return 0;
}``````

### 20. What are the security implications of using hash tables?

While hash tables themselves are not inherently insecure, improper usage or implementation can lead to security vulnerabilities. Some potential security implications include:

1. Hash collisions: Attackers can exploit hash collisions to perform denial-of-service attacks, causing a system to slow down or crash due to the high number of collisions.
2. Hash cracking: Hash tables are often used to store password hashes. Weak hash functions and poor salting mechanisms can make it easier for attackers to crack passwords using techniques like rainbow tables.
3. Hash-based storage vulnerabilities: Storing sensitive information directly in hash tables without proper encryption or access control can lead to data breaches if unauthorized parties gain access.

## Coding Questions

### 1. Write a function to check if two strings are anagrams of each other using a hash table.

C++
``````#include <unordered_map>
#include <string>

bool areAnagrams(const std::string& str1, const std::string& str2) {
if (str1.length() != str2.length()) {
return false;
}

std::unordered_map<char, int> charCount;

// Count characters in str1
for (char ch : str1) {
charCount[ch]++;
}

// Decrement count for characters in str2
for (char ch : str2) {
charCount[ch]--;
}

// Check if all counts are zero
for (const auto& pair : charCount) {
if (pair.second != 0) {
return false;
}
}

return true;
}``````

### 2. Write a function to find the first non-repeating character in a string using a hash table.

C++
``````#include <unordered_map>
#include <string>

char findFirstNonRepeatingChar(const std::string& str) {
std::unordered_map<char, int> charCount;

// Count characters in the string
for (char ch : str) {
charCount[ch]++;
}

// Find the first character with count 1
for (char ch : str) {
if (charCount[ch] == 1) {
return ch;
}
}

return '\0'; // Return null character if no non-repeating character found
}``````

### 3. Write a program to find pairs with a given sum in an array using a hash table.

C++
``````#include <unordered_map>
#include <vector>

std::vector<std::pair<int, int>> findPairsWithSum(const std::vector<int>& nums, int targetSum) {
std::unordered_map<int, int> complementMap;
std::vector<std::pair<int, int>> result;

for (int num : nums) {
int complement = targetSum - num;

if (complementMap.find(complement) != complementMap.end()) {
result.push_back(std::make_pair(complement, num));
}

complementMap[num]++;
}

return result;
}``````

### 4. Implement a simple hash table from scratch.

C++
``````// HashTable class implementing separate chaining collision resolution

#include <vector>
#include <list>
#include <utility>

template<typename Key, typename Value>
class HashTable {
public:
explicit HashTable(int size) : table(size) {}

void insert(const Key& key, const Value& value) {
int index = hashFunction(key);

for (const auto& pair : table[index]) {
if (pair.first == key) {
return; // Key already exists, update the value
}
}

table[index].emplace_back(key, value);
}

bool contains(const Key& key) const {
int index = hashFunction(key);

for (const auto& pair : table[index]) {
if (pair.first == key) {
return true;
}
}

return false;
}

const Value& get(const Key& key) const {
int index = hashFunction(key);

for (const auto& pair : table[index]) {
if (pair.first == key) {
return pair.second;
}
}

}

void remove(const Key& key) {
int index = hashFunction(key);

for (

auto it = table[index].begin(); it != table[index].end(); ++it) {
if (it->first == key) {
table[index].erase(it);
return;
}
}
}

private:
std::vector<std::list<std::pair<Key, Value>>> table;

int hashFunction(const Key& key) const {
// Custom hash function implementation
return std::hash<Key>{}(key) % table.size();
}
};``````

### 5. Implement a LRU (Least Recently Used) cache using hash tables.

C++
``````#include <unordered_map>
#include <list>

template<typename Key, typename Value>
class LRUCache {
public:
explicit LRUCache(int capacity) : capacity(capacity) {}

Value get(const Key& key) {
if (cacheMap.find(key) == cacheMap.end()) {
}

// Move accessed key-value pair to the front of the list (indicating most recently used)
cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
return cacheMap[key]->second;
}

void put(const Key& key, const Value& value) {
if (cacheMap.find(key) != cacheMap.end()) {
// Key already exists, update the value and move the pair to the front
cacheMap[key]->second = value;
cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
} else {
// Insert a new key-value pair
if (cacheMap.size() == capacity) {
// Remove the least recently used key-value pair from the cache
cacheMap.erase(cacheList.back().first);
cacheList.pop_back();
}

// Insert the new key-value pair to the front of the list
cacheList.emplace_front(key, value);
cacheMap[key] = cacheList.begin();
}
}

private:
int capacity;
std::unordered_map<Key, typename std::list<std::pair<Key, Value>>::iterator> cacheMap;
std::list<std::pair<Key, Value>> cacheList;
};``````

### 6. Write a program to find all the duplicates in an array using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>

void findDuplicates(const std::vector<int>& nums) {
std::unordered_map<int, int> countMap;

for (int num : nums) {
countMap[num]++;
}

std::cout << "Duplicate elements: ";
for (const auto& pair : countMap) {
if (pair.second > 1) {
std::cout << pair.first << " ";
}
}
std::cout << std::endl;
}

int main() {
std::vector<int> nums = {1, 2, 3, 4, 5, 2, 3, 4, 7};
findDuplicates(nums);

return 0;
}``````

### 7. Write a program to count the frequency of elements in an array using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>

void countFrequency(const std::vector<int>& nums) {
std::unordered_map<int, int> countMap;

for (int num : nums) {
countMap[num]++;
}

std::cout << "Element  Frequency" << std::endl;
for (const auto& pair : countMap) {
std::cout << pair.first << "         " << pair.second << std::endl;
}
}

int main() {
std::vector<int> nums = {1, 2, 3, 4, 5, 2, 3, 4, 7};
countFrequency(nums);

return 0;
}``````

### 8. Write a program to find the intersection of two arrays using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>

std::vector<int> findIntersection(const std::vector<int>& nums1, const std::vector<int>& nums2) {
std::unordered_map<int, bool> map;
std::vector<int> intersection;

// Store elements of nums1 in the hash table
for (int num : nums1) {
map[num] = true;
}

// Check if elements in nums2 are present in the hash table
for (int num : nums2) {
if (map[num]) {
intersection.push_back(num);
map[num] = false; // Mark the element as visited
}
}

return intersection;
}

int main() {
std::vector<int> nums1 = {1, 2, 3, 4, 5};
std::vector<int> nums2 = {4, 5, 6, 7};
std::vector<int> intersection = findIntersection(nums1, nums2);

std::cout << "Intersection: ";
for (int num : intersection) {
std::cout << num << " ";
}
std::cout << std::endl;

return 0;
}``````

### 9. Write a function to find the longest substring without repeating characters using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <string>

std::string findLongestSubstringWithoutRepeatingChars(const std::string& str) {
std::unordered_map<char, int> charIndex;
int start = 0;
int maxLength = 0;
int maxStart = 0;

for (int i = 0; i < str.length(); i++) {

if (charIndex.find(str[i]) != charIndex.end() && charIndex[str[i]] >= start) {
start = charIndex[str[i]] + 1;
}
charIndex[str[i]] = i;

if (i - start + 1 > maxLength) {
maxLength = i - start + 1;
maxStart = start;
}
}

return str.substr(maxStart, maxLength);
}

int main() {
std::string str = "abcabcbb";
std::string longestSubstring = findLongestSubstringWithoutRepeatingChars(str);

std::cout << "Longest substring without repeating characters: " << longestSubstring << std::endl;

return 0;
}``````

### 10. Implement a solution for the two-sum problem using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
std::unordered_map<int, int> map;

for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (map.find(complement) != map.end()) {
return {map[complement], i};
}
map[nums[i]] = i;
}

return {};
}

int main() {
std::vector<int> nums = {2, 7, 11, 15};
int target = 9;
std::vector<int> indices = twoSum(nums, target);

std::cout << "Indices of the two numbers: " << indices << ", " << indices << std::endl;

return 0;
}``````

### 11. Write a program to group anagrams from a list of strings.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

std::vector<std::vector<std::string>> groupAnagrams(const std::vector<std::string>& strs) {
std::unordered_map<std::string, std::vector<std::string>> anagramGroups;

for (const std::string& str : strs) {
std::string sortedStr = str;
std::sort(sortedStr.begin(), sortedStr.end());

anagramGroups[sortedStr].push_back(str);
}

std::vector<std::vector<std::string>> result;
for (const auto& pair : anagramGroups) {
result.push_back(pair.second);
}

return result;
}

int main() {
std::vector<std::string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
std::vector<std::vector<std::string>> anagramGroups = groupAnagrams(strs);

std::cout << "Anagram groups:" << std::endl;
for (const auto& group : anagramGroups) {
for (const std::string& str : group) {
std::cout << str << " ";
}
std::cout << std::endl;
}

return 0;
}``````

### 12. Write a function to check if a string contains all unique characters using a hash table.

C++
``````#include <iostream>
#include <unordered_set>
#include <string>

bool hasUniqueCharacters(const std::string& str) {
std::unordered_set<char> charSet;

for (char ch : str) {
if (charSet.find(ch) != charSet.end()) {
return false;
}
charSet.insert(ch);
}

return true;
}

int main() {
std::string str = "abcdefg";
bool unique = hasUniqueCharacters(str);

std::cout << "String has unique characters: " << (unique ? "true" : "false") << std::endl;

return 0;
}``````

### 13. Write a program to find the majority element in an array using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>

int findMajorityElement(const std::vector<int>& nums) {
std::unordered_map<int, int> countMap;

for (int num : nums) {
countMap[num]++;
if (countMap[num] > nums.size() / 2) {
return num;
}
}

return -1; // No majority element
}

int main() {
std::vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
int majorityElement = findMajorityElement(nums);

if (majorityElement != -1) {
std::cout << "Majority element: " << majorityElement << std::endl;
} else {
std::cout << "No majority element found." << std::endl;
}

return 0;
}``````

### 14. Implement a function that checks if a pattern matches with a string with/without consistent mapping of characters using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <string>

bool patternMatchesString(const std::string& pattern, const std::string& str) {
std::unordered_map<char, std::string> patternToStr;
std::unordered_map<std

::string, char> strToPattern;

int len = pattern.length();
int i = 0;

for (char ch : pattern) {
std::string substr = "";
while (i < str.length() && str[i] != ' ') {
substr += str[i];
i++;
}

if (patternToStr.find(ch) != patternToStr.end() && patternToStr[ch] != substr) {
return false;
}

if (strToPattern.find(substr) != strToPattern.end() && strToPattern[substr] != ch) {
return false;
}

patternToStr[ch] = substr;
strToPattern[substr] = ch;
i++;
}

return i == str.length() + 1;
}

int main() {
std::string pattern = "abba";
std::string str = "dog cat cat dog";
bool matches = patternMatchesString(pattern, str);

std::cout << "Pattern matches string: " << (matches ? "true" : "false") << std::endl;

return 0;
}``````

### 15. Write a function to check if a string can be formed from another string by at most one swap using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <string>

bool isOneSwapAway(const std::string& str1, const std::string& str2) {
if (str1.length() != str2.length()) {
return false;
}

int len = str1.length();
int diffCount = 0;
std::unordered_map<char, int> charCount;

for (int i = 0; i < len; i++) {
if (str1[i] != str2[i]) {
diffCount++;

if (diffCount > 2) {
return false;
}

charCount[str1[i]]++;
charCount[str2[i]]--;
}
}

if (diffCount == 0) {
return true; // Strings are identical
}

if (diffCount == 2) {
for (const auto& pair : charCount) {
if (pair.second != 0) {
return false;
}
}
return true;
}

return false;
}

int main() {
std::string str1 = "abc";
std::string str2 = "bac";
bool oneSwapAway = isOneSwapAway(str1, str2);

std::cout << "Strings are one swap away: " << (oneSwapAway ? "true" : "false") << std::endl;

return 0;
}``````

### 16. Write a function to find the longest consecutive sequence in an unsorted array using a hash table.

C++
``````#include <iostream>
#include <unordered_set>
#include <vector>

int longestConsecutiveSequence(const std::vector<int>& nums) {
std::unordered_set<int> numSet;
for (int num : nums) {
numSet.insert(num);
}

int maxLength = 0;

for (int num : nums) {
if (numSet.find(num - 1) == numSet.end()) {  // Check if current number is the start of a sequence
int currentNum = num;
int currentLength = 1;

while (numSet.find(currentNum + 1) != numSet.end()) {  // Increment currentNum and increase currentLength until the next number is not found
currentNum++;
currentLength++;
}

maxLength = std::max(maxLength, currentLength);  // Update maxLength if currentLength is greater
}
}

return maxLength;
}

int main() {
std::vector<int> nums = {100, 4, 200, 1, 3, 2};
int length = longestConsecutiveSequence(nums);

std::cout << "Length of the longest consecutive sequence: " << length << std::endl;

return 0;
}``````

### 17. Write a function that returns the first recurring character in a string using a hash table.

C++
``````#include <iostream>
#include <unordered_set>
#include <string>

char firstRecurringCharacter(const std::string& str) {
std::unordered_set<char> charSet;

for (char ch : str) {
if (charSet.find(ch) != charSet.end()) {
return ch;
}
charSet.insert(ch);
}

return '\0';  // If no recurring character is found
}

int main() {
std::string str = "abcdefgha";
char recurringChar = firstRecurringCharacter(str);

if (recurringChar != '\0') {
std::cout << "First recurring character: " << recurringChar << std::endl;
} else {
std::cout << "No recurring character found." << std::endl;
}

return 0;
}``````

### 18. Write a function to find the longest palindrome that can be built from a string using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <string>

int longestPalindrome(const std::string& str) {
std::unordered_map<char, int> charCount;

for (char ch : str) {
charCount[ch]++;
}

int maxLength = 0;
bool hasOddCount = false;

for (const auto& pair : charCount) {
if (pair.second % 2 == 0) {
maxLength += pair.second;
} else {
maxLength += pair.second - 1;
hasOddCount = true;
}
}

if (hasOddCount) {
maxLength++;  // Add one character with an odd count to the palindrome
}

return maxLength;
}

int main() {
std::string str = "abccccdd";
int length = longestPalindrome(str);

std::cout << "Length of the longest palindrome: " << length << std::endl;

return 0;
}``````

### 19. Write a function to find the common elements in three sorted arrays using a hash table.

C++
``````#include <iostream>
#include <unordered_set>
#include <vector>

std::vector<int> findCommonElements(const std::vector<int>& nums1, const std::vector<int>& nums2, const std::vector<int>& nums3) {
std::unordered_set<int> commonElements;

std::unordered_set<int> set1(nums1.begin(), nums1.end());

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

std::unordered_set<int> set2(commonElements.begin(), commonElements.end());

std::vector<int> result;

for (int num : nums3) {
if (set2.find(num) != set2.end()) {
result.push_back(num);
}
}

return result;
}

int main() {
std::vector<int> nums1 = {1, 3, 4, 6, 7};
std::vector<int> nums2 = {2, 3, 6, 8};
std::vector<int> nums3 = {3, 6, 9};

std::vector<int> commonElements = findCommonElements(nums1, nums2, nums3);

std::cout << "Common elements: ";
for (int num : commonElements) {
std::cout << num << " ";
}
std::cout << std::endl;

return 0;
}``````

### 20. Write a function to check if a given array contains any duplicates within k distance from each other using a hash table.

C++
``````#include <iostream>
#include <unordered_set>
#include <vector>

bool containsNearbyDuplicates(const std::vector<int>& nums, int k) {
std::unordered_set<int> numSet;

for (int i = 0; i < nums.size(); i++) {
if (i > k) {
numSet.erase(nums[i - k - 1]);  // Remove the element that is outside the window
}

if (numSet.find(nums[i]) != numSet.end()) {
return true;
}

numSet.insert(nums[i]);
}

return false;
}

int main() {
std::vector<int> nums = {1, 2, 3, 1, 2, 3};
int k = 2;
bool containsDuplicates = containsNearbyDuplicates(nums, k);

std::cout << "Array contains duplicates within " << k << " distance: " << (containsDuplicates ? "true" : "false") << std::endl;

return 0;
}``````

### 21. Implement a hash set from scratch.

C++
``````#include <iostream>
#include <vector>
#include <list>

class HashSet {
private:
std::vector<std::list<int>> buckets;
int numBuckets;

int hashFunction(int key) {
return key % numBuckets;
}

public:
HashSet(int numBuckets) : numBuckets(numBuckets) {
buckets.resize(numBuckets);
}

void insert(int key) {
int index = hashFunction(key);
std::list<int>& bucket = buckets[index];

if (!contains(key)) {
bucket.push_back(key);
}
}

void remove(int key) {
int index = hashFunction(key);
std::list<int>& bucket = buckets[index];

bucket.remove(key);
}

bool contains(int key) {
int index = hashFunction(key);
std::list<int>& bucket = buckets[index];

for (int num : bucket) {
if (num == key) {
return true;
}
}

return false;
}
};

int main() {
HashSet hashSet(5);
hashSet.insert(1);
hashSet.insert(2);
hashSet.insert(3);
hashSet.insert(2);

std::cout << "HashSet contains 2: " << (hashSet.contains(2) ? "true" : "false") << std::endl;

hashSet.remove(2);

std::cout << "HashSet contains 2: " << (hashSet.contains(2) ? "true" : "false") << std::endl;

return 0;
}``````

### 22. Implement a hash map from scratch.

C++
``````#include <iostream>
#include <vector>
#include <list>
#include <utility>

class HashMap {
private:
std::vector<std::list<std::pair<int, int>>> buckets;
int numBuckets;

int hashFunction(int key) {
return key % numBuckets;
}

public:
HashMap(int numBuckets) : numBuckets(numBuckets) {
buckets.resize(numBuckets);
}

void put(int key, int value) {
int index = hashFunction(key);
std::list<std::pair<int, int>>& bucket = buckets[index];

for (auto& pair : bucket) {
if (pair.first == key) {
pair.second = value;
return;
}
}

bucket.push_back(std::make_pair(key, value));
}

int get(int key) {
int index = hashFunction(key);
std::list<std::pair<int, int>>& bucket = buckets[index];

for (const auto& pair : bucket) {
if (pair.first == key) {
return pair.second;
}
}

}

void remove(int key) {
int index = hashFunction(key);
std::list<std::pair<int, int>>& bucket = buckets[index];

for (auto it = bucket.begin(); it != bucket.end(); it++) {
if (it->first == key) {
bucket.erase(it);
return;
}
}
}
};

int main() {
HashMap hashMap(5);
hashMap.put(1, 100);
hashMap.put(2, 200);
hashMap.put(3, 300);

std::cout << "Value for key 2: " << hashMap.get(2) << std::endl;

hashMap.remove(2);

std::cout << "Value for key 2: " << hashMap.get(2) << std::endl;

return 0;
}``````

### 23. Write a function to check if two arrays are disjoint using a hash table.

C++
``````#include <iostream>
#include <unordered_set>
#include <vector>

bool areArraysDisjoint(const std::vector<int>& nums1, const std::vector<int>& nums2) {
std::unordered_set<int> numSet(nums1.begin(), nums1.end());

for (int num : nums2) {
if (numSet.find(num) != numSet.end()) {
return false;
}
}

return true;
}

int main() {
std::vector<int> nums1 = {1, 2, 3, 4};
std::vector<int> nums2 = {5, 6, 7};

bool isDisjoint = areArraysDisjoint(nums1, nums2);

std::cout << "Arrays are disjoint: " << (isDisjoint ? "true" : "false") << std::

endl;

return 0;
}``````

### 24. Write a function to print a vertical order traversal of a binary tree using a hash table.

C++
``````#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;

TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

void verticalOrderTraversal(TreeNode* root) {
if (!root) {
return;
}

std::map<int, std::vector<int>> verticalOrderMap;
std::queue<std::pair<TreeNode*, int>> nodeQueue;

nodeQueue.push(std::make_pair(root, 0));

while (!nodeQueue.empty()) {
TreeNode* node = nodeQueue.front().first;
int column = nodeQueue.front().second;
nodeQueue.pop();

verticalOrderMap[column].push_back(node->val);

if (node->left) {
nodeQueue.push(std::make_pair(node->left, column - 1));
}

if (node->right) {
nodeQueue.push(std::make_pair(node->right, column + 1));
}
}

for (auto& pair : verticalOrderMap) {
std::cout << "Column " << pair.first << ": ";
for (int value : pair.second) {
std::cout << value << " ";
}
std::cout << std::endl;
}
}

int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);

verticalOrderTraversal(root);

return 0;
}``````

### 25. Write a function to check if an array can be divided into pairs whose sum is divisible by K using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>

bool canDivideIntoPairs(const std::vector<int>& nums, int k) {
if (nums.size() % 2 != 0) {
return false;  // Array size must be even to form pairs
}

std::unordered_map<int, int> remainderCount;

for (int num : nums) {
int remainder = num % k;
remainderCount[remainder]++;
}

for (const auto& pair : remainderCount) {
int remainder = pair.first;
int count = pair.second;

if (remainder == 0) {
if (count % 2 != 0) {
return false;  // If the remainder is 0, there must be an even count to form pairs
}
} else if (2 * remainder == k) {
if (count % 2 != 0) {
return false;  // If the remainder is half of k, there must be an even count to form pairs
}
} else {
int complement = k - remainder;
if (remainderCount[complement] != count) {
return false;  // If the remainder and its complement have different counts, pairs cannot be formed
}
}
}

return true;
}

int main() {
std::vector<int> nums = {1, 2, 3, 4, 5, 6};
int k = 3;
bool canFormPairs =

canDivideIntoPairs(nums, k);

std::cout << "Array can be divided into pairs with sum divisible by " << k << ": " << (canFormPairs ? "true" : "false") << std::endl;

return 0;
}``````

### 26. Write a function to check if two lists are circularly identical using a hash table.

C++
``````#include <iostream>
#include <unordered_set>
#include <vector>

bool areListsCircularlyIdentical(const std::vector<int>& list1, const std::vector<int>& list2) {
if (list1.size() != list2.size()) {
return false;
}

std::unordered_set<int> numSet;

for (int i = 0; i < list1.size(); i++) {
numSet.insert(list1[i]);
}

for (int i = 0; i < list2.size(); i++) {
if (numSet.find(list2[i]) == numSet.end()) {
return false;
}
}

return true;
}

int main() {
std::vector<int> list1 = {1, 2, 3, 4, 5};
std::vector<int> list2 = {4, 5, 1, 2, 3};

bool areIdentical = areListsCircularlyIdentical(list1, list2);

std::cout << "Lists are circularly identical: " << (areIdentical ? "true" : "false") << std::endl;

return 0;
}``````

### 27. Write a function to count distinct elements in every window of size k in the array using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>

void countDistinctElements(const std::vector<int>& nums, int k) {
std::unordered_map<int, int> elementCount;

for (int i = 0; i < k; i++) {
elementCount[nums[i]]++;
}

std::cout << "Distinct elements in window [0, " << k - 1 << "]: " << elementCount.size() << std::endl;

for (int i = k; i < nums.size(); i++) {
elementCount[nums[i - k]]--;
if (elementCount[nums[i - k]] == 0) {
elementCount.erase(nums[i - k]);
}
elementCount[nums[i]]++;
std::cout << "Distinct elements in window [" << i - k + 1 << ", " << i << "]: " << elementCount.size() << std::endl;
}
}

int main() {
std::vector<int> nums = {1, 2, 1, 3, 4, 2, 3};
int k = 4;

countDistinctElements(nums, k);

return 0;
}``````

### 28. Write a function to print all subarrays in the array which has sum 0 using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>

void printZeroSumSubarrays(const std::vector<int>& nums) {
std::unordered_map<int, std::vector<int>> sumIndices;
int sum = 0;

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

if (sum == 0) {
std::cout << "Subarray [0, " << i << "]" << std::endl;
}

if (sumIndices

.find(sum) != sumIndices.end()) {
for (int index : sumIndices[sum]) {
std::cout << "Subarray [" << index + 1 << ", " << i << "]" << std::endl;
}
}

sumIndices[sum].push_back(i);
}
}

int main() {
std::vector<int> nums = {4, 2, -3, -1, 0, 4};
printZeroSumSubarrays(nums);

return 0;
}``````

### 29. Write a function to find the length of the longest subarray with an equal number of 0s and 1s using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>

int findMaxLength(const std::vector<int>& nums) {
std::unordered_map<int, int> sumIndices;
int maxLength = 0;
int sum = 0;

for (int i = 0; i < nums.size(); i++) {
sum += nums[i] == 0 ? -1 : 1;

if (sum == 0) {
maxLength = i + 1;
}

if (sumIndices.find(sum) != sumIndices.end()) {
maxLength = std::max(maxLength, i - sumIndices[sum]);
} else {
sumIndices[sum] = i;
}
}

return maxLength;
}

int main() {
std::vector<int> nums = {0, 1, 0, 1, 1, 0, 1};
int length = findMaxLength(nums);

std::cout << "Length of the longest subarray with equal 0s and 1s: " << length << std::endl;

return 0;
}``````

### 30. Write a function to count the number of subarrays with a given XOR using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>

int countSubarraysWithXOR(const std::vector<int>& nums, int targetXOR) {
std::unordered_map<int, int> xorCount;
int count = 0;
int prefixXOR = 0;

for (int num : nums) {
prefixXOR ^= num;

if (prefixXOR == targetXOR) {
count++;
}

if (xorCount.find(prefixXOR ^ targetXOR) != xorCount.end()) {
count += xorCount[prefixXOR ^ targetXOR];
}

xorCount[prefixXOR]++;
}

return count;
}

int main() {
std::vector<int> nums = {4, 2, 2, 6, 4};
int targetXOR = 6;

int count = countSubarraysWithXOR(nums, targetXOR);

std::cout << "Number of subarrays with XOR " << targetXOR << ": " << count << std::endl;

return 0;
}``````

### 31. Write a function to check if two given strings are isomorphic to each other using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <string>

bool areStringsIsomorphic(const std::string& str1, const std::string& str2) {
if (str1.length() != str2.length()) {
return false;
}

std::unordered_map<char, char> charMap;
std::unordered_map<char, bool> usedChars;

for (int i = 0; i < str

1.length(); i++) {
char ch1 = str1[i];
char ch2 = str2[i];

if (charMap.find(ch1) != charMap.end()) {
if (charMap[ch1] != ch2) {
return false;
}
} else {
if (usedChars[ch2]) {
return false;
}

charMap[ch1] = ch2;
usedChars[ch2] = true;
}
}

return true;
}

int main() {
std::string str1 = "egg";

bool isIsomorphic = areStringsIsomorphic(str1, str2);

std::cout << "Strings are isomorphic: " << (isIsomorphic ? "true" : "false") << std::endl;

return 0;
}``````

### 32. Write a function to find four elements a, b, c, and d in an array such that a + b = c + d using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>

bool hasEqualSumPair(const std::vector<int>& nums) {
std::unordered_map<int, std::pair<int, int>> sumPair;

for (int i = 0; i < nums.size() - 1; i++) {
for (int j = i + 1; j < nums.size(); j++) {
int sum = nums[i] + nums[j];

if (sumPair.find(sum) != sumPair.end()) {
std::pair<int, int> pair = sumPair[sum];
if (pair.first != i && pair.first != j && pair.second != i && pair.second != j) {
return true;
}
} else {
sumPair[sum] = std::make_pair(i, j);
}
}
}

return false;
}

int main() {
std::vector<int> nums = {3, 4, 7, 1, 2, 9, 8};

bool hasPair = hasEqualSumPair(nums);

std::cout << "Array has four elements with equal sum pair: " << (hasPair ? "true" : "false") << std::endl;

return 0;
}``````

### 33. Implement a function to find the shortest subarray with a sum greater than a given value using a hash table.

C++
``````#include <iostream>
#include <vector>
#include <unordered_map>

int shortestSubarrayWithSum(const std::vector<int>& nums, int targetSum) {
std::unordered_map<int, int> prefixSumIndices;
int sum = 0;
int minLength = INT_MAX;

prefixSumIndices = -1;

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

if (prefixSumIndices.find(sum - targetSum) != prefixSumIndices.end()) {
int startIndex = prefixSumIndices[sum - targetSum];
int subarrayLength = i - startIndex;
minLength = std::min(minLength, subarrayLength);
}

prefixSumIndices[sum] = i;
}

return minLength == INT_MAX ? -1 : minLength;
}

int main() {
std::vector<int> nums = {2, 3, 1, 2, 4, 3};
int targetSum = 7;

int length = shortestSubarrayWithSum(nums, targetSum);

std::cout << "Length of the shortest subarray with

sum greater than " << targetSum << ": ";
if (length == -1) {
} else {
std::cout << length << std::endl;
}

return 0;
}``````

### 34. Write a program to implement a phonebook using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <string>

class PhoneBook {
private:
std::unordered_map<std::string, std::string> contacts;

public:
void addContact(const std::string& name, const std::string& phoneNumber) {
contacts[name] = phoneNumber;
}

void removeContact(const std::string& name) {
contacts.erase(name);
}

std::string getPhoneNumber(const std::string& name) {
if (contacts.find(name) != contacts.end()) {
return contacts[name];
}
}
};

int main() {
PhoneBook phoneBook;

std::cout << "John's phone number: " << phoneBook.getPhoneNumber("John") << std::endl;
std::cout << "Jane's phone number: " << phoneBook.getPhoneNumber("Jane") << std::endl;
std::cout << "Alice's phone number: " << phoneBook.getPhoneNumber("Alice") << std::endl;

phoneBook.removeContact("Jane");

std::cout << "Jane's phone number: " << phoneBook.getPhoneNumber("Jane") << std::endl;

return 0;
}``````

### 35. Write a function to check if there is a subarray with a 0 sum in a given array using a hash table.

C++
``````#include <iostream>
#include <unordered_set>
#include <vector>

bool hasZeroSumSubarray(const std::vector<int>& nums) {
std::unordered_set<int> sumSet;
int sum = 0;

for (int num : nums) {
sum += num;

if (sum == 0 || sumSet.find(sum) != sumSet.end()) {
return true;
}

sumSet.insert(sum);
}

return false;
}

int main() {
std::vector<int> nums = {4, 2, -3, -1, 0, 4};

bool hasZeroSum = hasZeroSumSubarray(nums);

std::cout << "Array has a subarray with a 0 sum: " << (hasZeroSum ? "true" : "false") << std::endl;

return 0;
}``````

### 36. Implement a data structure that supports insert, delete, and getRandom in O(1) time complexity using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <vector>
#include <random>

class RandomizedSet {
private:
std::unordered_map<int, int> valueIndices;
std::vector<int> values;

public:
bool insert(int val) {
if (valueIndices.find(val) != valueIndices.end()) {
return false;  // Value already exists
}

valueIndices[val] = values.size();
values.push_back(val);

return true;
}

bool remove(int val) {
if (valueIndices.find(val) == valueIndices.end()) {
return false;  // Value does not exist
}

int index

= valueIndices[val];
int lastValue = values.back();

valueIndices[lastValue] = index;
values[index] = lastValue;

values.pop_back();
valueIndices.erase(val);

return true;
}

int getRandom() {
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<int> dis(0, values.size() - 1);

int randomIndex = dis(gen);

return values[randomIndex];
}
};

int main() {
RandomizedSet randomizedSet;
randomizedSet.insert(1);
randomizedSet.insert(2);
randomizedSet.insert(3);

std::cout << "Random element: " << randomizedSet.getRandom() << std::endl;

randomizedSet.remove(2);

std::cout << "Random element: " << randomizedSet.getRandom() << std::endl;

return 0;
}``````

### 37. Implement a function to find all pairs such that a^b = b^a in two arrays using a hash table.

C++
``````#include <iostream>
#include <unordered_set>
#include <vector>

std::vector<std::pair<int, int>> findPairsWithEqualXOR(const std::vector<int>& nums1, const std::vector<int>& nums2) {
std::unordered_set<int> numSet(nums1.begin(), nums1.end());

std::vector<std::pair<int, int>> result;

for (int num1 : nums1) {
int targetXOR = num1;

for (int num2 : nums2) {
int complement = targetXOR ^ num2;

if (numSet.find(complement) != numSet.end()) {
result.push_back(std::make_pair(num1, num2));
}
}
}

return result;
}

int main() {
std::vector<int> nums1 = {1, 2, 3, 4};
std::vector<int> nums2 = {2, 1, 4, 5};

std::vector<std::pair<int, int>> pairs = findPairsWithEqualXOR(nums1, nums2);

std::cout << "Pairs with equal XOR: ";
for (const auto& pair : pairs) {
std::cout << "(" << pair.first << ", " << pair.second << ") ";
}
std::cout << std::endl;

return 0;
}``````

### 38. Write a program to find the smallest window that contains all distinct characters of a string itself using a hash table.

C++
``````#include <iostream>
#include <unordered_map>
#include <string>

std::string findSmallestWindow(const std::string& str) {
std::unordered_map<char, int> charCount;
int distinctCount = 0;

for (char ch : str) {
if (charCount[ch] == 0) {
distinctCount++;
}
charCount[ch]++;
}

int minLength = INT_MAX;
int windowStart = 0;
int windowEnd = 0;
int count = 0;
std::string smallestWindow;

while (windowEnd < str.length()) {
char ch = str[windowEnd];

if (charCount[ch] == 0) {
windowEnd++;
continue;
}

charCount[ch]--;
if (charCount[ch] == 0) {
count++;
}

if (count == distinctCount) {
while (count == distinctCount) {
char startCh = str[windowStart];

if (charCount[startCh] == 0) {
windowStart++;
continue;
}

if (windowEnd - windowStart + 1 < minLength) {
minLength = windowEnd - windowStart + 1;
smallestWindow = str.substr(windowStart, minLength);
}

charCount[startCh]++;
if (charCount[startCh] > 0) {
count--;
}

windowStart++;
}
}

windowEnd++;
}

return smallestWindow;
}

int main() {
std::string str = "aabcbcdbca";
std::string window = findSmallestWindow(str);

std::cout << "Smallest window: " << window << std::endl;

return 0;
}``````

### 39. Write a function to find if there is a pair with a given sum in a Binary Search Tree (BST) using a hash table.

C++
``````#include <iostream>
#include <unordered_set>

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;

TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

bool findPairWithSum(TreeNode* root, int targetSum, std::unordered_set<int>& numSet) {
if (!root) {
return false;
}

if (numSet.find(targetSum - root->val) != numSet.end()) {
return true;
}

numSet.insert(root->val);

return findPairWithSum(root->left, targetSum, numSet) || findPairWithSum(root->right, targetSum, numSet);
}

bool findPair(TreeNode* root, int targetSum) {
std::unordered_set<int> numSet;

return findPairWithSum(root, targetSum, numSet);
}

int main() {
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(3);
root->right = new TreeNode(6);
root->left->left = new TreeNode(2);
root->left->right = new TreeNode(4);
root->right->right = new TreeNode(7);

int targetSum = 9;
bool hasPair = findPair(root, targetSum);

std::cout << "Pair with sum " << targetSum << " exists in the BST: " << (hasPair ? "true" : "false") << std::endl;

return 0;
}``````

### 40. Implement a solution to solve the Longest Substring with At Most K Distinct Characters problem using a hash table.

C++
``````#include <iostream>
#include <unordered_map>

int longestSubstringWithKDistinctCharacters(const std::string& str, int k) {
std::unordered_map<char, int> charCount;
int maxLength = 0;
int distinctCount = 0;
int windowStart = 0;

for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
char ch = str[windowEnd];

if (charCount[ch] == 0) {
distinctCount++;
}
charCount[ch]++;

while (distinctCount > k) {
char startCh = str[windowStart];

charCount[startCh]--;
if (charCount[startCh] == 0) {
distinctCount--;
}

windowStart++;
}

maxLength = std::max(maxLength, windowEnd - windowStart + 1);
}

return maxLength;
}

int main() {
std::string str = "eceba";
int k = 2;

int length = longestSubstringWithKDistinctCharacters(str, k);

std::cout

<< "Length of the longest substring with at most " << k << " distinct characters: " << length << std::endl;

return 0;
}``````

## MCQ Questions

### 1. What is a hash table?

a) A data structure that stores data in a sorted manner
b) A data structure that stores data in an unordered manner
c) A data structure that stores data in a binary tree
d) A data structure that stores data in a linked list

Answer: b) A data structure that stores data in an unordered manner

a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)

### 3. What is a hash function?

a) A function that maps data to a unique index in the hash table
b) A function that sorts data in ascending order
c) A function that searches for data in a hash table
d) A function that calculates the average value of data in a hash table

Answer: a) A function that maps data to a unique index in the hash table

### 4. What is collision in the context of hash tables?

a) When two different keys produce the same hash value
b) When the hash table is full and cannot accommodate new elements
c) When the hash function fails to generate a unique index
d) When the data in the hash table is sorted in descending order

Answer: a) When two different keys produce the same hash value

### 5. How are collisions resolved in a hash table?

a) By discarding the colliding elements
b) By increasing the size of the hash table
c) By rehashing the colliding elements
d) By sorting the colliding elements

Answer: c) By rehashing the colliding elements

a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)

a) Stack
b) Queue
c) Array

### 8. What is the advantage of using a hash table over other data structures?

a) Constant time complexity for all operations
b) Efficient sorting of data
c) Automatic resizing of the data structure
d) Support for recursive operations

Answer: a) Constant time complexity for all operations

### 9. Which of the following operations are typically supported by a hash table?

a) Insertion, deletion, and search
b) Sorting and merging
c) Graph traversal
d) Recursive operations

Answer: a) Insertion, deletion, and search

a) O(1)
b) O(n)
c) O(log n)
d) O(n^2)

### 11. Which of the following is not a common application of hash tables?

a) Caching
b) Symbol table implementation
c) Graph traversal
d) Spell checking

a) Stack
b) Queue
c) Array

### 13. Which of the following is not a requirement for a good hash function?

a) It should always generate a unique index
b) It should evenly distribute the elements across the hash table
c) It should be efficient to compute
d) It should minimize collisions

Answer: a) It should always generate a unique index

### 14. Which of the following is a disadvantage of using a hash table?

a) Slow search time
b) Limited storage capacity
c) High memory usage
d) Inefficient for large datasets

### 15. How does the load factor affect the performance of a hash table?

c) Load factor does not affect search times
d) Load factor only affects insertion and deletion operations

a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)

### 17. Which collision resolution technique uses linked lists to handle collisions?

a) Linear probing
c) Chaining
d) Double hashing

### 18. What is the purpose of a hash code in a hash table?

a) To determine the load factor of the hash table
b) To calculate the index for storing and retrieving elements
c) To sort the elements in the hash table
d) To handle collisions in the hash table

Answer: b) To calculate the index for storing and retrieving elements

### 19. Which of the following is an example of a perfect hash function?

a) f(x) = x
b) f(x) = x + 1
c) f(x) = x mod 10
d) f(x) = floor(sqrt(x))

Answer: c) f(x) = x mod 10

### 20. Which of the following is a common application of a hash table?

b) Depth-first search algorithm
c) Dijkstra’s algorithm
d) Memoization

a) Insertion
b) Deletion
c) Sorting
d) Search

a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)

### 23. Which collision resolution technique rehashes the key with a different hash function if a collision occurs?

a) Linear probing
c) Chaining
d) Double hashing

a) Stack
b) Queue
c) Array

### 25. What is the advantage of using open-addressing collision resolution over chaining?

a) Reduced memory usage
b) Faster search times
c) Easier implementation
d) Less susceptible to collisions

### 26. Which of the following is a disadvantage of using open-addressing collision resolution?

a) Slower search times
b) Limited storage capacity
c) Higher memory usage
d) Difficulty in handling collisions

### 27. What happens when the load factor of a hash table exceeds a certain threshold?

a) The hash table is resized to accommodate more elements
b) The hash table is emptied and all elements are rehashed
c) The hash table becomes read-only and no more elements can be inserted
d) The hash table collapses and all elements are lost

Answer: a) The hash table is resized to accommodate more elements

### 28. Which of the following is a commonly used hash function for string keys?

a) Identity function
b) XOR-based hash function

c) Fibonacci hash function
d) MD5 hash function

### 29. Which of the following is not a property of a good hash function?

a) Deterministic
b) Fast computation
c) Collisions are guaranteed
d) Uniform distribution of hash values