edited by
28,962 views
62 votes
62 votes

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$
edited by

11 Answers

5 votes
5 votes
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
2 votes
2 votes
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.

Answer is :10
1 votes
1 votes
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).
1 votes
1 votes
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
Answer:

Related questions