#codingexercise
Convert a binary tree to its mirror tree
Node  mirror(ref node root)
{
if (root == null) return root;
els
mirror(ref node.left);
mirror(ref node.right);
temp = node.left;
node.left = node.right;
node.right = temp;
}
}

void serialize(Node root, Node delimiter, Node Empty)
{
var q = new Queue<Node>();
q.Enqueue(root);
q.Enqueue(delimiter);

var node = q.Dequeue();
while (node)
{
if (root.left)
      q.Enqueue(root.left) ;
else
      q.Enqueue(Empty); // new node

if (root.right)
      q.Enqueue(root.right);
else
      q.Enqueue(Empty); // new node

node = q.Dequeue();

Console.Write(node.toString());

if (node == delimiter) {q.Enqueue(delimiter);}

}
}

Connect nodes at the same level
Void ConnnectNodes (node root)
{
If (root == null) return;
var q = new Queue <node>();
Node prev = null;
q.Enqueue(root);
q.Enqueue(null);

var node = q.Dequeue();
while (node)
{
if (root.left)
  q.Enqueue(root.left);
if (root.right)
      q.Enqueue(root.right);
node = q.Dequeue();
If (prev)
Prev.nextnodeinlevel = node;
if (node == null) {
q.Enqueue(null);
prev = null;
}
}
}

#coding exercise ( one more )
Output nearest number greater than given number such that output is palindrome
int nextPalindrome(int n)

{

for (int i =n+1; i< INT_MAX; i++)

   if (isPalindrome(i)) return i;

return INT_MAX;

}
bool isPalindrome(int n)
{
var digits = n.toDigits();
int start = 0;
int end = digits.Count - 1;
while (start < end)
{
if (digits[start] != digits[end])
{
return false;
}
start++;
end--;
}
return true;
}

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;
}

Print sorted from a matrix which is rowwise and columwise sorted
This is an online solution though I don't agree with it
Such a matrix is called Young's Tableau
int extractMin(int m[,], int N)
{
    int ret = m[0,0];
    m[0,0] = INT_MAX;
    youngify(m, N, 0, 0);
    return ret;
}
void youngify(int[,] m, int N, int i, int j)
{
    int down  = (i+1 < N)? m[i+1,j]: INT_MAX;
    int right = (j+1 < N)? m[i,j+1]: INT_MAX;

    if (down==INT_MAX && right==INT_MAX)
        return;

    if (down < right)
    {
        m[i,j] = down;
        m[i+1,j] = INT_MAX;
        youngify(m, i+1, j);
    }
    else
    {
        m[i,j] = right;
        m[i,j+1] = INT_MAX;
        youngify(m, i, j+1);
    }
}
The example that seems to break this is
1   2    9
3   4   11
10 12 13

