# Introduction To

Hashing Data Structure

Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends of the efficiency of the hash function used.

Let a hash function H(x) maps the value x at the index x%10 in an Array. For example if the list of values is [11,12,13,14,15] it will be stored at positions {1,2,3,4,5} in the array or Hash table respectively.

# Course Structure

## Basics

## Easy

- Print a Binary Tree in Vertical Order | Set 2 (Map based Method)
- Find whether an array is subset of another array | Added Method 3
- Union and Intersection of two linked lists | Set-3 (Hashing)
- Given an array A[] and a number x, check for pair in A[] with sum as x
- Minimum delete operations to make all elements of array same
- Minimum operation to make all elements equal in array
- Maximum distance between two occurrences of same element in array
- Count maximum points on same line
- Check if a given array contains duplicate elements within k distance from each other
- Find duplicates in a given array when elements are not limited to a range
- Find top k (or most frequent) numbers in a stream
- Most frequent element in an array
- Smallest subarray with all occurrences of a most frequent element
- First element occurring k times in an array
- Given an array of pairs, find all symmetric pairs in it
- Find the only repetitive element between 1 to n-1
- Find any one of the multiple repeating elements in read only array
- Find top three repeated in array
- Group multiple occurrence of array elements ordered by first occurrence
- How to check if two given sets are disjoint?
- Non-overlapping sum of two sets
- Find elements which are present in first array and not in second
- Check if two arrays are equal or not
- Pair with given sum and maximum shortest distance from end
- Pair with given product | Set 1 (Find if any pair exists)
- Find missing elements of a range
- k-th missing element in increasing sequence which is not present in a given sequence
- Find pair with greatest product in array
- Minimum number of subsets with distinct elements
- Remove minimum number of elements such that no common element exist in both array
- Count items common to both the lists but with different prices
- Minimum Index Sum for Common Elements of Two Lists
- Change the array into a permutation of numbers from 1 to n
- Count pairs with given sum
- Count pairs from two sorted arrays whose sum is equal to a given value x
- Count pairs from two linked lists whose sum is equal to a given value
- Count quadruples from four sorted arrays whose sum is equal to a given value x
- Number of subarrays having sum exactly equal to k
- Count pairs whose products exist in array
- Given two unsorted arrays, find all pairs whose sum is x
- Cumulative frequency of count of each element in an unsorted array
- Sort elements by frequency | Set 4 (Efficient approach using hash)
- Find pairs in array whose sums already exist in array
- Find all pairs (a, b) in an array such that a % b = k
- Convert an array to reduced form | Set 1 (Simple and Hashing)
- Return maximum occurring character in an input string
- Group words with same set of characters
- Second most repeated word in a sequence
- Smallest element repeated exactly ‘k’ times (not limited to small range)
- Numbers with prime frequencies greater than or equal to k
- Find the first repeating element in an array of integers
- Find sum of non-repeating (distinct) elements in an array
- Non-Repeating Element
- k-th distinct (or non-repeating) element in an array.
- Print All Distinct Elements of a given integer array
- Only integer with positive value in positive negative value in array
- Pairs of Positive Negative values in an array

## Intermediate

- Find Itinerary from a given list of tickets
- Find number of Employees Under every Employee
- Count divisible pairs in an array
- Check if an array can be divided into pairs whose sum is divisible by k
- Longest subarray with sum divisible by k
- Subarray with no pair sum divisible by K
- Print array elements that are divisible by at-least one other
- Find three element from different three arrays such that that a + b + c = sum
- Find four elements a, b, c and d in an array such that a+b = c+d
- Find the length of largest subarray with 0 sum
- Printing longest Increasing consecutive subsequence
- Longest Increasing consecutive subsequence
- Longest subsequence such that difference between adjacents is one | Set 2
- Longest Consecutive Subsequence
- Largest increasing subsequence of consecutive integers
- Count subsets having distinct even numbers
- Count distinct elements in every window of size k
- Maximum possible sum of a window in an array such that elements of same window in other array are unique
- Check if array contains contiguous integers with duplicates allowed
- Length of the largest subarray with contiguous elements | Set 2
- Find if there is a subarray with 0 sum
- Print all subarrays with 0 sum
- Find subarray with given sum | Set 2 (Handles Negative Numbers)
- Find four elements that sum to a given value | Set 3 (Hashmap)
- Implementing our Own Hash Table with Separate Chaining in Java
- Implementing own Hash Table with Open Addressing Linear Probing in C++
- Vertical Sum in a given Binary Tree | Set 1
- Group Shifted String
- Minimum insertions to form a palindrome with permutations allowed
- Check for Palindrome after every character replacement Query
- Maximum length subsequence with difference between adjacent elements as either 0 or 1 | Set 2
- Maximum difference between frequency of two elements such that element having greater frequency is also greater
- Difference between highest and least frequencies in an array
- Maximum difference between first and last indexes of an element in array
- Maximum possible difference of two subsets of an array
- Sorting using trivial hash function
- Smallest subarray with k distinct numbers
- Longest subarray not having more than K distinct elements
- Sum of f(a[i], a[j]) over all pairs in an array of n integers
- Find number of pairs in an array such that their XOR is 0
- Maximize elements using another array

## Hard

- Clone a Binary Tree with Random Pointers
- Largest subarray with equal number of 0s and 1s
- Count subarrays with equal number of 1’s and 0’s
- Longest subarray having count of 1s one more than count of 0s
- Count Substrings with equal number of 0s, 1s and 2s
- Print all triplets in sorted array that form AP
- All unique triplets that sum up to a given value
- Find all triplets with zero sum
- Count number of triplets with product equal to given number
- Count of index pairs with equal elements in an array
- Palindrome Substring Queries
- Find smallest range containing elements from k lists
- Range Queries for Frequencies of array elements
- Elements to be added so that all elements of a range are present in array
- Cuckoo Hashing – Worst case O(1) Lookup!
- Subarrays with distinct elements
- Count subarrays having total distinct elements same as original array
- Count subarrays with same even and odd elements
- Minimum number of distinct elements after removing m items
- Distributing items when a person cannot take more than two items of same type
- Maximum consecutive numbers present in an array
- Maximum array from two given arrays keeping order same
- Maximum number of chocolates to be distributed equally among k students
- Find largest d in array such that a + b + c = d
- Find Sum of all unique sub-array sum for a given array.

## Misc

- Advantages of BST over Hash Table
- Internal Working of HashMap in Java
- Recaman’s sequence
- C++ program for hashing with chaining
- Largest subset whose all elements are Fibonacci numbers
- Pairs of Amicable Numbers
- Find All Duplicate Subtrees
- Hash Table vs STL Map
- Maximum area rectangle by picking four sides from array
- Root to leaf path with maximum distinct nodes
- Game of replacing array elements
- Length of longest strict bitonic subsequence
- Last seen array element (last appearance is earliest)