Skip to content
GATEiit

GATE CSE 2022 Q16: Expected keys per slot with two simple uniform hash functions

Question

Suppose we are given nn keys, mm hash table slots, and two simple uniform hash functions h1h_1 and h2h_2. Further suppose our hashing scheme uses h1h_1 for the odd keys and h2h_2 for the even keys. What is the expected number of keys in a slot?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: B (official GATE 2022 final answer key)

Concept used: Under simple uniform hashing every key lands in a given slot with probability 1m\frac{1}{m}, whichever hash function is used.

First step: Use linearity of expectation: sum 1m\frac{1}{m} over all nn keys.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key

More Programming and Data Structures PYQs

PracticePractise Programming and Data Structures questions →Full paperAll GATE CSE 2022 questions →