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
edited | 7k views
+87

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

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.

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

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 (:
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 :)

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

Much better explanation.

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)

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
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)