The Gateway to Computer Science Excellence
+47 votes
7k 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 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$
in DS by Veteran (105k points)
edited by | 7k views
+87

.....,..............

+4
it should be 23 rt? rather than 33
0
Tnx bhai mje aa gye

9 Answers

+63 votes
Best answer

53 - 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$

by Veteran (431k points)
edited by
0

@arjun sir, i count same as you count above this comment..but did not get logic of selected answer  for question 53..can you explain that approach?

0
is n't case 2 subset of case 1 ?
+8

The problem can be modelled as the number of Topological orders of the above graph.

Clearly, 33 has to come last.

Case 1: 42,23,34,46(All deg 0 nodes) can come in any order->4! ways=24.

Case 2:I Selected to remove 42,23,34 first.->3!->6 choices.Now, if after that 46 and 52 comes in that order, this case will be redundant(Included in Case 1) so I consider 52 followed by 46 and then 33 so only 6 possible orders this way.

Total Order=30.Answer.

+50 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$

by Boss (30.8k points)
edited by
0
EPIC EXPLANATION
0
Your case 2 also include Case 1 Permutations , rt ?? Why not subtracting them ?
0
@toto_chan Independent events bro. And keeping 46 fixed is one case that's not taken into account in case 1.
0
Good one.
+22 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

by Veteran (65.7k points)
0
For such questions if we make DAG first then it is just no of topological sorts right ?
0
yes !
0
Very easy explanation.
0

5C1 confusing me here @Shaik Masthan. If hash function is given and it will be mapped to only 6th bucket, then how come it have 5 choices?

+1

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

This statement should be 46 can come in any order among 5 available numbers(i.e first, second, third, fourth, fifth) that makes it 5.

Perfect way to deal with topo couting. Thank you. 

0
Not Good at English... :)

finally did you understood ?
0
Yes bro... no no don't get me wrong. I thought that line specify placement in a particular bucket. That is why there was confusion. Totally my fault.
+1

@Shaik Masthan that was an amazing explanation!!

0
Brilliant! Thanks for this answer (:
+14 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.
by Boss (23.9k points)
+1
Rajesh nice explanation :)
+11 votes

In the above expression, 3! is for elements 42, 23 and 34 as they can appear in any order, and 5 is for element 46 as it can appear at 5 different places.

so  Total number of different sequences = 3! x 5 = 30

by Loyal (5.6k points)
0
Nice explanation w.r.t Gate.
0
this method is very simple
0

@rajan 

Much better explanation.

+6 votes
As in previous we found sequence 46,34,42,23 are added in to hash table as we add 52 now ,2nd position is already occupied and now to enter 52 there are 6 possibilities ,now when we add 33 ,as 3 position is already occupied now to enter 33 there are 5 possibilities

so total different possibilities = 6*5= 30

so option c is correct
by Active (1.9k points)
+2 votes

We have 6 elements and 6 places. Fix 33 at the sixth place(It can only come at the end) . So 5 places and 5 elements are remaining

Now fix 52

42

23

34

46 4! = 24 ways
52   1 way
     

24*1*1 = 24 ways

42

23

34

  3! = 6 ways
52   1 way
  46 1 way

6*1*1 = 6 ways

Total 24+6 = 30 ways

by (217 points)
0
Good answer.
+2 votes
Total 6 insertions
― 33 must be inserted at last (only one possibility)
― 46 can be inserted in any of the 5 places remaining. So 5 ways.
― 52 must be inserted only after inserting 42, 23, 34. So only one choice for 52.
〈42,23,34〉can be sequenced in 3! ways.
Hence, 5×3! = 30 ways
by Active (4.3k points)
Answer:

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,370 answers
198,506 comments
105,275 users