Insertion in Hash table. (M.E.)

Question

The number of different insertion sequences of numbers $\left \{ 7,20,32,50,66,77 \right \}$ on an initially empty hash table H of size $6$ and a hash function $h\left ( k \right )=k\mod6$ with linear probing scheme for collision resolution such that the hash table obtained after the insertion looks as shown in fig below is equal to ______________________

66

7

20

32

50

77

     ${\color{Blue} {0}}$.                  ${\color{Blue} {1}}$               ${\color{Blue} {2}}$                      ${\color{Blue} {3}}$.                       ${\color{Blue} {4}}$                     ${\color{Blue} {5}}$

 

 

Comments

@Shobhit Joshi how it is coming 6! as 3 elements and 1 set is there  so shoud nt it be 4??

 

---

6! factorial is for total combinations possible with 6 elements.

---

ohh so it finally reduces to problem of 6 elements with 3 to come in a specific sequence... got it thanks :)

Answer 1

final result be like this -

index        elements 

0                  66

1                  7

2                  20

3                  32

4                  50

5                  77

input sequence = {7, 20, 32, 50, 66, 77}

h(k)=k mod 6          |    |    |    |     |    |

                                   v    v    v    v      v    v     

                                   1    2   2    2     0    5

So therefore order of there coming can be 

66, 77, 7 are independent  they can come anywhere in any order.

20→32→50  this order has to be maintained.

out of 6 3 places has to chooses and then rest 3 places any  order 

i.e.  6C3 * 3! = 120.

  

 

Answer 2

66,7,77 can come in anytime.

Order for these:20-> 32-> 50

Think of these as 4 schedules.

No of schedule possible = 6!/3! (As 3 are in same schedule so no reordering possible)

                                             = 120

Wrong approach:

Trying to make 20-> 32 -> 50 as a group and trying to solve it like abc must come together combination problem.

Here answer is 4!.

Why wrong?

Here 20,32,50 needn't be consecutive so we cannot solve it that way.

Answer 3

in my opinionwhat I have undestood that sequence number asked is 6! =720 nos