edited by
26,929 views
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?

  1. $10$
  2. $20$
  3. $30$
  4. $40$
edited by

10 Answers

Best answer
88 votes
88 votes

Option (C).

Slots $3,4,5$ and $6$ must be filled before $33$ comes. Similarly slots $2,3$ and $4$ must be filled before $52$ comes. And $52$ must come before $33$, as it is not occupying slot $2$. So, $33$ must be at the end and $52$ can come at position $4$ or $5$.

Let $52$ come at position $4$. Slots $2, 3$ and $4$ must be filled before $52$ leaving only slot $6$ left for the element coming at position $5$ which should be $46$. So, the first $3$ elements can come in any order giving $3! = 6$ ways.

Let $52$ come at position $5$. Now, the first four elements can come in any order. So, $4! = 24$ ways.

So, total number of different insertion sequences possible $= 24 + 6 = 30$

edited by
79 votes
79 votes

answer = option C

the element $33$ has managed to hold position at slot #7 it means elements should occupy slot #3 to slot #6 before it in the sequence. Currently, it seems like all element except $42$ should come before $33$ in the sequence.

But, element $52$ requires that $42$ comes before it. and $33$ requires that $52$ comes before it. This means that $42$ has to come before $33$. this makes element $33$ to occupy last position in the sequence.

now for element $52$ to occupy its place these can be two cases :

  • Case 1 : $\boxed{\{42,23,34\}}, 52$ 
  • Case 2: $\boxed{\{42,23,34,46\}}, 52$ 

Case 1 means that those three elements comes before $52$ = $3! = 6$ways
Case 2 means that those four elements comes before $52$ = $4! = 24$ways

Combining all info we get,
Total number of sequences possible that will form the same hash table as above $= (6 + 24) \times 1 = 30$

edited by
52 votes
52 votes

there are 6 elements,

__ __ __ __ __ __

1  2  3  4  5  6

1) we can clearly observe that, 33 is always last, therefore fix it ===> 1 choice only for 33

 

Now we have 5 elements

__ __ __ __ __

1  2  3  4  5

46 can insert it any where ===> 5C1 = 5 choices

 

remaining 4 elements

__ __ __ __

1  2  3  4

clearly we can observe that, 52 is the las element ===> fix it ==> 1 choice

 

remaining 3 elements

__ __ __

1  2  3

 

there is no conflict between them ===> 3! possibles

 

Totally = 1 * 5 * 1 * 3! = 5*6=30

20 votes
20 votes
Convention Followed here:-Those things in ( ) can be permute in any order. Except bracket all no. are fixed

Here 2 cases occur

Case1:-->>(42,23,34,46),52, 33

(Means first 4 item permutable  and last 2 item fixed)

Due to mod 10 function they will always go to their unit position Bucket

so 4!=24 Insertion Sequence possible.

Case2:-->>(42,23,34),52,46,33

Case2 Explanation...

To get more insertion sequence we compulsory put 52 as 4th item in insertion sequence which will be different from above 24 insertion sequence bcz in those 24 sequence 52 always comes as 5th item of insertion sequence where as here it comes as 4th item of insertion Sequence.

So 3!= 6 possibilities

So total case1+case2=24+6= 30 possibilities.
Answer:

Related questions

23 votes
23 votes
3 answers
1
go_editor asked Sep 30, 2014
6,581 views
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...
57 votes
57 votes
12 answers
3
go_editor asked Sep 29, 2014
16,072 views
In a binary tree with $n$ nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree ...