The Gateway to Computer Science Excellence
+25 votes
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 by Boss (16.3k points)
edited by | 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.

11 Answers

0 votes
0.5 < $\frac{Number / of /  elements / already / inserted + 1}{20}$

==> 20 x 0.5 <  Number of elements already inserted + 1

==> Number of elements already inserted > 20 x 0.5 -1

==> Number of elements already inserted > 9

Answer (D) 10
by Active (1.4k points)
0 votes
Answer is 6

Let's take example key mod 20

Ans consider 0 to 5 filled

If new number index is 0 then 6 collision

If position is 1 then 5 collision

As well for all 6 position

All collision value is 21 and free slots are 14 now here probability is greater than. 5
by (27 points)
–3 votes
ans 10
by Loyal (5.2k points)
+4
I think it's answer is (A) that is after insertion of 5 keys, the insertion of new key will exceed 0.5...

and (10) not be the answer.. even if I think in that way that insert 10 keys.. then we have 10 slots vacat.. probability of collision = 10 / 20 = 0.5.. He used the word "exceed".. exceed means greater than.. It doesn't mean "greater and equal", but it is equal.. !!

explaination:

probability of inserting a new key is not independent they depends on previous insertions. So basically it is a conditional probability.. p("insetion of new key" | "insertion of m keys")

We are asking to insert the new key with probablity exceeds 0.5

0.5 < probabiltity of collision when (m + 1) keys are inserted!!

=> 0.5 < 1 - p(all are hashed to a different location)

after insertion of 5 keys

p(all are...) = 1 * 19/20 * 18/20 * 17/18 * 16/20 = 0.581  => 1 - 0.581 = 0.418 < 0.5..

after insertion of 6 th keys

it exeedes 0.5..

so, after hashing of 5 keys new key hashsed collides with an existing one exceed 0.5..

So.. (A) is the answer...
0

1 * 19/20 * 18/20 * 17/18 * 16/20 = 0.581  => 1 - 0.581 = 0.418 < 0.5.

it should be 17/20 right??

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,241 answers
194,282 comments
95,929 users