The GATE Grind

GATE 2014 CS (CS3) – Question 50

Programming and Data Structures · Hashing · 2 marks · Multiple choice

A 100-slot hash table resolves collisions by chaining. Under simple uniform hashing, find the probability that the first three slots remain empty after the first three insertions.

  1. $97^3/100^3$
  2. $99\times98\times97/100^3$
  3. $97\times96\times95/100^3$
  4. $97\times96\times95/(3!\times100^3)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $97^3/100^3$

Explanation

Each independent uniform insertion must hash into one of the other97slots. Chaining allows repeated choices of those slots without reducing the available set. Therefore probability is **(97/100)³,A**. Multiplying97×96×95would incorrectly require distinct destinations.