Linear probing

0

0 votes
Easy
Problem

You need to implement linear probing.You have to perform insertion, deletion operations in it following the below input format.

Input format:
First line contains the size of the hash table
Next line contains the no of queries q
Next q lines contains 3 types of queries
Type 1 contains 1 followed by an integer that need to be inserted into the hash table
Type 2 contains 2 followed by an integer that need to be deleted from the hash table
Type 3 contains a single integer 3 which indicates that the elements of hash table need to be displayed

Output format:

If the operation is insertion there is nothing to be printed. If operation is to display then print the hash table.

For displaying, print the elements of the hash table on the same line seperated by space.

Print -1 for empty buckets.

Sample Input:
10
8
1 5
1 15
1 25
1 6
3
2 5
2 15
3

Sample Output:

-1 -1 -1 -1 -1 5 15 25 6 -1 
-1 -1 -1 -1 -1 25 6 -1 -1 -1

Explanation:
10 is the size of the hash table
8 - no of queries
First query - 5 will be inserted into the hash table at 5th position. 
Second query - 15 need to be inserted at 5th position(since 15%10=5). Since it is not empty, it will be inserted at next empty position i.e.,6th position.
Third query - 25 need to be inserted at 5th position(since 25%10=5). Since it is not empty, it will be inserted at next empty position i.e.,7th position.
Fourth query - 6 need to be inserted at 6th position. Since it is not emoty, it will be inserted at next empty position i.e.,8th position.
Fifth query - displays all the elements of the hash table
-1 -1 -1 -1 -1 5 15 25 6 -1 
Sixth query - 5 need to be deleted. First it will be deleted and then all the elements will be rehashed. Now the elements of the hash table are -1 -1 -1 -1 -1 15 25 6 -1 -1
Seventh query - 15 need to be deleted. First 15 will be deleted and then all the elements will be rehashed. Now the elements of the hash table are -1 -1 -1 -1 -1 25 6 -1 -1 -1 
Eighth query - displays the elements of the hash table. 
-1 -1 -1 -1 -1 25 6 -1 -1  -1

Time Limit: 5
Memory Limit: 256
Source Limit:
Editor Image

?