Tuesday, June 7, 2016

We were discussing young's tableau  yesterday and spotted the mistake we saw in a version of the online solution.
The correct solution is something like this :
void youngify(int[,] m, int N, int i, int j)
{
int si = i;
int sj = j;
if (i+1<=N and m[i,j] > m[i+1,J]){
si = i + 1;
sj = j;
}
if (j+1<=N and m[i,j] > m[i,j+1]{
si = i;
sj = j + 1;
}
if (si != i && sj != j){
Swap(m[si,sj], m[i,j]);
youngify(m, N, si, sj);
}
}
Insertion is also recursive and can be applied backwards.
Insert(m,k)
m[m,n] = k
Youngify(m,n)

Youngify(Y,i,j)
{
 li = i;
 lj = j;
 if (i-1>=1 && m[i,j] < m[i-1,j]){
    li = i-1;
    lj = j;
}
if (j-1 >= 1&& m[li, lj]  < m[i,j-1]){
   li = i;
 lj = j-1;
}
if (li !=i || lj !=j){
swap(m, i,j,li,lj)
Youngify(m,li,lj);
}
}

#one more coding question
Determine chain length of a binary tree. A chain length is the sum of the left node series, the right node series and one.
          1
     2        3
  4   5   6   7
8  9
has chain length 3 + 2 + 1 for nodes 8,4,2,1,3,7
int chainlength(node root)
{
int ret = 1;
node left = root.left;
while(left){ ret+=1; left = left.left;}
node right = root.right;
while(right){ ret+=1; right = right.right}
return ret;
}

No comments:

Post a Comment