GATE CSE 2010 | Question: 53

Question

A hash table of length $10$ uses open addressing with hash function $h(k) = k \: \mod \: 10$, and linear probing. After inserting $6$ values into an empty hash table, the table is shown as below
$$\begin{array}{|l|l|}\hline \text{0}  &  \text{} \\ \hline \text{1} & \text{} \\\hline  \text{2} & \text{42} \\ \hline  \text{3} & \text{23} \\\hline   \text{4} & \text{34} \\\hline   \text{5} & \text{52} \\\hline   \text{6} & \text{46} \\\hline   \text{7} & \text{33} \\\hline   \text{8} & \text{} \\\hline   \text{9} & \text{}  \\\hline \end{array}$$

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

• A. $10$
• B. $20$
• C. $30$
• D. $40$

Comments

$\underbrace{42,23,34}$ $52$ $33$

$3!\ ways$

$46$ $42$ $46$ $23$ $46$ $34$ $46$ $52$ $46$ $33=5\ ways$

$Ans: 6\times 5=30$

---

thanks!

---

Adding few bits to @KUSHAGRA गुप्ता ‘s comment:-

FIX $33$ at last (as it must come at the last)

42 23 34 _ _ 33 . We have $2$ nos left $46$ and $52$ out of which $46$ is a free number which can appear in any of the $5$ places before $33$. So no. of ways to place $46$ = $5C1 = 5$

Lastly the 3 no.s $(42 ,23 ,34)$ are a group which can appear in $3! = 6$ ways.

So total no of ways = $5*6=30$

Answer 1

In the above expression, 3! is for elements 42, 23 and 34 as they can appear in any order, and 5 is for element 46 as it can appear at 5 different places.

so  Total number of different sequences = 3! x 5 = 30

Comments

Nice explanation w.r.t Gate.

---

this method is very simple

---

@rajan 

Much better explanation.

Answer 2

As in previous we found sequence 46,34,42,23 are added in to hash table as we add 52 now ,2nd position is already occupied and now to enter 52 there are 6 possibilities ,now when we add 33 ,as 3 position is already occupied now to enter 33 there are 5 possibilities

so total different possibilities = 6*5= 30

so option c is correct

Answer 3

We have 6 elements and 6 places. Fix 33 at the sixth place(It can only come at the end) . So 5 places and 5 elements are remaining

Now fix 52

42 23 34	46	4! = 24 ways
52		1 way

24*1*1 = 24 ways

42 23 34		3! = 6 ways
52		1 way
	46	1 way

6*1*1 = 6 ways

Total 24+6 = 30 ways

Comments

Good answer.

Answer 4

Total 6 insertions
― 33 must be inserted at last (only one possibility)
― 46 can be inserted in any of the 5 places remaining. So 5 ways.
― 52 must be inserted only after inserting 42, 23, 34. So only one choice for 52.
〈42,23,34〉can be sequenced in 3! ways.
Hence, 5×3! = 30 ways