The correct approach should be :
void youngify(int[,] m, int N, int i, int j)
{
int si = i;
int sj = j;
if (i+1<=N and Y[i,j] > Y[i+1,J]){
si = i + 1;
sj = j;
}
if (j+1<=N and Y[i,j] > Y[i,j+1]{
si = i;
sj = j + 1;
}
if (si != i && sj != j){
Swap(m[si,sj], m[i,j]);
youngify(Y, si, sj);
}

}


Get zero sum elements from a list of positive and negative integers:

void GetZeroSum(List<int> A, int sum, ref List<int> candidate, int start, int level)

{

for (int i = start; i < A.Length; i++)

{

    for (int k = 0; k < 3; k++){

      candidate[level+k] = A[i];

      if (candidate.Sum() == sum)

          print (candidate.toString());

      if (level+k < 3)

         GetZeroSum(A, sum, ref candidate, start+1, level+k+1);

      candidate[level+k] = 0;

    }

}

}

// Trial runs from this approach

[-3, 6]

Sum 0

Candidate on different iterations:

-3

-3 6

-3 6 6 

-3 -3 6  print

-3 -3 -3

6 

6 6

6 6 6

GetZeroSum(List<int> A, int sum, ref List<int> candidate)
{
if (candidate.Sum() == sum) return True;
if (candidate.Count() > 3) return False;
if (A.Count() == 0) return False;
if (A[0] == 0 && sum == 0) return True;
for (int i = 1; i <= 3; i++)
{
    candidate.Add(A[0]);
    var localsum = candidate.sum();
    if (localsum + A.sum() > sum) break; // or add other conditions to terminate early
    if (GetZeroSum(A.Remove(A[0]), sum, ref candidate) ||
        GetZeroSum(A.Remove(A[0]), sum-localsum, ref candidate))
        return True;
}
return False;
}

We continue our previous posts with some more programming exercises
Given a binary tree find the vertical sum
void GetMinMaxHD(Node root, ref int min, ref int max, int hd)
{
if (root == null) return;
if (hd < min) min = hd;
if (hd > max) max = hd;
GetMinMaxHD(root.left, ref min, ref max, hd-1);
GetMinMaxHD(root.right, ref min, ref max, hd+1);
}
void GetVerticalLine(Node root, int linenum, int hd, ref List<int> line)
{
if (root == null) return;
if (hd == linenum) line.add(root);
GetVerticalLine(root.left, linenum, hd-1, ref line);
GetVerticalLine(root.right, linenum, hd+1, ref line);
}
List<int> verticalSum(node root)
{
var ret = new List<int>();
if (root == null) return null;
int min =0;
int max = 0;
GetMinMaxHD(Node root, ref min, ref max, 0);
for (int linenum = min; linenum <= max; linenum++)
{
  var line = new List<int>();
  GetVerticalLine(root, linenum, 0, ref line);
  ret.Add(line.sum());
}
return ret;
}

Print sorted from a matrix which is rowwise and columwise sorted
void PrintSorted(int[,] m, int rows, int cols, int r, int c, ref List<int>sorted)
{
int left = GetMinColumn(m, c+1); // extract min and replace with INT_MAX;
int down = GetMinRow(m, r+1); // extract min and replace with INT_MAX;
if (left == down && left == INT_MAX) // finished
    return;
if (left < down)
sorted.Add(left);
else
sorted.Add(down);
}

#codingexercise

Void PrintBinaryNumbersUpto(int N) 

{ 

Var ret = new List<Bit>(); 

For (int I =0; I < N; I++) 

{ 

If (I == 0)  {ret.add(new Bit(0)); continue;} 

If (ret[ret.Count-1] == 0) {ret[ret.Count-1] = 1; continue;} 

For (int I = ret.Count -2; I >=0; i++) 

{ 

If (ret[i] == 0) {ret[I] == 1; break;} 

ret[I] = 0; 

If (I == 0){ret.InsertAt(I, new Bit(1)); break;} 

} 

Console.Write(ret.toString()); 

} 

} 

A Linked list ends in a loop. Remove the loop and flatten the list. 

Void RemoveLoop(node root) 

{ 

If (root == null) return; 

Node loopnode = DetectLoop(root); 

If (loopnode == null) return; 

For (node cur = root; cur.next != loopnode; cur = cur.next) 

{ 

//traverse the loop to see if it encounters cur 

For (node next = loopnode.next; next.next != loopnode.next; next = next.next) 

{ 

If (next.next == cur){next.next = null; break;break;} 

} 

}  

} 

Node DetectLoop(Node root) 

{ 

If (root == null || root.next == null) return;  

Node slow = root; 

Node fast = root; 

While ( slow && fast  && fast.next){ 

Slow = slow.next; 

Fast = fast.next.next; 

If (slow == fast) return slow; 

} 

Return null; 

} 
#codingquestion
Void printLeftView (node root, int level, ref int minLevel)
{
If (root==null)return root;
If (level > maxlevel)
     maxlevel = level;
PrintLeftView (root.left, level+1, maxlevel);
PrintRightView (root.right, level+1, maxlevel);


}

Void printRightView (node root, int level, ref int maxLevel)
{
If (root==null)return root;
If (level < maxLevel)
     MaxLevel = level;
PrintLeftView (root.right,  level+1, maxlevel);
PrintRightView (root.left, level+1, maxlevel);
}

Duplicity software takes different backends as remote source for file CRUD operations. . More about it here: https://goo.gl/f9xoiq

How does backup of a virtual instance work in VMWare - a do it yourself approach:
Let us assume we know where to find the vmdk file for the virtual machine instance. A running instance may not have all its state flushed to disk. A powered off VM instance does. If the machine is powered off, we can use the virtual machine directly. If the machine is powered on, we can clone the vm so that we don't disturb the running instance. With a cloned vm, we can now access the vmdk with the state flushed to disk. Sometimes we can even do without powering off by requiring a restart so that the state is flushed to disk. We can use less intrusive techniques if the instance provides so.
Now that we have a vmdk, we package a ovf file. To do so, we create a descriptor using the ovfmanager and the virtual machine instance.
When we write the ovf file, we can then package the vmdks and the ovf file into an archive with an ova file extension. We just tar ball this in a specific layout to create the ova file.

We continue with a few more coding questions from our earlier posts this week.
#codingquestions
Find the maximum sum path across two arrays. We are given two sorted arrays and we can switch the arrays only on a common element. The sum is continuous along the path chosen.

int GetMaxSumPath(List<int> first, List<int> second)
{
int i =0;
int j =0;
int sum1=0;
int sum2=0;
int result =0;
while(i < first.count && j <second.count)
{
if (first[i] < second[j]){
    sum1 += first[i];
    i++;
    }
else if (first[i] > second[j]){
   sum2 += second[j];
   j++
}
else{
  // intersection
   result += max(sum1, sum2);
  sum1 = 0;
  sum2 = 0;
  while ( i < first.Count && j < second.Count && first[i] == second[j])
  {
    result = result + first[i];
    i++;
    j++;
  }
}
}
while (i < first.count)
{
  sum1 += first[i];
  i++;
}
while (j < second.count)
{
  sum2 += second[j];
  j++;
}
result += max(sum1, sum2);
return result;
}

None balls with one heavier than other. Find it
Int getheavier (List <int> balls)
{
var grp1 = balls.range (0,3);
var grp2 = balls.range (3,3);
var grp3 = balls.range (6,3);
var next = max (grp1,grp2,grp3);
Next = next.split ();
Return max (next);
}

interleavings of strings 

Void printRecursive(string str1, string str2, ref  string result, int m, int n, int index) 

{ 

If (m==0&& n==0) Console.Write(result); 

If (m != 0){ 

result[index] = str1[0]; 

printRecursive(str1.substring(1), str2, result, m-1, n, index+1); 

} 

If ( n!= 0){ 

result[index] = str2[0]; 

printRecursive(str1, str2.substring(1), result, m. n-1, index+1); 

} 

} 

Given a linked list, reverse alternate nodes and append at theend 

Input 1->2->3->4->5->6 

Output 1->3->5->6->4->2 (evens are reversed) 

Void ReverseEven(Node odd) 

{ 

If (odd == null || odd.next == null || odd.next.next == null) return; 

Node even = odd.next; 

Odd.next= odd.next.next; 

Odd = odd.next; 

Even.next = null; 

While(odd && odd.next) 

{ 

Node temp = odd.next.next; 

Odd.next.next = even; 

Even = odd.next; 

Odd.next = temp; 

If (temp != null) 

  Odd = temp; 

} 

Odd.next = even; 

}

Given a binary search tree, find the number of pairs whose sum of two nodes values equals to k
One method is to do an inorder traversal and serialize the tree to a sorted array
int GetCountPairs(List<int> num, int sum)
{
int count = 0;
int start = 0;
int end = nums.Count;
for (int i =0; i< num.Count; i++)
{
  int pair = find(num, sum-nums[i]); // binary chop
   if (pair != -1)
        count +=1 ;
}
return count;
}
or advance start and end as long as their sum is greater than target.
the same thing may be applied to tree with the following:
find inorder node as n1
find reverse of node as n2
if n1 != n2 and their sum is equal to target increment 1
else if sum < target take next inorder
else if sum > target take reverse of inorder
if inorder is exhausted then there are no more
Assuming no duplicates
int GetCountPairs(List<int> num, int sum)
{
int count = 0;
int start = 0;
int end = nums.Count - 1;
While (start < end){
Int total = nums [start] +nums [end]
If (Total == sum)
{
 Count+=1;
Start++;
End- -;
}
If (Total  < sum)
{
Start++;
}else {
End- -;
}
}
return count;
}