6.1k views

Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed $0.5$.

1. $5$
2. $6$
3. $7$
4. $10$
in DS
edited | 6.1k views
0
Does anybody know what the official answer to this question in the answer key is? I'm getting 7 as the answer.

The question is a bit ambiguous.

After hashing of how many keys, will the probability that any new key hashed collides with an existing one exceed 0.5.

Here, 'new key hashed' is the ambiguity. It can mean the probability of a collision in the next 'hash', or the probability of a collision in any of the hashes of the 'new keys' starting from the first insertion. For the first case answer must be $10$ to get probability equal to $0.5$, and so $11$ must be the answer for probability $> 0.5$. Thus we can conclude from given choices, it is the second case.

So, we need to find $n$ such that after $n$ hashes, probability of collision (in any of the $n$ hashes)  $> 0.5$.

Probability that there will be a collision after $n$ hashes (a collision happened in at least one of those $n$ hashes) $= 1 -$Probability that there was no collision in the first $n$ hashes

$= 1 - 1. \frac{19}{20} . \frac{18}{20} \dots \frac{20-n+1}{20}$.

So, we need,

$0.5 < 1 - 1. \frac{19}{20} . \frac{18}{20} \dots \frac{20-n+1}{20}$.

$\implies \frac{19}{20} . \frac{18}{20} \dots \frac{20-n+1}{20} < 0.5$.

For $n=5$, we get, $0.5814$ and for $n=6$, we get $0.43605$. So, answer should be $n = 6$.

Correct Answer: $B$

by Veteran (422k points)
edited
+4
@Shraddha Please read the given explanation. Had there been no choice given 11 is the best answer. But given the choices a candidate is expected to rethink what the question setter meant.
0
@ arjun sir, i am not able to understand the difference between the two cases. please elaborate a bit. ?
0
@Arjun Sir I could not understand the explanation given by you.. Can u please explain again in bit more detail. I could not understand the diference in two cases made by you
+7
I hashed 5 keys - meaning I inserted 5 elements to the hashtable. What is the probability that there was a (at least one) collision during these insertions?

Now, I have 5 values in my hashtable. What is the probability that the next insertion causes a collision?
+1
Thanx sir. Got ur point. :)
0

@Arjun sir,you mentioned that:-

Probability that there will be a collision after n hashes = 1 - Probability that there was no collision in the first n hashes

It means, Probability of at least collision in first n hashes =1- Probability of no collision in first n hashes.

Isthis correct?

0

@Rahul

I donot think so. What is meaning of " at least collision in first n hashes "? First n hashes not all making collision

@Arjun Sir

$= 1 - 1. \frac{19}{20} . \frac{18}{20} \dots \frac{20-n+1}{20}$.

why u searching from 19, 18, 17................upto n th hashing to find hashing exceeds 0.5 or not

here " Probability that there will be a collision after n hashes = 1 - Probability that there was no collision in the first n hashes "

So, equation could be $= 1 - 1. \frac{1}{20} . \frac{2}{20} \dots \frac{20-n+1}{20}$.  like this too

0
@Rahul, yes you are correct. I just made it clear in the answer.

@Srestha How $1,2,\dots$ comes?
0
0
I removed the link -- what else can be done? :O
0
I mean probability of 1st hast where no collision should be 1/20

for 2nd hash 2/20

but why u started from 19/20?
+4
For the first hash there wont be any collision -- so 20/20, for the second one one can collide, remaining 19/20 and so on.
0
@Arjun

If it is a fill in the blank then how will you solve it ? like n=5, n=6 or n=10..... etc
0

then 11 would be best answer @Raju Kalagoni

0

My worry is not about the answer @ rahul sharma 5. I'm more biased towards the procedure of tackling this kind of problems. Please explain if you know....

0

Probability that there will be a collision after n hashes (a collision happened in at least one of those n hashes)

even if there is no collision in those n hashes.....probablity of collision after n can occur right ?

why is it necessary to have atleast one collision there

i actually dint get this statement properly

