GATE CSE 2021 Set 1 | Question: 47

Question

Consider a $\textit{dynamic}$ hashing approach for $4$-bit integer keys:

1. There is a main hash table of size $4$.
2. The $2$ least significant bits of a key is used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
5. First, the $3^{\text{rd}}$ least significant bit is used to divide the keys into left and right subtrees.
6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the $4^{\text{th}}$ least significant bit.
7. A split is done only if it is needed, i.e., only when there is a collision.

Consider the following state of the hash table.

Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

• A. $5,9,4,13,10,7$
• B. $9,5,10,6,7,1$
• C. $10,9,6,7,5,13$
• D. $9,5,13,6,10,14$

Comments

For those who are unable to understand the question and solution as well. The question is simple but elegant.

What the question is saying is that the keys are represented in 4bits and the 2 least significant bits(last 2 bits while reading from left to right) will decide where the key is going to be placed. And if there is a collision then we have to see the 3rd least significant bit(3 bit from right) and if 3rd LSB of both the keys are same then move on to the 4 LSB. Try to form a binary tree with the conflicted keys. That's it now go to the options and try one by one .. option elimination would be a faster way to solve.

[*For collision just move to the next bit from right to left.]

---

After solving this question i felt that in gate exam on  the D day it is all about our mindset that how well we are going to perform on that day bcoz in the first go i didnt understood question but it is very easy question it can come in 1 mark also ​​​​

---

Yes being calm and staying composed on the D-Day can help extravagantly...!

Answer 1

• $1 – 0001$
• $4 – 0100$
• $5 – 0101$
• $6 – 0110$
• $7 – 0111$
• $9 – 1001$
• $10 – 1010$
• $13 – 1101$
• $14 – 1110$

• A. $5, 9, 4, 13, 10, 7$

• A. $9,5,10,6,7,1$

• A. $10,9,6,7,5,13$

• A. $9,5,13,6,10,14$

So only one option correct C.

Ans. (C)

Comments

Time saving move- Option A&D are directly eliminated because slot 10 should have exactly 2 keys and In option A slot 10 have only one key and In option D slot 10 have 3 keys. Now only option remains to check is Option B&C.

---

no bro, 6 10 14 cant be together

---

@dheeraj23 That’s why I eliminated option D. What’s your doubt? I didn't get your point.