998 views
1 votes
1 votes

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}}$

 

 

3 Answers

0 votes
0 votes

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.

  

 

0 votes
0 votes
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.

Related questions

0 votes
0 votes
1 answer
1
tishhaagrawal asked Dec 16, 2023
311 views
Below is my approach to solving this question, can anyone please explain if I am doing it the right way?Let X = #free slotssince, m =7 and n = 3So, $4 \leqslant x\leqsla...