GATE CS 2025 Set 1 Q55 — Searching, Sorting, Hashing

We are given a double hashing scheme with a hash table of size $m = 11$ (slots $0$ to $10$). The hash function for the $i$-th probe is:

where $h_{1}(k) = k \bmod 11$ and $h_{2}(k) = 1 + (k \bmod 7)$. Let's insert the keys step-by-step:

1. Key 63: $h_1(63) = 63 \bmod 11 = 8$. Slot 8 is empty. Store 63 at slot 8.
2. Key 50: $h_1(50) = 50 \bmod 11 = 6$. Slot 6 is empty. Store 50 at slot 6.
3. Key 25: $h_1(25) = 25 \bmod 11 = 3$. Slot 3 is empty. Store 25 at slot 3.
4. Key 79: $h_1(79) = 79 \bmod 11 = 2$. Slot 2 is empty. Store 79 at slot 2.
5. Key 67: $h_1(67) = 67 \bmod 11 = 1$. Slot 1 is empty. Store 67 at slot 1.
6. Key 24:
   • $h_1(24) = 24 \bmod 11 = 2$
   • $h_2(24) = 1 + (24 \bmod 7) = 1 + 3 = 4$
   • Probe $i = 0$: $h(24, 0) = 2$ (occupied by 79)
   • Probe $i = 1$: $h(24, 1) = (2 + 1 \times 4) \bmod 11 = 6$ (occupied by 50)
   • Probe $i = 2$: $h(24, 2) = (2 + 2 \times 4) \bmod 11 = 10$ (empty)
   Store 24 at slot 10.

Thus, key 24 gets stored at slot 10.