edited by
12,968 views
71 votes
71 votes
A Young tableau is a $2D$ array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with $\infty$, and hence there cannot be any entry to the right of, or below a $\infty$. The following Young tableau consists of unique entries.
$$\begin{array}{|l|l|l|l|}\hline \textbf{1}  &  \text{2}&  \text{5} &  \text{14}  \\\hline  \text{3} & \text{4} &  \text{6} &  \text{23}  \\\hline  \text{10} & \text{12} &  \text{18} &  \text{25}  \\\hline  \text{31} & \text{$\infty$} &  \text{$\infty$} &  \text{$\infty$}  \\\hline \end{array}$$
When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled with a $\infty$). The minimum number of entries (other than $1$) to be shifted, to remove $1$ from the given Young tableau is _____.
edited by

9 Answers

3 votes
3 votes
sir may i think this Young tableau as  min heap.. delete 1 and it should filled by 31.. then just apply modified heapify procedure to get desired Young tableau..
removal of 1 and replacement of 1s position with 31 is single atomic operations so shift should not be counted..

later only swaps (modified heapify) required..
31 with 2,
31 with 4,
31 with 6,
31 with 18,
31 with 25..

is it not right way ???
2 votes
2 votes
Ans is 5, shift 2,5,14 to left and 23,25 up.

 

Edit: these shift moves will violate the Young Table property, So we have to shift 2,4,6,18 and 25 in zig-zag fashion.
edited by
2 votes
2 votes

Answer: 6

Shift $2,4,6,18,25, \infty$ in a zig-zag manner.

2 4 5 14
3 6 18 23
10 12 25
31
edited by
1 votes
1 votes

After removing 1

 

NULL 2 5 14
3 4 6 23
10 12 18 25
31 Infinite Infinite Infinite

 

NULL moves right:

(Note: NULL cannot move down because it will contradict the given question conditions. Hence, we have to move right.)

 

2 NULL 5 14
3 4 6 23
10 12 18 25
31 Infinite Infinite Infinite

 

NULL moves down:

 

2 4 5 14
3 NULL 6 23
10 12 18 25
31 Infinite Infinite Infinite

 

NULL moves right:

 

2 4 5 14
3 6 NULL 23
10 12 18 25
31 Infinite Infinite Infinite

 

NULL moves down:

 

2 4 5 14
3 6 18 23
10 12 NULL 25
31 Infinite Infinite Infinite

 

NULL moves right:

 

2 4 5 14
3 6 18 23
10 12 25 NULL
31 Infinite Infinite Infinite

 

Now in question given that " Unfilled entries are filled with infinite

Therefore:

2 4 5 14
3 6 18 23
10 12 25 Infinite
31 Infinite Infinite Infinite

 

 

We will not bring NULL to the bottom right because question is asked to find the minimum.

Since total 5 movements of NULL is involved:

 

The answer will be 5

 

 

 

Answer:

Related questions

44 votes
44 votes
3 answers
1
35 votes
35 votes
12 answers
2
go_editor asked Feb 12, 2015
30,000 views
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.
38 votes
38 votes
5 answers
3
36 votes
36 votes
6 answers
4
go_editor asked Feb 13, 2015
15,511 views
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.