Consider a hash table of size 10 with indices , with the hash function
where linear probing is used to handle collisions. The hash table is initially empty and then the following sequence of keys is inserted into the hash table: . The indices where the keys 14 and 15 are stored are, respectively
2 and 5
2 and 6
4 and 5
4 and 6
ANSWER
Keys 14 and 15 are stored at indices 4 and 6, so the answer is (D).
Official answer: DSource: Official answer key, GATE 2025 DA (IIT Roorkee)
Compute each key's home slot with and insert in the given order. On a collision, probe forward one slot at a time (linear probing), wrapping around the table.
Key 1: . Slot 3 is empty, so 1 goes to slot 3.
Key 4: . Slot 2 is empty, so 4 goes to slot 2.
Key 5: . Slot 5 is empty, so 5 goes to slot 5.
Key 6: . Slot 8 is empty, so 6 goes to slot 8.
Key 14: . Slot 2 is occupied by 4 and slot 3 by 1. Slot 4 is empty, so 14 goes to slot 4.
Key 15: . Slot 5 is occupied by 5. Slot 6 is empty, so 15 goes to slot 6.
Keys 14 and 15 are stored at indices 4 and 6, which is option (D).
KEY IDEA
With linear probing, insert keys in the given order. A key goes to its home slot if that slot is free. Otherwise it goes to the next free slot, checking modulo the table size.
WATCH OUT FOR
Using instead of . Also stopping after one probe: key 14's home slot 2 is full, and slot 3 is full too, so it must go on to slot 4.
From the GATE 2025 DA paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes
