GO Classes 2023 | IIITH Mock Test 1 | Question: 16

Answer 1

First key can go to any slot. For the second key, we have $3$ options to map (left of first key, right of first key and to the same slot of first key). Hence probability $= 3/9 = 1/3.$

Comments

for two consecutive slots , we can have left right only how come the slot itself is counted in the probablity ?

---

By similar idea:
Can I say for 3 consecutive places upon 3 insertions, the probability should be:
 p = 1 * 3/9 * 4/9 = 4/27

---

@KhushiRastogi consider open addressing and open chaining .

---

@Lakshman Bhaiya Solution is incorrect. 2nd one cannot be mapped to same slot. Question has asked for consecutive slots

Favourable cases: 9 ordered pairs like (slot 1 , slot 2), (slot1,slot 9), (slot 2 , slot 3)...etc. Every ordered pair can be filled up in 2 ways (key1,key2) or (key2, key1).. so total cases= 2*9=18

Total cases= 81 (Each key has 9 options..Also can be thought as 9c2+ reflexive cases (slot1,slot1)..etc so, 72+9=81)

so ans= 18/81=2/9

---

We have to consider the same slot because if the new element falls in the same slot, then we have to do probing and put it in the immediate next slot which leads to 2 consecutive slots filling.

---

Shit you're correct. Completely missed that word linear probing in the question 🤦🏻

Answer 2

9C2 ways to select any two slots and then there are 9 possible combinations of the consecutive slots  (1,2),(2,3), (3,4),(4,5) ,(5,6),(6,7),(7,8),(8,9),(9,1).

So shouldn’t it be ¼ ?

Answer 3

I think consecutive slots be like – (0,1), (1,2), (2,3), (3,4), (4,5),(5,6), ( 6,7),  (7,8) ,(8,0) ==== 9 choices and  the total number of options we have is 9C2 = 9 / 9C2  ==== ¼ ??

Answer 4

First we select 2 places out of 9 places and then there are 9 possible combinations of the consecutive slots (0,1) ,(1,2) ,(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,0)

so Answer is the ¼.