73 votes 73 votes 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? $10$ $20$ $30$ $40$ DS data-structures hashing normal gatecse-2010 + – go_editor asked Apr 21, 2016 • edited Jun 17, 2021 by Lakshman Bhaiya go_editor 27.5k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments KUSHAGRA गुप्ता commented Feb 6, 2020 reply Follow Share $\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$ 24 votes 24 votes CheeseCuBES commented Dec 9, 2020 reply Follow Share thanks! 0 votes 0 votes Abhrajyoti00 commented Nov 12, 2022 reply Follow Share 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$ 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes Total ways = 6(factorial) 42,23,34,46 can come in any order and the order of 52 and 33 should be constant. So 6(fact)/4(fact)=30. Ayan Kumar Pahari answered Feb 6, 2020 Ayan Kumar Pahari comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes A bit intuitive, scholaraniket answered Sep 9, 2019 scholaraniket comment Share Follow See all 0 reply Please log in or register to add a comment.