Hashing with Linear probing

Question

Consider an initially empty hash table of length 10. Following are the keys in hash table inserted using mod function h(k)=k mod 10.

Slot Number	Value
0
1	91
2
3	33
4	44
5	23
6	64
7	77
8
9

How many different insertion sequences of keys would result in the above hash table?

My answer comes to be 56, is it correct?

Comments

No 60 is the correct ans

---

91 33 44 23 64 77

Among these 91 and 77 can come in any order, as there is no competition for their position.
33 should come before 23 and 44 should come before 64

and 44 should come before 23

possible ways:

(91 77) can come in any order

(33 44 23 64) should come in this order
_ 33 _ 44 _ 23 _ 64 _
these 5 positions can be filled with 91 /77 -- 5 places and 2 elements = 10 ways

(33 44) can also come in any order so 2!
20 ways?

---

manisha11  see brother

33 and 44 can be come in any order  = 2! ways

and 77 and 91 can come in any order as you said above

23 and 64 have no choices

 

_ 33 _ 44 _23_64_

77 can place in any of the 5 places right ???  

therefore 5 ways for 77

now insert the 77 into the hash

_33_44_23_64_77_

Now 91 can place in any of the 6 place right ???

therefore total possible ways = 2*5*6 = 60  

---

i am also getting 60. what is the right answer given

---

By going into Topological order, we can easily get it. (Answer is 60)

33 → 23

44 → 23

23 → 64

and 91 and 77 are free birds

 

total 6 positions, choose any 2 for 91 and 77 but it is permutation = ⁶P₂ = 30 choices

remaining 4 positions, last 2 positions should be filled by 23 and 64 respectively = 1 choice

remaining 2 positions, 33 and 44 can be in any order = 2 choices

∴ Total = 30*1*2 = 60

---

wow nice Shaik Masthan

---

I  got 36 :(

77 and 91 can insert in any order So, $6\times 5$ ways

64 can place in 1 way

23 also can place in 1 way

rest 2 can place in 2! ways

total $2!\times 30=60$

---

@srestha mam

check my method, Moreover 91 can also insert in any order , you forgetted this point

---

why $^{6}P_{2}$

why not $6\times 6??$

---

placing first number it have 6 positions,

Placing 2nd number it have only 5 positions but not 6.

---

yes, that was my mistake

thanks :)

plz chk conflict serializable one too

---

plz chk conflict serializable one too

i already commented in morning only.

---

we didn't get notification, when some one add new answer. ( due to it is not our own question )

i will check and comment.

---

@shaik-Why we are considering only 91 and 77 as free to move. 33 and 44 also have freedom and they also can come in any order.So why not we are taking $^6P_4$?

---

@Ayush Upadhyaya

Why we are considering only 91 and 77 as free to move

due to their positions doesn't effect by others.

 

33 and 44 also have freedom and they also can come in any order.So why not we are taking 6P4?

if 33 is free bird, then it can occur at last position also. then what about 23?

think similarly in case of 44 also.

 

there is a restriction that, 33 and 44 should occur before 23, and for 23, it should be occur before 64, due to that they are not free birds.

---

ohh you mean 33 and 44 should occur in way such that 2 positions after them must be left for 23 and 64 right?

---

@Shaik-Nice approach shaik bhai :)
Could you please refer me some kind of problems based on these. I am weak in finding the number of orders in such cases.

---

what are the beautiful questions till now i seen, on this concept.

1. refers two answers and comments https://gateoverflow.in/240811/topological-sort

2. https://gateoverflow.in/243402/hashing

3. refer my answers to easy way of doing https://gateoverflow.in/43327/gate2010-53

4. https://gateoverflow.in/240941/topological-sort

5.https://gateoverflow.in/243285/avl-tree

 

if you want more solve transactions (DBMS) problems

1.https://gateoverflow.in/245417/test-series

2.https://gateoverflow.in/96108/schedules

---

I m getting $6^4 * 4$==> 5184

---

Please elaborate

---

Is that the answer?

---

https://gateoverflow.in/245897/hashing-with-linear-probing

---

@Shaik Masthan

very nice approach..

I have seen you answer in https://gateoverflow.in/43327/gate2010-53

can you check graph here is this right?

first place 91 ==> 6 ways

then 77 ==> 5 ways

then 64 ==> 1 way

23 ==> 1 way

33,44 ==> 2! ways

6*5*1*2 = 60

 

---

yes, it is right

---

60

---

How 60 is the answer, please explain it.

I am getting answer 40.

---

0
1	91
2
3	33
4	44
5	23
6	64
7	77
8
9

Lets have a look at the mod values generated : for 91 is 1 for 33 it is 3 for 44 it is 4 for 23 it is 3 for 64 it is 4 and for 77 it is 7 .

Now as 23 is not at its correct position it means that it must have come after 33 and as it is not at 4 it means that it must have come after 44 also.

Now as 64 is also not at its correct position it must have come after 33,44 and 23. 77 and 91 are at their correct position so they can come at anytime.

Now : for 23 and 64 2 things are possible: 33->44->23->64 or 44->33->23->64.

Let us take case 1: 33->44->23->64 so 77 can come anywhere So we have 5 options for 77 and after that we have 6 options for 91.So in all 5*6=30.

As there are two cases:30*2=60.

 

---

@shubham6596 we will first see which insertions in the hash table are depending upon the other insertions and then insert. Those who do not depend can come at any time. Check my ans for solution and correct me if I am wrong.

---

@anjali007  I got it now, Thanks 

---

See first of all (33,34) they must appear before (23,64) in any order either (33,34) or (34,33) → 2 ways.

23 must appear before 64 so sequence can be 33,34,23,64 or 34,33,23,64.→ 1 ways.

for 77 or 97 there are 5 places → first, last and between digits total 5 places. → 5 ways.

after insertion one of 77 or 97, for the second number we 6 places first, last and between digits total 6 places.→ 6ways.

Result = 2*1*5*6 = 60.

Answer 1

Total number of elements = 6

1) In the given table, 23 should be stored at 23mod10 which is equal to 3.

But because of 3 being occupied, it goes to the next value which is 4. Again because of being occupied it is stored at 5.

Therefore, 23 must be in the sequence after 33 and 44.

2) Similarly considering 64, it should be in the sequence after 44 and 23.

3) 91 and 77 can be anywhere in the sequence. Therefore, the total possible positions of 91 and 77 are (6C2)*2! = 30

4) The remaining 4 positions should be in the following order:

33 44 23 64 or

44 33 23 64

2 combinations are possible.

5) Therefore the number of different sequences that would give the resulting table = 30*2 = 60