Hashing Interview Questions and Answers

C++, Java / July 17, 2022 / sumitsuthar94 / 0

Hashing is an important programming concept that is used in many areas including data storage and encryption. A good knowledge of hashing algorithms and data structures is crucial for any programmer looking to tackle larger projects. This article will provide an overview of the most commonly asked hashing interview questions and answers.

Following are famous hashing interview questions and answers:

Palindrome Substring Queries

Palindrome substring queries are an important concept in hashing. It involves finding the longest palindromic substring within a given string. This technique can be implemented using hashing to store the partial strings in a hash table. A code example for this query is given below:

// Function to return the longest palindromic
// substring
string longestPalindromicSubstring(string str)
{
    // Set the initial longest substring
    int maxLength = 0;
    string longestSubstring;

    // Create a hash set to store all substrings
    unordered_set<string> substrings;

    // Iterate through the string
    for (int i = 0; i < str.length(); i++)
    {
        // Set the current substring
        string subs = str.substr(i, str.length() - i); 

        // Iterate through the substring
        for (int j = 0; j < subs.length(); j++)
        {
            // Store the current substring
            string sub = subs.substr(0, j + 1);

            // Check if the Current substring is palindromic
            if (isPalindrome(sub))
            {
                // Check the length of the palindromic substring
                if (sub.length() > maxLength)
                {
                    maxLength = sub.length();
                    longestSubstring = sub;
                }

                // Store the substring in the hash set
                substrings.insert(sub);
            }
        }
    }

    // Return the longest palindromic substring
    return longestSubstring;
}

The above code uses the hash set to store all substrings and check if they are palindromic. It then compares the maxLength variable with the current length of the palindromic substring to get the longest palindromic substring.

Internal Working of HashMap in Java

The HashMap in Java is an important data structure that supports the insertion, retrieval and removal of elements in an efficient manner. It is implemented using a hash table which stores the key-value pairs and provides constant time complexity for insertion, retrieval and removal of elements. The internal working of the HashMap in Java is as follows:

1. When inserting a new element, the key is hashed using a hash function and the position of the element is calculated using the hash code.
2. The element is then stored in the hash table at the calculated position.
3. When retrieving an element, the key is again hashed using the same hash function and the position is calculated using the hash code.
4. The element is then fetched from the hash table at the calculated position.
5. When removing an element, the key is hashed using the same hash function and the position is calculated using the hash code.
6. The element is then removed from the hash table at the calculated position.

Count the number of subarrays having a given XOR

The problem of counting the number of subarrays having a given XOR can be solved using hashing. This can be implemented using a sliding window technique along with a hash table to store the XOR values of each subarray. A code example for this query is given below:

// Function to count the number of subarrays
// having a given XOR
int countSubarraysXOR(int arr[], int n, int x)
{
    // Initialize result
    int count = 0;

    // Create an empty hash set
    unordered_set<int> s;
    // Insert 0 into set to handle the case when
    // subarray with XOR 0 starts from index 0
    s.insert(0);
    // Initialize prefix XOR
    int pre_xor = 0;
    // Traverse array element
    for (int i = 0; i < n; i++)
    {
        // Calculate prefix xor of current element
        pre_xor = pre_xor ^ arr[i];
        // Check if there exist an element in set
        // with XOR equal to x^pre_xor
        if (s.find(pre_xor^x) != s.end()) 
            count++;
        // Insert current prefix XOR into set
        s.insert(pre_xor);
    }
    return count;
}

The above code uses the sliding window technique and the hash set to store the XOR values of subarrays. It then checks if the XOR of the current prefix XOR and the given XOR matches with any of the XOR values stored in the set, if so it increments the count.

Find whether an array is subset of another array

The problem of finding whether an array is a subset of another array can be solved using hashing. This can be implemented using a hash table to store the elements of the second array and then iterating over the first array to check if all the elements of the first array are present in the second array. A code example for this query is given below:

// Function to check if arr2 is subset of arr1
bool isSubset(int arr1[], int arr2[], int m, int n)
{
    // Create an empty hash set
    unordered_set<int> s; 

    // Store elements of arr1 in the set
    for (int i = 0; i < m; i++)
        s.insert(arr1[i]);
    // Check if all elements of arr2 are present
    // in the set
    for (int i = 0; i < n; i++)
        if (s.find(arr2[i]) == s.end())
            return false;
    return true;
}

The above code uses a hash set to store all the elements of the first array and then iterates over the second array to check if all the elements of the second array are present in the first array. If all the elements of the second array are present in the first array, the function returns true, else it returns false.

Given an array of pairs, find all symmetric pairs in it

The problem of finding all symmetric pairs in an array of pairs can be solved using hashing. This can be implemented by creating a hash table to store the values of all the pairs and then iterating over the hash table to check for symmetric pairs. A code example for this query is given below:

// Function to find all Symmetric pairs in
// an array of pairs
void findSymmetricPairs(int arr[][2], int n)
{
    // Create an empty hashmap
    unordered_map<int, int> m;
    // Insert the first element of each pair
    // in the hashmap
    for (int i = 0; i < n; i++)
        m[arr[i][0]] = arr[i][1];
    // Traverse each pair and search for its
    // symmetric pair
    for (int i = 0; i < n; i++)
    {
        // If a symmetric pair is found, print it
        if (m.find(arr[i][1]) != m.end() &&
                m[arr[i][1]] == arr[i][0])
            cout << "(" << arr[i][0] << ", "
                << arr[i][1] << ")" ;
    }
}

The above code uses a hash table to store the first element of each pair and then iterates over the array to check for a symmetric pair. If a symmetric pair is found, it is printed on the screen.

C++, interview questions, Java