Top K Frequent Elements - Hashing Problem

Problem : Get top K frequent elements.

Implementation:

Sort By Frequency - Hashing Problem

Problem : Sort elements by their frequency.

Following is the implementation where we store the frequency in hashmap:

Count Distinct Elements In Every Window - Hashing Problem

Problem: Count distinct elements in every window of given K size.

Following is the implementation, which rotates the array window:

Print Non-repeated Elements - Hashing Problems

Problem : Print the non-repeated elements of an array.

Following is the implementation:

Relative Sorting - Hashing Problems

Problem : Sort array1 in the order of array2 elements.

Following is the implementation:

Zero Sum Sub-arrays Count - Hashing Problems

Problem : Find the number of sub-arrays whose sum evaluates to zero.

Following is the implementation:

Largest Sub-array With Sum Zero - Hashing Problem

Problem : Find the maximum length of the largest sub-array with sum zero.

Following is the implementation, where we store the sum at every index in hashmap and look for sum already being present in hashmap(only possible if sum of the sub-array is zero):

Four Sum - Hashing Problems

Problem : Find four elements in array whose sum equals to x.

Following is the implementation using hashmap:

Two Sum - Hashing Problem

Problem : Find two elements in an array whose sum is x.

Following is the implementation:

Longest Consequent Sub-sequence - Hashing Problem

To find longest consequent sub-sequence in an array, following is the implementation using hashmap:

Maximum Distance Between Two Occurences Of Same Element - Hashing Problem

To find the maximum distance between two occurrences of same element, we can store the elements in hashmap and compare max index distance. Following is the implementation:

Check If Two Arrays Are Equal - Hashing Problems

To check if two arrays are equals, lengths and elements along with their frequency need to be considered. For this, a hashmap can be used. Following is the implementation:

Linear Probing - Coursera Algorithms

Linear probing is used to resolve collisions in hashing. It takes less space and has better cache performance.

An array of size M > number of elements N is used such that:

1. Hash - map key to i between 0 and M-1.
2. Insert - at table index i, if not free - try i+1, i+2 etc

3. Search - search table index i, if occupied and no match - try i+1, i+2 etc

Following is the implementation :

Separate Chaining - Coursera Algorithms

To deal with collisions in hashing, separate chaining implementation can be used, where M linked lists(<number of elements N) are used such that :

1. Hash - map key to i between 0 and M-1.
2. Insert - at the front of ith chain.

3. Search - in ith chain.

Easier to implement and clustering less sensitive to poorly designed hash function.

Following is the implementation:

Hash Functions - Coursera Algorithms

We can do better than the sequential/binary search or search through BST/red-black BST, by storing the data in key-indexed table. Hash functions compute the array index from key. We need to handle the hash implementation, equality test and collision resolution when two keys hash to the same index.

There are several hashing implementations, some of them being :
1. 31*initial_hash_value+ current element value or current object hashcode.
2. Modular - Math.abs(key.hashCode() & 0x7fffffff)%M returning a hash between 0 and M-1

Following code experiments with what happens when we override equals/hashcode: