GATE CSE 2014 Set 3 | Question: 40

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 97 \times 97) / 100^3$
• B. $(99 \times 98 \times 97) / 100^3$
• C. $(97 \times 96 \times 95) / 100^3$
• D. $(97 \times 96 \times 95 / (3! \times 100^3)$

Comments

can someone share the answer we get, using linear probing?

---

I think 

C(97,3) / C(100,3)

@Arjun sir please confirm once

---

very similar to: https://gateoverflow.in/2272/gate-cse-1997-question-12

Answer 1

We have $100$ slots each of which are picked with equal probability by the hash function (since hashing is uniform). So, to avoid first $3$ slots, the hash function has to pick from the remaining $97$ slots. And repetition is allowed, since chaining is used- meaning a list of elements are stored in a slot and not a single element.

So, required probability $= \frac{97}{100} \times  \frac{97}{100} \times  \frac{97}{100}$

$= (97 \times 97 \times 97)/100^3$

Correct Answer: $A$

Comments

Sir, here if we use another hashing technique like Linear probing then ans will be c ?

---

Linear probing won't give c. It is slightly more trickier :)

---

if liner probing then what will be the ans ?@ arjun sir

is it 97*96*95/(100*99*98)

---

for liner probing it is complex . every time slot can picked up with equal probability. total 100^3 .

but then linear probing is method applied . in 1st go we can choose any 97 , but if we choose the last slot then for 2nd time we can choose 96 slots . if not then we can chhose 97 slots . likewise we have to split according to the condition .

---

hey pranay .. i didnt get your point .. pls explain again... and where my approach is wrong ?

---

total outcome : 1st time we can choose 100 slots * for 2nd time it we can choose 100 slots (if collision occur linear probing will handle ) * 3rd time 100 slot  = 100^3 .

Desire outcome : in 1st go we can choose any 97 , but if we choose the last slot then for 2nd time we can choose 96 slots + if not then we can choose 97 + 2nd time 97  if last slots are empty + if not 96 way only last one slot is full +and if 95 ways if last two slot is full + as goes for 3rd go  .

then  Desire outcome / total outcome = Something / 100^3 .

Your approach would be right if they include one condition that no collision occur also .

---

ohk ohk i got it.. i missed out  thank you :)

---

@Arjun sir if we take "linear probing" shouldnt the answer be :(95/100 *94/100 *93/100) + (97/100*96/100*95/100)+ (96*100*95/100*94/100)

---

We are doing "probability". Your answer is > 1.

Answer for linear probing is not simple here- we have to consider the cases separately - that is first one going to 99 and 100 are special cases, and so on. It is no longer a simple objective question which can be asked for GATE.

---

Sorry sir i did not notice the greater than 1 part.

sir just out of curiosity

if there are 2 more collisions in 99 after a no is entered in 99,then that case is getting cancelled because the third no will enter in 0. Sir will then the possible solution be by blocking 99 and 100 ? if so then

(95/100 *94/100 *93/100)

similarly sir if there are 2 more collisions in 100 after a no is entered in 100,then that case is getting cancelled because the second and third no will enter in 0 and 1. Sir will then the only possible solution is by blocking 100? if so then (96*100*95/100*94/100)

and rest of the cases

(97/100*96/100*95/100)

---

yes, just that you have to do it more formally.

---

okay got it sir.

---

How to solve this using reverse probability?

Answer 2

for the first insertion we have (4-100) 97 slots out of 100 slots for the second insertion also we have (4-100) 97 slots out of 100 because here chaining is used to resolve collision it means 2nd element may also get the slot where the first element already have and 3rd  insertion also have  (4-100) 97 slots out of 100 slots it means 3rd element may also get the slot  first and second elements already have. it is just like repetitions.  so answer should be       97/100 * 97/100 * 97/100

Comments

@Murali

Completely satisfied by ur approach.

Nice explanation thank you. !

Answer 3

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. (Source: https://en.wikipedia.org/wiki/SUHA_%28computer_science%29).

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) 

Comments

Refer : https://www.geeksforgeeks.org/gate-gate-cs-2014-set-3-question-50/