#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.
The suggestion is that the lengths array we construct will have values similar to the palindrom-ic nature of Pascal's triangle.
Therefore the algorithm is:
Initialize the lengths array to the number of possible centers
Set the current center to the first center
Loop while the current center is valid:
       Expand to the left and right simultaneously until we find the largest palindrome around this center
       Fill in the appropriate entry in the longest palindrome lengths array
       Iterate through the longest palindrome array backwards and fill in the corresponding values to the right of the entry for the current center until an unknown value (because we don't have sufficient elements in the string to make an interpretation on the length) is encountered.
       Set the new center to the index of this unknown value
Return the lengths array
Courtesy: Fred Akalin 2007

If we have a continuous stream of letters, we can find the palindrome for the string upto that character and repeat.
Otherwise the method above is also online in its processing.

#codingexercise2
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
This is equivalent to finding the kth element where k = (m+n)/2

if (m+n)%2 != 0
   return findkth(A, B, (m+n)/2, 0, m-1, 0, n-1);
else
   return (findkth(A,B, (m+n)/2, 0, m-1, 0, n-1)
              + findkth(A,B, (m+n)/2 - 1, 0, m-1, 0 , n-1)) / 2;


int findKth(A, B, k, astart, aend, bstart, bend)
{
   int alen = aEnd - aStart + 1;
   int blen = bEnd  - bStart + 1;

 // special cases
  if (aLen == 0)
       return B[bStart + k];
  if (bLen == 0)
       return A[aStart + k];
  if (k == 0)
       return A[aStart] < B[bStart] ? A[aStart]  : B[bStart];
 

  int aMid = (aLen* k)/ (aLen +bLen);
  int bMid = k - aMid - 1;
 
 aMid = aMid + aStart;
 bMid = bMid + bStart;

if (A[aMid] > B[bMid])
{
   k = k - (bMid- bStart +1);
   aEnd  = aMid;
   bStart = bMid + 1;
}else{
  k = k - (aMid - aStart + 1);
  bEnd = bMid;
  aStart = aMid + 1;
}
return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}

or we can merge the two arrays and find the middle element.

#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

Find missing numbers in a contiguous sequence and express them as a string of ranges.
For example,
124569 should output 3,7-8
String GetMissingNumbers(List<int> numbers)
{
string ret = string.empty;
numbers.sort();
if ( numbers.Count() <= 1) return ret;
for (int i = 1; i < numbers.Count(); i++)
{
if (numbers[i] - numbers[i-1] == 2)
   ret += (numbers[i-1] + 1).toString() + ",";
if (numbers[i] - numbers[i-1] > 2)
  ret += (numbers[i-1] + 1).toString() + "-" + (numbers[i]-1).toString() + ",";
}
return ret;
}
The above is O(n)
We can make it O(log n) with below:

void GetMissing(List<int> numbers, ref List<string> result, int start, int end)
{
if (start < end)
{
mid = (start + end)/2;
GetMissing(numbers, ref result. start, mid);
GetMissing(numbers, ref result, mid+1, end);
Merge(numbers, result, start, mid, end);
}
}
void Merge(List<int> numbers, ref List<string> result, int start, int mid, int end)
{
// constant time operation
if (numbers[mid] - numbers[start] == mid - start &&
     numbers[end] - numbers[mid+1] == end-(mid+1) &&
     numbers[mid+1] - numbers[mid] <= 1) return; // assume sequence is already sorted
if (numbers[mid+1] - numbers[mid] == 2)
   result.Add (numbers[mid] + 1).toString();
if (numbers[mid+1] - numbers[mid] > 2)
  result.Add(numbers[mid] + 1).toString() + "-" + (numbers[mid+1]-1).toString() ;
}

result.Join(",")

Today we continue the set of coding exercise with different orders of traversal. This time we include levelwise traversal with InOrder. Again we fallback on our argument that the left and right tree need to be separated by root node in at least one sequence to make it easier for the tree to be rebuild.

                    A

             B            C

        D      E          F     G

H    I    J    K         L   M    N    O
Pre:     A  B  D  H  I  E  J  K  C  F  L  M  G  N  O
Post:    H   I   D  J   K E B  L  M F N   O  G  C   A
In:       H   D   I  B   J  E K A  L  F M   C  N  G   O

Level  NULL A  NULL B  C  D  NULL  E F G  H  NULL I   J  K  L M  N   O NULL

We iterate the nodes level wise so we know that the parents are traversed before the children are.
for any node we try to rebuild, we have the inorder give us the left-subtree +  root  + right-subtree going forward. Each sub-tree is found till a node upto a parent . For example, E has sub trees in the inorder upto B on one side and upto A on the other side. A has subtrees to the extremes because it is the root. The siblings are found in their respective subtrees as occuring in the next level.


Node Rebuild(List<Node> level, List<node> in) // All nodes in list initialized with left and right = null and set only with data
{
assert( level!= null && in != null);
assert (level.Count() == in.Count());

for(int i =  level.Count(); i > 0; I--)
{
     Node root = level[I];
     int inIndex= Array.indexOf(in, level[i]);
     Node left = in.First( x => Array.indexOf(level, x) < i);
     Node right = in.First( x => Array.indexOf(level, x) > i );
     int left = Array.indexOf(in, left);
     int right = Array.indexOf(in, right);
     int left-tree-len = inIndex - left - 1;
     int right-tree-len = inIndex - right - 1;
     Node leftSibling = findNextLevelOccurrenceFromSubtree( level, in,  i, left, -1, inIndex);
     Node rightSibling = findNextLevelOccurrenceFromSubtree(level, in, i, -1, right, InIndex);
     root.left = leftSibling;
     root.right = rightSibling;
}
return level[0];
}

Node findNextLevelOccrrenceFromSubtree(
           List<Node> level, // the level list
           List<Node> in, // the in list
           int current, // the index in level of the current element
           int left, // left most position of subtree in inorder
           int right, // left most position of subtree in inorder
           int inIndex, // left most position of subtree in inorder
           )
{
while( current != null) current++;
current++;
if (left > 0){
for (int i = inIndex; i >= left; i--) // left subtree only
      for (int j = current; j != NULL; j++)  // next level only
     if (in[i] == level[j])
         return in[i];
}
if (right > 0)
{
for (int i = inIndex; i <= right; i++) // left subtree only
      for (int j = current; j != NULL; j++)  // next level only
     if (in[i] == level[j])
         return in[i];
}
 return NULL;
}
       

Yesterday we were discussing rebuilding a tree from post order and in order traversals.
Today we see if we can rebuild a tree from preorder and post order:
We make the following observations:
1) the roots are found top down by walking the post order list in the reverse manner or the preorder in the forward manner
2) the length of the left subtree for any root in preorder is given by the number of nodes between its position in the postorder and the start for the subtree of the parent.
3) the position of the start of the subtree of the parent is given by the start of the post order or the start of the sibling in the post order depending on whether it is the left or the right subtree
4) In general, we can rebuild the tree if we know the sizes of either left or right subtree consistently. We don't need both but if we do that's great.
5)  the length of the right subtree is the distance between the the position of the left sibling and the root in the post order.
6) The subtrees may be null and we just need to be mindful of the size but not need to check it upfront.
7) Since the items 2) and 5) indicate that we need to the postion of a sibling for at least the root of the whole tree to begin with, it is important to identify one of the siblings first.
8) if the element next to the root in pre is the same as the element previous to the same root in post, then one of the subtrees is null.
9) Since we cannot say which of the subtree is null from 8), this problem is not possible to solve.

