Testbook Test Series: Programming & DS - Hashing

Question

The keys 44, 63, 29, 78, 23, 6, 81, 14, 13, 12 and 52 are inserted into an initially empty hash table of length 12 using linear probing with hash function h(k)= k mod 12. What is the probability that the 10th slot will be filled next?

i. 11/12

ii. 1/12

iii. 10/12

iv. 1

The answer given is i but according to me it should be iv because after we insert all the given numbers in the hash table only one slot  is left which have a probability of filling as 1 because no matter what index we get for the next insert we are going to fill 10th slot only.

Comments

suppose the next element k(12th element) is inserted and k mod 12=11 but since it is filled(also the slots next from 0-9 are also filled) and we r  follwing linear probing we have travel elemnt 23,12,13,14,63,48,29,78,6,44,81(11 elemnts) to reach slots 10 in table.

so probablity = total events /sample space= 11/12

---

in best case only it can happen that the element k gives you slot number 10  but you have to take every case in picture if not mentioned anything.

hope you get it

---

edited. answer iv. 1

---

That is what I am saying whatever may be the case the 10th element is going to get filled this time because no other element is empty, so the probability should be 1.

The resultant hash table after inserting all the keys is:

0	12
1	13
2	14
3	63
4	52
5	29
6	78
7	6
8	44
9	81
10
11	23

Now whatever be the hashed value may it be anything from 0-11 including 0 and 11 10th position is going to get filled. So favourable events are 12 and total events are 12 therefore 12/12 = 1. I still dont get your answer.

---

(see your table and my comment)favourable event will be 11 not 12. you are not getting this properly.

before explaining further can you explain how u r getting favourable events 12(it is wrong btw)

---

Can you please tell me in which event the 10th index will not be filled? May be I am counting that event in my calculations

---

If kmod12 = 0 10th position will be filled

if kmod12 = 1 10th position will be filled

if kmod12 = 2 10th position will be filled

.

.

.

.

if kmod12 = 11 10th position will be filled

therefore in 12 out of 12 events, 10th position will get filled. Therefore 12 favorable events

---

but bro it will have to cross the elements so it will come in pictures too. it is follwing linear probing . h(k) mod 12=anything(other than 10) will just not directly put it in that table(10th slots).it will cross/cover every element and that element will be considered as event.it is asking about probability(it will include all the events possible and that is possible if h(k) mod 12=11).

just read my first comment again

---

Can you tell me the source of this formula, I am not getting why the element hoping is considered as events. Please specify the chapter number and page number of the standard book.

---

it should be probability of 1 only...
note that it is asking for filling, what ever may be the value, it should come and filled by 10th slot only

---

even though the probes are different but it should come and filled by 10th slot only

---

thank you

sorry @vinay for confusions i let you in.

---

how it's selected as a best answer ??

there's no explanation nothing :3

---

Why people want to earn a point and select this is the best answer??

This thing is not good

---

i totally agree.

thanks for removing it (but btw @magma and @lakshman patel rjit ,i had the  brief discussion with the person who posted it in above comments after that i edited my answer ,if he has selected my answer as best ,so i cant do anything .at last we came to conclusion)i think i earned my points to be honest.

you can go with the above pile of  comments.

---

If enough discussion in the comment section, why you write "edited. answer iv. 1"

This is not required, in the answer, you can move answer to comment?

---

sorry ,i will be careful about this in future. my intention was to just finalize the answer (so that anybody come across this question,then they know that the answer is 1)

---

adarsh_1997

brother chill ...  Don't say sorry it's all fine :D

---

Ok, no problem,but if someone read the entire comment so they will definetely undestand the answer.

or you can write the final answer in the comment section. It will be good.

Keep doing it.

Thanks

---

If 9th and 10th both are empty then filling 10 th  will have 11/12 probability ?

---

If 9th and 10th are empty them the probability of filling 10th will be 1/12 because 10th gets filled only when element is directly mapped to it, otherwise 9th will get filled, therefore the probability of filling 9th will become 11/12.

---

answer will be 1 only, it's a sure event, there is only 1 bucket left empty.