New Hash Tables Interview Questions

#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;
}

#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;
            }
        }
        return -1; // Key not found
    }
};

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

#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)
    ageTable.max_load_factor(0.7);

    // 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
    std::cout << "Current Load Factor: " << ageTable.load_factor() << std::endl;

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

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

    // Check the new load factor after rehashing
    std::cout << "New Load Factor: " << ageTable.load_factor() << std::endl;

    return 0;
}

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

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

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

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

#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;
}

#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;
}

#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;
}

#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];
        }
        return "Not found";
    }

    // 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;
}

#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;
}

#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;
}

#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
}

#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;
}

// 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;
            }
        }

        throw std::out_of_range("Key not found");
    }

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

#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()) {
            return Value{}; // Return default value if key not found
        }

        // 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;
};

#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;
}

#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;
}

#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;
}

#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;
}

#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[0] << ", " << indices[1] << std::endl;

    return 0;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
            }
        }

        return -1;  // If key is not found
    }

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

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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";
    std::string str2 = "add";

    bool isIsomorphic = areStringsIsomorphic(str1, str2);

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

    return 0;
}