Consider:
Pre: AB
Post BA
and
Pre: AC
Post: CA

                    A

             B            C

        D      E          F     G

H    I    J    K         L   M    N    O
Pre:   A  B  D  H  I  E  J  K  C  F  L  M  G  N  O
Post: H   I   D  J   K E B  L  M F N   O  G  C   A
In:    H   D   I  B   J  E K A  L  F M   C  N  G   O

Here too we see that unless the left subtree and the right subtree are listed once on both sides of the root, the solution becomes difficult. Therefore inorder traversal is needed.

#coding exercise

int GetSmallestNumberListed(string number, int n) // assume unique

{

if (String.IsNullorEmpty(number) || n <= 0) return null;

for (int I =0; I < numbers.Length; I++ )

{

     if (Char.IsDigit(numbers[I]) == false)

     {

          return -1;

     }

}    

string sorted = number.sort();

int returnLength = number.Length - n;

if (returnLength <= 0) return -1;

sorted = sorted.substring(0, returnLength);

String result = null;

for (int I = 0; I < numbers.Length; I++)

{

  var candidate = string.Empty;

  if (sorted.Contains(numbers[I]))

  {

      candidate += numbers[I];

      for (int j = I+1; j < numbers.Length; j++)

      {

          if (sorted.contains(numbers[j]))

          {

              if (candidate.Length >= returnLength) break;

              candidate += numbers[j];

          }

      }

      if (result == null)

      {

              result =  candidate;

      }

      if (candidate.Length == returnLength && String.CompareOrdinal(candidate, result) <= 0)

      {

              result = candidate;

      }

  }

}

return result;

}

#codingexercise
int GetMissingSerialNumber(List<int> num)
{
int sum_of_n = num.Count x (numCount + 1)/2;
return sum_of_n-num.sum();
}

The sorting would help narrow down the range with the missing numbers logarithmically if there were more than one.
int binarysearch(List<int> num, int target, int start, int end)
{
assert (start <= end);
int mid = (start + end)/2;
if (num[mid] == target) return mid;
if ( mid == start) return -1;
if (num[mid] < target)
       return binarysearch(num, target, mid + 1, end);
else
       return binarysearch(num, target, start, mid-1);
}

