Hash Data Structures Quiz

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 × 97 × 97)/100³

B) (99 × 98 × 97)/100³

C) (97 × 96 × 95)/100³

D) (97 × 96 × 95)/(3! × 100³)

Solution :

A) is correct.

Simple Uniform hashing function is a hypothetical hashing function that evenly distributes items into the slots of a hash table. Moreover, each item to be hashed has an equal probability of being placed into a slot, regardless of the other elements already placed.

Probability that the first 3 slots are unfilled after the first 3 insertions = (probability that first item doesn't go in any of the first 3 slots)*(probability that second item doesn't go in any of the first 3 slots)*(probability that third item doesn't go in any of the first 3 slots)
= (97/100) * (97/100) * (97/100)

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Starting a Website

Git With The Program

Git Flow Chart

How to setup a project using pyenv?

An Introduction to Nutanix: What, Why, and How

“There And Back Again Lane” — Past Present and Future from 3 senior IT professionals.

Raft Consensus Algorithm Implementation with Go

Task 3 server client video calling program

SessionStack’s Year in Review: What We Shipped, Where We Hung Out, and Who We Talked to

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Longest Increasing Subsequence Coding Question

PlatinumX Tech’s Algorithm Expert Course Review (How I got into Turing).

Leetcode 290. Word Pattern

“Delete and Earn” problem using Dynamic Programming