The Gateway to Computer Science Excellence
+10 votes
1.2k views

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 __________.

in DS by Boss (10.8k points)
edited by | 1.2k views
+2
Answer should be 288.
+2
It will be highly appreciated if along with the final answer , a short reasoning or explanation could also be provided :)
0
Is it correct?

here's my solution :

91, 77 can come anytime,

12 and 62 should after (2,12,24), 82 must be last

Hence

_ (2 _ 12 _ 24)_ 12 _ 62 _ 82

Hence 2,12,24 has 3! ways.

for 91 and 77 we have 6 palces, 6*5

hence 6*5*3! = 180.
0
@ashwin

I think you miss some cases just see ans, if i'm wrong, let me know.
0

@Ashwin Kulkarni

You can check my answer :)

0
@VS

ans given 128

right??

4 Answers

+21 votes
Best answer

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];  }

by Veteran (431k points)
selected by
+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)

by Boss (10.8k points)
+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!!

by Active (2k points)
edited by
+1

Great approach !

Just one mistake :

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  (after 82 you can not put 77 otherwise h[7] will fill up with 82 which would be wrong)

1)  [ 12,_ , 77,_, 62,  __ , 82, __ ] = 4 ways to put 91   

2) [ 12 , __, 62,_ , 77,_ , 82, __ ] = 4  ways to put 91   

So total way to arrange them would be =

                                          2 * 4( 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. 

0
Thank you @vs for correcting me.

I missed those gaps.I edited my ans.
0
hey i am getting 336
0

sid122

check the soln If you find anything wrong please ask?

0
ok .. by the way i did in this way 99 can come in 8 ways 77 can come in 7 ways , and 2 13 24 can come 3! ways other have only 1 choice so 6*8*7 336 ... whats wrong here pls correct me
0


77 can come in 7 ways 

here you are doing mistake 77 can come in 6 ways only you can't put after 88

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

0
am not calculating after 82 but am putting 91 also ..
0
ok ok got my mistake thanks :)
0
0 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.

by Junior (611 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,309 answers
198,336 comments
105,022 users