0.5170 is taken as wrong answer :(

Dark Mode

956 views

1 vote

Suppose you have a hash table that can hold $100$ elements. It currently stores $30$ elements (in one of $30$ possible different locations in the hash table). The probability that your next two inserts will cause at least one collision is ( by assuming a totally random hash function) __________

8 votes

Best answer

Second Method to solve this problem :-

3 cases are possible when we insert 2 elements in hash table

**Case 1- Collision on First insertion and Not Collision on Second Insertion**

P(case-1) = (30/100)* (69/100) = 0.207

**Case 2- Not Collision on First insertion and Collision on Second Insertion**

P(case-2) = (70/100)* (31/100) =0.217

**Case 3- Collision on both First insertion and Second Insertion**

P(case-3) = (30/100)*(31/100) = 0.093

Finally,

**Required Probability = P(Case-1) or P(Case-2) or P(Case-3)**

=0.207 + 0.217 + 0.093 = 0.517

**Note - This method is only efficient when number of insertion is less.**

@ShiveshRoy @Bikram shouldnt it be 30/100 and 30/100 for collision on first insertion means that we are hasihng to one of the 30 possible options and 2nd time collision also means that we are hashing again to one of these 30 slots ... pls explain ..

0

5 votes