retagged by
3,349 views
10 votes
10 votes

Consider an initially empty hash table of length 10. Following set of keys are inserted using open addressing with hash function h(k) = k mod 10 and linear probing.

0

 

1

91

2

2

3

13

4

24

5

12

6

62

7

77

8

82

9

 

The number of different insertion sequence of the key values using the given hash function and linear probing will result in the hash table shown in above __________.

retagged by

4 Answers

Best answer
23 votes
23 votes

The node dependencies are as shown below for insertion. For example; $2, 13$ and $24$ can come in any order but $12$ must strictly come after $2, 13$ and $24$. From the below graph, the problem reduces to finding the number of possible topological sorts possible. We can do this by starting from the top of the dependency.

  • $2,13,24$ can come in $3! = 6$ ways.
  • $12$ must follow it - so no more additional here, same for $62$
  • Now we have considered $5$ elements and $6$ positions (including one at first) for $77$ to be inserted. So, total ways $=6\times 6 = 36.$
  • $82$ must follow and no more additional ways here.
  • Similar to $77$, now for $91$ we have $8$ positions. So, total ways $=36 \times 8 = 288.$

digraph hash {       2 -> 12 [type=s];       13 -> 12 [type=s];       24 -> 12 [type=s];       12 -> 62 [type=s];       77 -> 82 [type=s];       62 -> 82 [type=s];       91  [type=s];  }

selected by
10 votes
10 votes


1) 91, 77 can come anytime , we will consider them latter.

2) (12,62,82) should come in same sequence and  should come after (2,13,24)

Till now :

2 , 13 , 24 , 12 , 62 , 82  ----> We can arrange (2,13,24) in 3! = 6 ways --->(1)

3) Now 77 : After 82 you can not put 77 otherwise h[7] will fill up with 82 which would be wrong

_,2 ,_, 13 ,_, 24,_ , 12 ,_, 62,_ , 82  ---> 6 ways --->(2)

Till now( Put 77 at one of the possible places) :

77, 2 , 13 , 24 , 12 , 62 , 82 

4) Now 91:

_, 77,_,2 ,_, 13 ,_, 24,_ , 12 ,_, 62,_ , 82 , _  ---> 8 ways ---->(3)

5) Total possible ways = (1) * (2) * (3) =  6*6*8  =  288 (ANS)

6 votes
6 votes

Sure @ VS !

Ok let's first check what actually given in the question -:

Given:

(i) Open addressing, Linear probing.

(ii) Hash function h(k) = k mod n , where n=10.

(iii) all slots are initially empty 

Find: No. of different insertion sequence possible to achieve given hash table ( It's actually permutation question)

Carefully look at the hash table you will find [ 12, 62, 82 ] will come always in this sequence only because of slot no. (here 'h' represent the hash table) h[2] would be filled with key 2.

Now we take some case step by step.

[ 91, 2, 13, 24, 77 ] [ 12, 62, 82]

case (i) [ 91, 2, 13, 24, 77 ] [ 12, 62, 82], in this step just we fixed the last unbolded sequence and try to arrange the Bolded sequence So in how many ways we can arrange the first Bolded partition = 5! =  (120 ways)

case (ii) Now take we are trying to take one element out of the first portion, So here you visualize we can take out only two elements 91, 77 and remaining elements 2, 13 24 we can not take out because of after key value 2 two gaps are in the hash table must be filled up with 13, 24 then only you can fill key 12 in given location in the hash table. 

Now take first element 91 out from the first portion and insert in the possible gap of the second portion( unbolded portion) which is 3 [ 12 _ 62 _ 82 _].

So total way to arrange them would be =

                                          3( possible gaps in the second portion) * 4! (arrange the first portion )  = (72 ways)

case (iii) Now take first element 77 out from the first portion and insert in the possible gap of the second portion( unbolded portion) which is 2 [ 12 _ 62 _ 82] because of after 82 you can not put 77 otherwise h[7] will fill up with 82 which would be wrong.

So total way to arrange them would be =

                                          2( possible gaps in the second portion) * 4! (arrange the first portion )  = (48 ways)

case (iv) Now take both elements 77 and 91 out from the first portion and insert in the possible chance of the second portion( unbolded portion) which is  8 { [ 12 , __77__, 62  __  82 __ ] = 4, [ 12 , __, 62 , __,77__ , 82 __ ] = 4 } but after 82 you can not put 77 otherwise h[7] will fill up with 82 which would be wrong.

      

So total way to arrange them would be =

                                        8 * ( possible chance in the second portion) * 3! (arrange the first portion )  = (48 ways)

So total possible ways of sequence

case(i) + case(ii) + case(iii) + case(iv) = 120+ 72+ 48+ 48 = (288) ans. 

I hope it will help you to understand [ thumb up] :)

Please if you find anything wrong, you are welcome!!

edited by
1 votes
1 votes

Just trying to present an alternative approach here :-

Since Open Addressing and Linear Probing are used here, so 2, 13 and 24 definitely need to be inserted before 12, 62 and 82. We keep 91 for separate now. This is because upon hashing, we find that 91 is to be inserted in position 1 (91 % 10 = 1) and whilst following the linear probing approach, we can observe that the position of 91 wouldn't be disturbed at all (later positions would be taken into consideration for filling up while inserting 12, 62 and 82). 

So, we can have 3 possible groupings of insertions (here, the ordering is wrt the insertion of 77) :-

1. (2, 13, 24), 77, 12, 62, 82 -> Here, 77 comes before both 12 and 62.

    The first 4 elements can be arranged in 4! = 24 ways.

2. (2, 13, 24), 12, 77, 62, 82 -> Here, 77 comes in between 12 and 62.

    The first 3 elements can be arranged in 3! = 6 ways. 

3. (2, 13, 24), 12, 62, 77, 82 -> Here, 77 comes after both 12 and 62.

    The first 3 elements can be arranged in 3! = 6 ways.

Hence, total number of ways (excluding the insertion of 91) = 24 + 6 + 6 = 36.

Since, there are a total of 8 insertions here, 91 will have 8 possible sequences of insertion (It can be inserted anytime).

Hence, required answer = 36 * 8 = 288.

Related questions

0 votes
0 votes
1 answer
1
Ram Swaroop asked Jan 27, 2019
1,261 views
Consider the hashing table with 'm' slots and 'n' keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search...
0 votes
0 votes
1 answer
2
Magma asked Dec 27, 2018
472 views
How to solve such kind of questions ? Can anybody tell what's is the concept behind this ?? someone provide me link so that I read it and understand the actual concept
0 votes
0 votes
0 answers
3
Jyoti Kumari97 asked Nov 25, 2018
542 views
What is the number of collisions while doing insert operation on the hash table? Options are 3456Answer is 4Can anyone tell me how? ​​