in DS
1,670 views
5 votes
5 votes

The number of different insertion sequences on numbers {1, 14, 26, 44, 60, 71} on an initially empty hash table H of size 6 and a hash function x%6 with linear probing scheme for collision resolution such that the end hash table should look like 60, 1, 14, 26, 44, 71 (The indices of numbers from left to right are 0 to 5) are ________

in DS
by
1.7k views

1 Answer

7 votes
7 votes
Best answer
14, 26 and 44 mod 6 = 2 and hence in any input sequence they must come in sequence (otherwise their sequence changes in the end result). The other 3 numbers hash to distinct locations and hence they can be inserted in any order. So, number of possible insertion sequence

$=\frac{\text{Total insertion sequences}}{\text{Invalid insertion sequences}}$

$=\frac{6!}{3!}$

$= \frac{720}{6} = 120$
edited by
by

4 Comments

SIR my approach is we have 4 places left so first elemet has 4 choices in such  a way 4*3*2 and these place can be arrange in 4! ways . Now we miss the case in which they together can be place in the 4 remaining  space so  3!*4 in total   120 . Is it right @arjun sir
0
0
$\binom{6}{3}*1* 3!$   Choosing 3 location from 6 and arranging it only one way i.e 14,26,44 and 3! for arrangement of remaining elements.
0
0

another way to solve these types of questions is by visualizing using the forest method: https://gateoverflow.in/376398/go-classes-test-series-2023-data-structures-test-question-14

0
0

Related questions