Yesterday we were discussing rebuilding a tree from post order and in order traversals.
We made the following observations:
1) the roots are found top down by walking the post order list in the reverse manner
2) the length of the right subtree for any root is given by the number of nodes between its position in the inorder and that of its parent.
3) the position of the left sibling in post order is at an offset equal to the length of the right subtree to the left of the root in post order. The position of the right sibling is immediately before the root.
4)  the length of the left subtree is the distance between the the position of the right sibling and the root in the in order.
6) The subtrees may be null and we just need to be mindful of the size but not need to check it upfront.

                    A

             B            C

        D      E          F     G

H    I    J    K         L   M    N    O
Post: H I D J K E B L  M F N O G C A
In:    H D I B J E K A  L  F M C N G O

Node Rebuild(List<Node> post, List<node> in) // All nodes in list initialized with left and right = null and set only with data
{
assert( post != null && in != null);
assert (posts.Count() == in.Count());

for(int i =  post.Count()-1; I >= 0; I--)
{
     Node root = post[i];
     int inIndex= Array.indexOf(in, post[i]);
     if ( I > 0 && I < post.Count())
     {
     Int parent = findParentIndex (Post, i); //parent occurs to the right of root in post with left,right set
     Int parentin = in.Count();// defaults to in.Count()
     if (parent < post.Count())
          parentin = Array.indexOf(in, post[parent]);
     Int righttreelen = parentIn-inIndex-1;
     if (i-righttreelen-1 > 0)
          Root.left = post [i-righttreelen-1];
     Int right = i-1;
     if (right > 0)
         Root.right = post [right];
}
return post[post.Count() - 1];
}

int findParentIndex(List<node>post, int current)
{
int target = post.Count();
for (int i = current+1; i< post.Count(); i++)
{
if ( post[i].left == post[current] ||
      post[i].right == post[current]){
     target  =  i;
     break;
     }
}
return target;
}

For performance gain, we also made the observation that the length of the right subtree need to be calculated only when we know that the right subtree is not null. We already know this if the index of the previous element (right sibling)  in post happens to have an inorder index less than that of the root.

Today we look at another coding problem along the same lines as the one we have seen in the previous post and the one before.
This time we have

// Postorder   C D B F E A
// Inorder       C B D A E F
// Build tree

We use relative comparisons which has worked for us before. Let us take the example of  our elemental subtree of a root with two siblings.
   J
K  L

1) All three nodes
    Post: K L J
    InOrder: K J L
2) Only left -subtree
    Post: K J
    In: K J    // L is missing because the previous element in post order lies within inIndex < that of J
3) Only right-subtree
    Post: L J
     InL J L  // K is missing when no elements appear before J whose inIndex < that of J
4) only root
Post:     Prev root Next
In :        Prev some-others root yet-others Next
4) is not differentiable from 2)

In general, with arbitrary sub-trees  for siblings
// left-subtree missing when
Previous node in pre appears to the rightof inIndex of root in inorder
// right-subtree missing when
previous element is left subtree in post order.

the sizes of the left and right sub tree can be kept track of because we use the same predecessor technique

                    A

             B            C

        D      E          F     G

H    I    J    K         L   M    N    O
Post: H I D J K E B L  M F N O G C A
In:    H D I B J E K A  L  F M C N G O

Node Rebuild(List<Node> post, List<node> in) // All nodes in list initialized with left and right = null and set only with data
{
assert( post != null && in != null);
assert (posts.Count() == in.Count());

for(int i =  post.Count()-1; I >= 0; I--)
{
Node root = post[i];
int inIndex= Array.indexOf(in, post[i]);
if ( I > 0 && I < post.Count())
{
//todo
int inIndexPrev = Array.indexOf(in, post[I-1]);
// Ignore comments below
// Ignore : Instead of taking subtree lengths, can we detect if subtrees are null from pattern
//Ignore: int inIndexNext = Array.indexOf(in, post[I+1]);
//Ignore: if both left and right subtree is null, handle it separately,
// Ignore: if (in.Count() - 1 - inIndex > 0)
// Ignore:if (inIndexPrev < inIndex && inIndexNext > inIndex)  continue;
//otherwise keep track of right subtree length as the differences in inorder indexes

     Int parent = findParentIndex (Post, i); //parent occurs to the right of root in post with left,right set
     Int parentin = Array.indexOf(in, post[parent]); // defaults to in.Count()
     Int righttreelen = parentIn-inIndex-1;
     if (i-righttreelen-1 > 0)
          Root.left = post [i-righttreelen-1];
     Int right = i-1;
     if (right > 0)
         Root.right = post [right];

}
return post[post.Count() - 1];
}

The recursive solution online is as follows:
public TreeNode buildTree(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd)
return null;

int rootValue = postorder[postEnd];
TreeNode root = new TreeNode(rootValue);

int k = 0;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == rootValue) {
k = i;
break;
}
}

root.left = buildTree(inorder, inStart, k - 1, postorder, postStart,
postStart + k - (inStart + 1));
// Becuase k is not the length, it it need to -(inStart+1) to get the length
root.right = buildTree(inorder, k + 1, inEnd, postorder, postStart + k- inStart, postEnd - 1);
// postStart+k-inStart = postStart+k-(inStart+1) +1

return root;
}