Linear probing in Hashing implementation

Question

I am trying to solve this problem where I need to implement Linear Probing.

Given an array of integers and a hash table size. Fill the array elements into a hash table using Linear Probing to handle collisions.

Example 1:

Input:
hashSize = 10
sizeOfArray = 4
Array[] = {4,14,24,44}

Output:
-1 -1 -1 -1 4 14 24 44 -1 -1

Example 2:

Input:
hashSize = 10
sizeOfArray = 4
Array[] = {9,99,999,9999}

Output:
99 999 9999 -1 -1 -1 -1 -1 -1 9

Your Task:
You don't need to read input or print anything.

Your task is to complete the function linearProbing() which takes as input a empty hash table (hash), the hash table size (hashSize), an integers array arr[] and its size N and inserts all the elements of the array arr[] into the given hash table.

The empty cells of the hash table are to be given a value of -1. Also, if there's no more space to insert a new element, just drop that element.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:

1 <= hashSize <= 100
1 <= sizeOfArray <= 100
0 <= Array[] <= 105

The code I wrote is:

static int[] linearProbing(int hash_size, int arr[], int N) {
    int[] a = new int[hash_size];
    for(int i = 0; i < hash_size; i++)
        a[i] = -1;
    for(int i = 0; i < N; i++) {
        int probe = arr[i] % hash_size;
        int offset = 1;
        while(a[probe] != -1) {
            probe = (probe + offset) % hash_size;
        }
        a[probe] = arr[i];
    }
    return a;
}

The given testcases are running. But when submitting I am getting TLE. Please help.

The driver code is given as follows = https://i.stack.imgur.com/ULVdd.png

user_5801823 · Answer

You missed out one single point, when the array size is bigger than the hash table, just skip the rest.

This could also be the simple point, Just replace N with hash_size and iterate. This would let you only iterate as long as arr contains elements

static int[] linearProbing(int hash_size, int arr[], int N) {
    //This is what was missing from your code
    int iterating_size = N>hash_size? hash_size : N;

    int[] a = new int[hash_size];
    for(int i = 0; i < hash_size; i++)
        a[i] = -1;
    int started = -1;
    for(int i = 0; i < iterating_size ; i++) {
        int probe = arr[i] % hash_size;
        int offset = 1;
        while(a[probe] != -1) {
            probe = (probe + offset) % hash_size;
        }
        a[probe] = arr[i];
    }
    return a;
}

Linear probing in Hashing implementation

1 Answers