GATE Overflow Test Series | Algorithms | Test 1 | Question: 2

Question

Suppose you are given the following set of keys to insert into a hash table that holds exactly $10$ values: $13, 107, 49 , 50 , 64 , 98 , 16 , 33.$ Which of the following best demonstrates the contents of the hash table after all the keys have been inserted using linear probing and $\mod 10$ as hash function

• A. $50\;-\;-\;13\;64\;33\;16\;107\;98\;49$
• B. $50\;33\;-\;13\;64\;-\;16\;107\;98\;49$
• C. $50\;-\;33\;13\;64\;-\;16\;107\;98\;49$
• D. $50\;-\;-\;33\;64\;13\;16\;107\;98\;49$

 

Answer 1

Given that, the values$:13, 107, 49 , 50 , 64 , 98 , 16 , 33.$

• $13\mod 10 = 3-$ No collision
• $107\mod 10 = 7-$ No collision
• $49\mod 10 = 9-$ No collision
• $50\mod 10 = 0-$ No collision
• $64\mod 10 =4- $ No collision
• $98\mod 10 = 8-$ No collision
• $16\mod 10 = 6-$ No collision
• $33\mod 10 = 3-$ There is collision, so $33$ will go to next free slot.

$$^\text{Hash Table} _{\begin{array}{|c|c|c|}\hline
\text{Index}&  \text{Values} \\\hline
0&  50 \\ \hline   
1&   \\     \hline
2&        \\\hline
3&    13     \\\hline  
4&   64\\     \hline
5&    33     \\\hline
6&    16     \\\hline  
7&   107\\     \hline
8&    98     \\\hline
9&    49     \\\hline
\end{array}}$$

So, the correct answer is $(A).$

Answer 2

Only $33$ has a collision here. Next slot $4$ is occupied but slot $5$ is empty. So, $33$ goes there. Option A is correct.