can someone help

+1

I think for the first hash value there wont be any collision,So probablity of collision is Zero.

how can it be 20/20 i.e 1?

0

For better understanding ,see https://gateoverflow.in/2272/gate1997-12

+2

The answer will be 10 only not 11 bcoz it is asked that "after hashing of how many keys the new key collides" ,so the answer will be 10 only bcoz after hashing of 10 keys the new key will be 11 and the probality will be 11/20 which is greater than 0.5. So the answer must be 10 only.

0

@BeBetter

Exactly sir i am also satisfied with ur answer.

but how best answer is 6 here.

Can anybody knows the official answer of this question?

He has asked "after how many insertion" or in which insertion probability will be >= 0.5

So after 10 keys has been inserted probability of collision will be 0.5

We can simply think like this :there are 20 slots out of which 10 are full. So there is half probability of collision. if there were less than 10 values prob. of collision would never exceed 1/2 rather it would decrease.

So answer less than 10 is not possible at all

Also probability in 'k' th insertion is  (k-1)/20

(k-1)/20 >=0.5

which gives k>=11

means in 11 th insertion we get required prob .  OR after inserting 10 values prob will exceed 0.5

by Loyal (7.8k points)
0
This is the most logical and beautiful solution of this question.
After the 10th insertion, probability of collision of new key hashed= 10/20= 0.5

After 11th insertion, probability of collision of new key hashed= 11/20 > 0.5

We are asked after which insertion, probability of collision of new key hashed exceeds 0.5. So it should be 11.
by (157 points)

Ans: D (10)

by (331 points)
0
great Solution!
0

Nice solution !

Why the answer selected as (B) then ?

Didn't clear which one is correct.

0

https://math.stackexchange.com/questions/2870603/after-hashing-of-how-many-keys-will-the-probability-that-any-new-key-hashed-coll

https://www.geeksforgeeks.org/gate-gate-it-2007-question-28/

https://prepinsta.com/questions-hash-tables-sapient-razorfish/

• But below given link is supporting answer selected as best answer and giving the same explanation as above.

https://gatecse.in/w/images/4/4c/Hashng.pdf

0

Isn't this same as "The probability of collision on the (i+1)th insertion exceeding 0.5?

https://gateoverflow.in/2272/gate1997-12

Part C. Here we considered the probabilities of no collisions till i insertions in the solution. Why didn't we consider it here?

0

The probability of collision for 11th insertion (after 10 hashing) will be exactly 10/20 =0.5

After 11 hashing (for 12th) prob. of collision>0.5

+1 vote
it is asking about exceed 0.5 which is 11 because it is not given in the option then we can mark 10 (thats all).
by Active (1.5k points)
+1 vote
Let P = Probability that newly hashed key collides with an existing one. Given P>0.5.

Let (1-P) be the probability that newly hashed key does not collide with existing one. Thus (1-P)<=0.5

Let “i” keys be already present in table. Thus number of free slots are (20-i) .

Thus (20-i)/20 <=0.5

Thus i>=10
by Junior (847 points)
+1 vote
Very Simple Question:

When first key is inserted : probability of collision: 0

When Second key is inserted : probability of collision: 1/20 , because there is only one place at which collision is possible out of 20 places

When Third key is inserted : probability of collision: 2/20... and so on.

by Active (1.2k points)
+1 vote
tell me if this approach is right or wrong
chances of collision of first element =0
chances of collision of 2nd element is 1/20

chances of collision of 3rd element is 2/20
.
.
.
.
and so on
we have to insert elements till our probability doesnt exceed 0.5 and the moment it exceeds 0.5 we take that nth number as our answer
probability = 0+1/20+2/20+3/20+4/20+...... so on till our value doesnt exceed 0.5
we can see for 5 elements our probability becomes => (0+1/20+2/20+3/20+4/20) which is equal to 0.5
now when we include 6 th element our probabilty will become 0.5+5/20 which is greater than 0.5 so 6 should be answer
by Junior (655 points)