#coding questions

#1) Merge two sorted arrays into one
int[] Merge(int[] first, int second)
{
int i = 0;  // first index
int j = 0;  // second index
int k = 0; // merged index
var result = new int[first.Length + second.Length];
while ( i < first.Length  && j < second.Length ){
if ( first[i] < second[j]){
        result[k] = first[i];
        i++;
        k++;
}else{
        result[k] = second[j];
        j++;
        k++;
}
}
while (i < first.Length )
{
        result[k] = first[i];
        i++;
        k++;
}
while (j < second.Length)
{
result[k] = second[j];
j++;
k++;
}
return result;
}

#2) Find the weight of each subtree in a weighted tree
- Traverse each subtree and accumulating the (level * weight) for each nodes in that subtree.

int GetSubTreeWeights(Node root, int level)
{
assert ( level > 0);
if (root == NULL) return 0;
int wt = root.weight x level;

for (int i = 0; i < root.siblings(); i++)
   wt += GetSubTreeWeights(root.siblings[i], level + 1);
return wt;
}

for (int i = 0; i < root.siblings(); i++)
    Console.WriteLine("Weight of subtree with root at {0} is {1}",
                                root.siblings[i].toString(),
                                GetSubTreeWeights(root.siblings[i], 2));

Alternatively the tree can be traversed level wise and then the sum computed linearly.

#3) Edit Distance:
Given a starting word and an ending word, find the edit distance.
Edit distances are computed using the corresponding operations for insertion, deletion and substitution. If we represent edit distance with f(i,j) where between the substring of the first word ending in j'th character and the substring of the second word ending in with ith character,
Then
f(i,0) = i
f(0,j) = j
and f(i,j) == f(i-1,j-1) when the character is the same
and f(i,j) = f(i-1, j-1) + 1 for substitutions
and f(i,j) = f(i-1,j) + 1 for insertion of jth character into the first
and f(i,j) = f(i,j-1) +1 for deleting the nth character of the first string
We can summarize that by saying the edit distance is the minimum of f(i-1,j) + 1, f(i,j-1) + 1 and f(i-1,j-1) + 1. It is max(i,j) if min(i,j) = 0;

We create a table with the characters of the first string as columns and those of the second string as rows and use the substring to compute the edit distances of any pair of substrings.
The first row and first column are all zero because they compare against an empty string
At each additional row, we use the value from the previous column or row, and find the minimum value from the three operations - insertion, deletion and substitution.The last cell gives the edit distance of the first string with the second string.

int GetEditDistance(List<char> s, List<char> t)
{
var d = new int[s.Count+1, t.Count+1]; // initialized with zero
for (int i =1; i< s.Count; i++)
  d[i,0] = i;
for (int j = 1; j < t.Count; j++)
  d[0,j] = j;
for (int i = 1; i < s.Count; i++)
   for (int j = 1; j < t.Count; j++)
      {
         int sub = 1;
         if (s[i] == t[j]) sub = 0;
         d[i,j] = min( d[i-1.j-1] + sub,
                               d[i-1,j] + 1, // for insertion
                               d[i, j-1] + 1); // for deletion
      }

return d[s.Count, t.Count];
}

#palindrome lengths in a continuous sequence:
The key observation here is that the lengths of the palindrome upto those found to a given center are also palindrom-ic. Therefore we look for the next center based on the lengths we have found already