IAE Academy

GATE 2026 CS2 Q.30: solution and answer

GATE 2026 · CS2Q.30 · 1 mark · NAT

The keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are inserted into a hash table using the hash function . The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is ________. (answer in integer)

See the question in the paper
GATE 2026 CS2 question 30Tap to open full size

Answer and solution

ANSWER

The length of the longest chain is 3.

Official answer: 3Source: Official answer key, GATE 2026 CS2 (IIT Guwahati)

  1. Compute h(k) = k mod 9 for each key in insertion order: 5→5, 28→1, 19→1, 15→6, 26→8, 33→6, 12→3, 17→8, 10→1.

  2. Group the keys by their bucket index (chaining): bucket 1 = {28, 19, 10}; bucket 3 = {12}; bucket 5 = {5}; bucket 6 = {15, 33}; bucket 8 = {26, 17}; buckets 0, 2, 4, 7 are empty.

  3. Compare chain lengths: bucket 1 has 3 keys, buckets 6 and 8 have 2 keys each, the rest have 1 or 0.

  4. The longest chain has length 3 (bucket 1, containing 28, 19, 10).

KEY IDEA

Compute h(k) = k mod 9 for every key in insertion order, group keys by resulting bucket index (chaining), and report the size of the largest bucket — that size is the "longest chain," not the key values themselves.

WATCH OUT FOR

Miscomputing a modulus (e.g., treating 28 mod 9 or 19 mod 9 incorrectly) or forgetting that bucket indices only range 0 to 8 (table size 9), causing keys to be misplaced into the wrong bucket and the chain count to come out wrong.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes

More Sorting & hashing questions