GATE CSE 2010 | Question: 53

Question

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?

• A. $10$
• B. $20$
• C. $30$
• D. $40$

Comments

@js__ it just practice u can use the JEE material tooo that also GOOD

---

We can consider cases and solve this

Facts to analyse while reading the question:

1. Keys valued 42,23,34,46 do not collide where as 52 and 33 experience collision.
2. 52 must come after 42, 23, 34, 46 and 33 must come at last

So we'll consider 2 cases:

Case 1: _ _ _ _ 52 33 (That is elements 42,23,34,46 come before 52)

Case 2: _ _ _ 52 _ 33 (46 comes after 52)

In first case...All the 4 considered elements(42,23,34,46) can come in any slot...
i.e 4*3*2*1 = 24 different sequences 

In second case....46 has only 1 choice and rest of the 3 elements can be arranged in any order
i.e. 3*2*1 = 6 different sequences

Since we are counting different possible cases, the total possible sequences will be the just the sum of those..

i.e 24 + 6 = 30

 

---

https://youtu.be/804ML4KSmVc?si=UnX6OvEOSZLhcTmg&t=462

Answer 1

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$

Comments

@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?

---

is n't case 2 subset of case 1 ?

---

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.

---

@Ayush Upadhyaya's method of visualizing as a DAG whenever there are such orders of elements is so useful, it helped me solve a different question, involving the number of ways one can create a balanced BST from the set $\{1, 2, ..., 7\}$ (the number of permutations of that set which when inserted into an empty BST lead to a balanced BST).

---

From where did you come up with this mind-blowing solution. I mean, did you read this from any book or it is your idea?

Please mention the reference(if any)

---

@faisal, unexpectedly i correlated this type of questions with DAG. Practiced and presented in GO.

---

Awesome!

---

If 52 comes at position 4, after 3! arrangements of the first 3 numbers, the next 3 numbers, i.e. 52, 46 and 33 can be arranged in 2 ways, 52 46 33 or 46 52 33. That would result in 3! × 2 = 12 ways of arranging. You've not taken that into account. ┐⁠(⁠ ⁠∵⁠ ⁠)⁠┌

---

best intuitive method 👌

---

Bro, the case with the last 3 as 46 52 33 will get covered in the case 1 only, so matlab sirf case 2 ke last 3 digits rakhne ka tareeka would be 52 46 33 and first 3 digits with 3!

Answer 2

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$

Comments

The bracketing of elements helped a lot in visualization.

---

I think we should multiply case 1, whose result is 6, with 2, since, we should also take into account that 52 comes before 46 or 46 comes before 52, in both these cases, the insertion sequence can be right.

for example 1: 42, 23, 34, 52, 46, 33

for example 2: 42, 23, 34, 46, 52, 33

---

best explaination ❤️.love it.

 

Answer 3

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 ===> ⁵C₁ = 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

---

Blog: https://gateoverflow.in/blog/16797/permutations-and-combinations-specific-to-dag

---

Practice: 

 https://gateoverflow.in/253496/

 https://gateoverflow.in/243402/hashing

https://gateoverflow.in/240941/topological-sort

https://gateoverflow.in/243285/avl-tree

https://gateoverflow.in/245897/hashing-with-linear-probing?show=245926#c245926

https://gateoverflow.in/118640/gate-cse-2017-set-2-question-44?show=289691#a289691

Comments

nice explanation sir.

---

nicely explained, thanks

---

$Best$ $answer$ $!!!!$

Answer 4

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.

Comments

Rajesh nice explanation :)

Answer 5

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

Comments

Nice explanation w.r.t Gate.

---

this method is very simple

---

@rajan 

Much better explanation.

Answer 6

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