Hashing Question List

Palindrome Substring Queries

InterviewBit Imp Problem Set  GeeksForGeek Problem Set   and https://leetcode.com/tag/hash-table/

*** Java HashMap, HashSet. when to use what and how to use them.
HashSet contains only values whereas HashMap contains entry(key and value).

Most of hashing questions are formed in association with String and Array.

  1. HashMap Basic Operations
  2. ****Design a data structure that supports insert, delete, search and getRandom in constant time –  This was asked in Uber. The logic is really great for the use case implementation, especially for gettRandom(). Worth reading the complete article.
    Also available on GeeksForGeeks.
  3. ** Find whether an array is subset of another array OR How to check if two given sets are disjoint?
    Given two arrays: arr1[0..m-1] and arr2[0..n-1]. Find whether arr2[] is a subset of arr1[] or not. Both the arrays are not in sorted order. It may be assumed that elements in both array are distinct. Algo
    1. Brute Force O(n^2)
    2. Sort both the array. Then do a binary search for elements of arr2[] in arr1[]. O(mLogm + nLogm). Here the worst case depends on the worst case of the sort type used.
    3. Sort both the array. Then start comparing the element of both the array. If at anytime, arr1[j] > arr2[i], break; This method is developed on good observation. So check the code.  O(mLogm + nLogn)
    4. Use Hashing. O(n) time and O(n) space complexity.
  4. ** Union and Intersection of two Linked Lists  – Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elements in output lists doesn’t matter. Algo –
    1. Brute Force. O(mn)
    2. Use Sorting. Since these are linked list, use Merge Sort.Linearly scan both sorted lists to get the union and intersection. This step takes O(m + n) time.
    Overall, O(mLogm + nLogn)
    3. Hashing. Put all items of first linked list into hash table. Now start looking up for each element of second list in this table.
    If element is found, move that element to the intersection list.
    If element not found, move it to union list.
    When all items are over in list, add all element of table to hash table to union list.
  5.  **  Link. Given an array A[] and a number x, check for pair in A[] with sum as x.  given an array A[] of n numbers and another number x, determines whether or not there exist two elements in S whose sum is exactly x.
    1. Sorting  – Sort the list. Maintain two pointer, one at start and other at end.  Rest is simple. Keep adding number at both pointer and see if the sum is equal to x, if not then move the pointer accordingly.
    Time Complexity: Depends on what sorting algorithm we use. If we use Merge Sort or Heap Sort then (-)(nlogn) in worst case. If we use Quick Sort then O(n^2) in worst case.
    Auxiliary Space : Again, depends on sorting algorithm. For example auxiliary space is O(n) for merge sort and O(1) for Heap Sort.
    2. Hashing – Save all the number in Hash Table. Now loop through the array. Search for the number, x-a[i] in table. O(n) – time and space.
  6. ** Check if a given array contains duplicate elements within k distance from each other.  Given an unsorted array that may contain duplicates. Also given a number k which is smaller than size of array. Algo
    The idea is to keep adding element to the hash table, but keep only those elements that are within k distance from the current i. If  i>=k,  we remove i-k, ie. a[i-k] position element from the table. This ensures that we are always searching within a distance of k.  This logic can be applied to other problems as well.
  7. Find Itinerary from a given list of tickets.   Algo –
    The idea is to first find the starting point. A starting point would never be on ‘to’ side of a ticket. Once we find the starting point, we can simply traverse the given map to print itinerary in order.
    We make two Hashmap – one to ->from and other, from->to.
    (We can also solve this based on the logic that the destination will appear only once and that too on the from side as it’s mentioned – ‘there is one ticket from every city except final destination’).
    We rarely see problem using hash table. Plus we are using HashMap here – we can search both for keys and value in HashMap. Check different ways to iterate through HashMap here.
    HashSet contains only values whereas HashMap contains entry(key and value).
  8. Find number of Employees Under every Employee Given a dictionary that contains mapping of employee and his manager as a number of (employee, manager) pairs like below.  Question Link. Algo –
    The approach give here is the same as we thought ourself. We reverse the relationship given and count the number for each of the manager. Done.
  9. * Given an array of integers and a number k, write a function that returns true if given array can be divided into pairs such that sum of every pair is divisible by k.
    Link  Complexity: O(n)  Algo –
    When we look at the pair we notice, that if the remainder of the each number of paid is same. So we maintain a hash table and maintain the frequency of remainder of each array element  when divided by k. Now we need to check 3 cases –
    a) Find remainder of current element.
    b) If remainder divides k into two halves, then there must be even occurrences of         it as it forms pair with itself only.
    c) If remainder is 0, then then there must be even occurrences.
    d) Else, number of occurrences of current remainder  must be equal to number of         occurrences of “k -current remainder”.
  10. **** Find four elements a, b, c and d in an array such that a+b = c+d Very important question. So directly copying the pseudo code here. Time Complexity: O(n2)
    Algo

    Loop i = 0 to n-1 :
        Loop j = i + 1 to n-1 :
            calculate sum
            If in hash table any index already exist
                Then print (i, j) and previous pair 
                from hash table  
            Else update hash table
        EndLoop;
    EndLoop;
  11. Given an array of pairs, find all symmetric pairs in it – Algo
    First element of pair is used as key and second element is used as value. The idea is traverse all pairs one by one. For every pair, check if its second element is in hash table. If yes, then compare the first element with value of matched entry of hash table. If the value and the first element match, then we found symmetric pairs. Else, insert first element as key and second element as value.
    Note:  since we will be doing search based on second value, we shd use hashmap as it provides that function.
    when questions specifies that element are given in pair, either consider the input as a 2D array or two 1D array with with pair element i position mapped to i position in second array.
  12. *** Find the largest subarray with 0 sum  Given an array of integers, find length of the largest subarray with sum equals to 0.
    Use Hashing to solve this problem in O(n) time. The idea is to iterate through the array and for every element arr[i], calculate sum of elements form 0 to i (this can simply be done as sum += arr[i]). If the current sum has been seen before, then there is a zero sum array. Hashing is used to store the sum values, so that we can quickly store sum and find out whether the current sum is seen before or not.
    Edge Case: Handle the case where the current element is itself zero. In that case the alone forms the subarray.
    Variation 1: Find the largest subarray with 0 sum  Edge Case specified above is very important in this case as well.
    Variation 2: Print all subarrays with 0 sum
    Need to solve it ourselves.
  13. *** Largest subarray with equal number of 0s and 1s  – Consider all 0 values as -1. The problem now reduces to find out the maximum length subarray with sum = 0 as above.
  14. *** Count distinct elements in every window of size k – Algo 
    Just as we thought. Cool !!! So we create a HashMap which maintains the frequency of each element encountered in the given window and keep updating the window. As we move to the next window we remove the first element from HashMap in previous window or decrease it’s frequency from the HashMap so that we don’t need to calculate the frequency for each window from start – Basically this is the logic here. We also maintain a flag to count the distinct element in HashMap at the moment so that we don’t need to traverse the HashMap everytime for distinct count of each window.
    We do this is 2 loop. First loop we get the count of first window element. In the next loop we start remove last element and start adding new window element.
  15. Length of the largest subarray with contiguous elements – Given an array of distinct integers, find length of the longest subarray which contains numbers that can be arranged in a continuous sequence. Algo
    It is given that all elements are distinct. If all elements are distinct, then a subarray has contiguous elements if and only if the difference between maximum and minimum elements in subarray is equal to the difference between last and first indexes of subarray. So the idea is to keep track of minimum and maximum element in every subarray.  So for each ith position we find the length of the maximum sub-array. All the consecutive numbers occur in a series(though not ordered).
    Time Complexity: O(n^2)
  16. Length of the largest subarray with contiguous elements – Given an array of integers, find length of the longest subarray which contains numbers that can be arranged in a continuous sequence. Duplicate Allowed. Same as the above problem but with duplicate. If duplicate numbers occur in consecutive position then the condition can’t be satisfied. So we use hash to maintain this check if the same element  is already present.
    Here at each outer loop we re-initialize the hashset, with the new i value.We check for non-repeated values only in the sub-array.
  17. *** Longest Consecutive Subsequence  – Given an array of integers, find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any orderAlgo
       1. Sorting and loop the array and ….Complexity = O(nLogn)
    * 2. Hashing. Complexity: O(n)

    1) Create an empty hash.
    2) Insert all array elements to hash.
    3) Do following for every element arr[i]
    ....a) Check if this element is the starting point of a 
           subsequence.  To check this, we simply look for
           arr[i] - 1 in hash, if not found, then this is
           the first element a subsequence.  
        
           If this element is a first element, then count 
           number of elements in the consecutive starting 
           with this element.
    
           If count is more than current res, then update    
           res.
  18. Given a singly linked list check if has a loop or not using Hash.
    Start traversing that Linked List and for each node store the address in the hash table. If the address wasn’t present then store it in table. If the address was present then the element has been already visited.
  19. Given an unsorted array with repetitions, the task is to group multiple occurrence of individual elements. The grouping should happen in a way that the order of first occurrences of all elements is maintained. Link on GFG.
    We need to print the element that occurred first in the array  in the output first.
    We basically maintain the frequency of each element in a Hash Table and in the end print the element that number of time. If we implement this using a HashMap
    then there’s no guarantee of the order.  So we use LinkedHashMap, it differs from HashMap in that it maintains a doubly-linked list running through all of its entries. . This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.)
  20. **** Find subarray with given sum – Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.
    Algo – we maintain a variable curr_sum and initialize it’s value as the first item in the array. Then we loop through the rest of the element and keep adding there value to the curr_sum and check if the required sum has reached. If at any time the curr_sum exceeds the required from sum the starting item of the array (as we need to maintain a subarray and subarray are contiguous).
    Subarray position is from start to i in the above code.
    Time complexity is O(n). We can prove it by counting the number of operations performed on every element of arr[] in worst case. There are at most 2 operations performed on every element: (a) the element is added to the curr_sum (b) the element is subtracted from curr_sum. So the upper bound on number of operations is 2n which is O(n).
    Variation 1: Handle the above case if negative numbers are involved: ???
  21. First repeating letter in a string. Similar question in array as well.
    Start looping through each character in the array. It it’s not present in the array insert it. If it’s already present then it’s repeated.
  22. Write all solutions for a^3 + b^3 = c^3 + d^3.
    Given an array A of integers, find the index of values that satisfy A + B = C + D, where A,B,C & D are integers values in the array
  23. Write an efficient function that checks whether any permutation of an input string is a palindrome. –
    No need to generate all the permutation for the string. A string can be palindrome only if the it has only one(at max) odd character count.
  24. Word Cloud Algorithm – InterviewCake.ComThis is just for reference. Here’s how Wordle( the best word cloud generator ) actually works:Count the words, throw away boring words, and sort by the count, descending. Keep the top N words for some N. Assign each word a font size proportional to its count. Generate a Java2D Shape for each word, using the Java2D API.Each word “wants” to be somewhere, such as “at some random x position in the vertical center”. In decreasing order of frequency, do this for each word:
    place the word where it wants to be
    while it intersects any of the previously placed words
        move it one step along an ever-increasing spiral
    

    That’s it. The hard part is in doing the intersection-testing efficiently, for which I use last-hit caching, hierarchical bounding boxes, and a quadtree spatial index

  25. Find Duplicates file.
    Algo:  Calculating hash will make your program run slow. Its better you also check the file size. All the duplicate file should have same file size. If they share same file size apply hash check. It’ll make your program perform fast.There can be more steps.
    Check if file size is equal
    If step 1 passes, check if first and last range of bytes (say 100 bytes) are equal
    If step 2 passes, check file type,
    If step 3 passes, check the hash at last
    The more criteria you add the more faster it’ll perform and you can avoid the last resort (hash) this way.
    Related Info:
    Checksum is the way to go here(in real world application)  What checksum algorithm should I use?   – know when to use CRC/md5/sha family
    This checksum logic has multiple application. The most common when downloading file of the internet or packet transmission over the net. Or like checking if a file has been updated and only then upload it.
  26. Finding anagrams for a given word –  both the approaches below rely on generating a unique key which will be used for lookup in the hash table we create.
    1. the first approach it to sort the given string and then insert that into the hash table as the key.
    2. the second approach uses ascii equivalent to generate character to generate the key instead of sorting the string. This value is generated is then inserted into the hash table. If we use the ascii equivalent then there’s a possibility of collision so we can instead use prime number in it’s place like below (26 prime number for 26 characters) –
    private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113 };
  27. Colourful Number  – Code
  28. 2 Sum Problem – sorting or hashing
  29. 4 Sum – Sorting and using hash with it
    The idea is to consider every pair of elements in the array one by one and insert it into a map. For each pair of element (i, j), we calculate the remaining sum. If remaining sum exists in the map and elements involved in previous occurrence don’t overlap with the current pair i.e. ((i, j, i, y) or (i, j, x, i) or (i, j, j, y) or (i, j, x, j)), we print the Quadruplet and return.
  30. Valid Sudoku – geeksforgeek 
  31. Given an array A of integers and another non negative integer k, find if there exists 2 indices i and j such that A[i] - A[j] = k, i != j.
  32. Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses. Code
    Example :
    Given numerator = 1, denominator = 2, return “0.5”
    Given numerator = 2, denominator = 1, return “2”
    Given numerator = 2, denominator = 3, return “0.(6)”
    We need to follow the basic remainder method.


  33. Maximum number of points in a line. Code.

  34. You are given a string, S, and a list of words, L, that are all of the same length.Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters. 

  35. Given a string, find the length of the longest substring without repeating characters.
    Code


  36. [Pending] Find the smallest window in a string containing all characters of another string.

  37. Longest Consecutive Subsequence Given an array of integers, find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order. 
    Two approach  1. Sorting   2. Hashing
  38. [SKIP] Palindrome Substring Queries

  39. Find a pair with the given difference Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n.  GFG.
    Algo:
    Hashing is an obvious solution – O(n) – time and space.
    Another way is to use sorting and then search with two pointer. Overall complexity will be O(nLogn)


  40. We have an array of integers and we have to find two such elements in the array such that sum of these two elements is equal to the sum of rest of elements in array. GFG.
    Algo: Find sum of all elements. Start looping through the array. for each index i, we do sum – a[i]. Check if this value exists in hash. If yes, pair found, else add the a[i] to hash.


     

  41. Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n. GFG.
    Algo:Create an empty hash table HT. Traverse the array, use array elements as hash keys and enter them in HT. Traverse the array again look for value n + arr[i] in HT.
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s