Question

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

• A. $(97\times 96\times 95)/{100}^3$
• B. $(99\times 98\times 97)/{100}^3$
• C. $(97\times 96\times 95)(3!\times {100}^3)$
• D. $(97\times 97\times 97)/{100}^3$

Answer 1

The correct option is A $(97\times 96\times 95)/{100}^3$

P (First 3 slots are unfilled after the first 3 insertions) because of uniform hashing

$=\frac{97}{100}\times \frac{96}{100}\times \frac{95}{100}$