Hashing – Practice Problems

Hash tables are extremely useful data structures as lookups take expected O(1) time on average, i.e. the amount of work that a hash table does to perform a lookup is at most some constant. Several data structures and algorithm problems can be very efficiently solved using hashing which otherwise has high time complexity.

 
In this post, we will list out few problems that can be solved elegantly using hashing, with a significant economy of time and space.

• std::set, std::map, std::unordered_set, std::unordered_map in C++
• HashMap, HashSet, TreeMap in Java
• Dictionary, Set in Python

 
We recommend getting yourself familiar with the above data structures before proceeding to the following hashing problems.

1. Find a pair with the given sum in an arrayEasy
2. Check if a subarray with 0 sum exists or notMedium
3. Print all subarrays with 0 sumMedium
4. Find maximum length subarray having a given sumMedium
5. Find maximum length subarray having an equal number of 0’s and 1’sMedium
6. Find the largest subarray formed by consecutive integersMedium
7. Find majority element (Boyer–Moore Majority Vote Algorithm)Easy
8. Find a subarray having the given sum in an integer arrayMedium
9. Find a triplet with the given sum in an arrayMedium
10. Find the longest continuous sequence length with the same sum in given binary arraysHard
11. Find pairs with difference k in an arrayEasy
12. 4–Sum Problem | Quadruplets with a given sumMedium
13. Group elements of an array based on their first occurrenceMedium
14. Find all symmetric pairs in an array of pairsMedium
15. Find the count of distinct elements in every subarray of size kMedium
16. Print all subarrays of an array having distinct elementsMedium
17. Find the minimum index of a repeating element in an arrayEasy
18. Find an index of the maximum occurring element with equal probabilityEasy
19. Check if an array is formed by consecutive integersMedium
20. Find two non-overlapping pairs having the same sum in an arrayMedium
21. Count distinct absolute values in a sorted arrayMedium
22. Find subarrays with a given sum in an arrayMedium
23. Efficiently calculate the frequency of all elements present in a limited range arrayMedium
24. Shuffle an array according to the given order of elementsMedium
25. Find duplicates within a range k in an arrayEasy
26. Find the longest subsequence formed by consecutive integersMedium
27. Determine whether an array can be divided into pairs with a sum divisible by kMedium
28. Sort elements by their frequency and indexMedium
29. Sort an array based on order defined by another arrayMedium
30. Efficiently sort an array with many duplicated valuesMedium
31. Find surpasser count for each array elementHard
32. Find all common elements present in each row of a matrixMedium
33. Find common elements present in all rows of a matrixMedium
34. Check if a repeated subsequence is present in a string or notHard
35. Determine whether two strings are anagram or notEasy
36. Isomorphic StringsMedium
37. Find all possible combinations by replacing given digits with characters of the corresponding listHard
38. >Find all words that follow the same order of characters as given patternMedium
39. Group anagrams together from a list of wordsMedium
40. Find minimum operations required to transform a string into another stringHard
41. Find the longest substring of a string containing k distinct charactersHard
42. Find all palindromic permutations of a stringMedium
43. Find all substrings of a string that are a permutation of another stringMedium
44. Construct the longest palindrome by shuffling or deleting characters from a stringMedium
45. Find the first non-repeating character in a string by doing only one traversal of itMedium
46. Find all substrings containing exactly k distinct charactersMedium
47. Determine whether a string matches with a given patternHard
48. Find the odd occurring element in an array in a single traversalEasy
49. Find two odd occurring elements in an array without using any extra spaceMedium
50. Find the duplicate element in a limited range arrayMedium
51. Find two duplicate elements in a limited range array (using XOR)Medium
52. Print bottom view of a binary treeMedium
53. Print top view of a binary treeMedium
54. Find ancestors of a given node in a binary treeMedium
55. Find the diagonal sum of a binary treeMedium
56. Iteratively print the leaf to root path for every leaf node in a binary treeMedium
57. Build a binary tree from a parent arrayHard
58. Construct a binary tree from inorder and preorder traversalHard
59. Construct a binary tree from inorder and postorder traversalsHard
60. Construct a binary tree from inorder and level order sequenceHard
61. Construct a full binary tree from a preorder and postorder sequenceHard
62. Find postorder traversal of a binary tree from its inorder and preorder sequenceMedium
63. Find preorder traversal of a binary tree from its inorder and postorder sequenceHard
64. Clone a binary tree with random pointersHard
65. Construct a binary tree from an ancestor matrixHard
66. Find a pair with the given sum in a BSTEasy
67. Find the frequency of each element in a sorted array containing duplicatesEasy
68. Find pairs with difference k in an array | Constant Space SolutionMedium
69. 3–Partition ProblemMedium
70. Find the probability that a person is alive after taking n steps on an islandMedium
71. Find all employees who directly or indirectly reports to a managerHard
72. Find correct order of alphabets in a given dictionary of ancient originHard
73. Graph Coloring ProblemMedium
74. Find itinerary from the given list of departure and arrival airportsEasy
75. Find first k non-repeating characters in a string in a single traversalMedium
76. Replace each array element by its corresponding rankEasy
77. Detect cycle in a linked list (Floyd’s Cycle Detection Algorithm)Easy
78. Remove duplicates from a linked list in a single traversalEasy
79. Clone a linked list with random pointerHard
80. Link nodes present in each level of a binary tree in the form of a linked listHard
81. Find the intersection point of two linked listsMedium
82. Find the vertical sum of a binary treeHard
83. Find numbers represented as the sum of two cubes for two different pairsMedium
84. Determine if two integers are equal without using comparison and arithmetic operatorsEasy
85. Efficiently print all nodes between two given levels in a binary treeEasy
86. Level order traversal of a binary treeEasy
87. Spiral order traversal of a binary treeMedium
88. Reverse level order traversal of a binary treeEasy
89. Print all nodes of a perfect binary tree in a specific orderHard
90. Print left view of a binary treeEasy
91. Print diagonal traversal of a binary treeMedium
92. Convert a binary tree into a doubly-linked list in spiral orderHard
93. Perform vertical traversal of a binary treeMedium
94. Compute the maximum number of nodes at any level in a binary treeEasy
95. Print right view of a binary treeMedium
96. Memory Efficient Implementation of Trie in C++ – Insert, Search and DeleteBeginner
97. Find duplicate rows in a binary matrixMedium
98. Generate a list of possible words from a character matrixHard