GATE CS 2010 Q53 — Arrays, Stacks and Queues

To find the number of valid insertion sequences, we analyze the dependencies between the keys based on their hash values $h(k) = k \pmod{10}$ and their final positions in the table:

• 42 ($h(42) = 2$): Placed at index 2. No dependencies.
• 23 ($h(23) = 3$): Placed at index 3. No dependencies.
• 34 ($h(34) = 4$): Placed at index 4. No dependencies.
• 46 ($h(46) = 6$): Placed at index 6. No dependencies.
• 52 ($h(52) = 2$): Placed at index 5. For $52$ to probe and land at index 5, indices 2, 3, and 4 must already be occupied. Thus, 42, 23, and 34 must be inserted before 52.
• 33 ($h(33) = 3$): Placed at index 7. For $33$ to probe and land at index 7, indices 3, 4, 5, and 6 must already be occupied. Thus, 23, 34, 52, and 46 must be inserted before 33.

Combining these constraints, we get the following partial order (poset) on the 6 keys:

• $42, 23, 34 \prec 52$
• $52, 46 \prec 33$

Since all other 5 elements must be inserted before $33$, $33$ must be at the very last position (position 6) of any valid insertion sequence.

For the remaining 5 elements $\{42, 23, 34, 52, 46\}$, the only constraint is that $42, 23,$ and $34$ must precede $52$.

• The total number of permutations of these 5 elements is $5! = 120$.
• Among the 4 elements $\{42, 23, 34, 52\}$, $52$ must appear last. The probability of $52$ being the last among these 4 elements in a random permutation is $\frac{1}{4}$.

Therefore, the number of valid insertion sequences is: