Consider a hash table that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is .
Consider the following sequence of insertions performed on :
Which of the following positions in the hash table is/are empty after these insertions are performed?
0
10
2
1
ANSWER
Only position 2 is empty among the given options, so the correct answer is (C).
Official answer: CSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)
The hash table P[0..10] has size 11, all slots initially empty. h(x) = (x+7) mod 11.
Insert 1: h(1) = 8 mod 11 = 8. Slot 8 is empty → P[8] = 1.
Insert 13: h(13) = 20 mod 11 = 9. Slot 9 is empty → P[9] = 13.
Insert 22: h(22) = 29 mod 11 = 7. Slot 7 is empty → P[7] = 22.
Insert 15: h(15) = 22 mod 11 = 0. Slot 0 is empty → P[0] = 15.
Insert 11: h(11) = 18 mod 11 = 7. Slot 7 is occupied (22); probe slot 8 (occupied by 1), slot 9 (occupied by 13), slot 10 (empty) → P[10] = 11.
Insert 24: h(24) = 31 mod 11 = 9. Slot 9 is occupied (13); probe slot 10 (occupied by 11), slot 0 (occupied by 15), slot 1 (empty) → P[1] = 24.
Final table: P[0]=15, P[1]=24, P[2..6]=empty, P[7]=22, P[8]=1, P[9]=13, P[10]=11.
Empty positions are {2, 3, 4, 5, 6}. Among the given options (0, 10, 2, 1), only position 2 (option C) is empty; the answer is (C).
KEY IDEA
Simulate linear probing step by step: compute h(x)=(x+7) mod 11 for each key, and if that slot is occupied, probe the next slots (wrapping around) until an empty one is found.
WATCH OUT FOR
Forgetting to wrap the probe sequence around from index 10 back to index 0 (linear probing is circular), or mis-tracking which slots are already occupied by the time a later collision occurs.
From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes
