We review a few more coding problems.
Node TreeSuccesor (Node root)
{
If root.right return TreeMinimum (root.right);
Node x = root;
Node y = root.parent;
while ( y && x == y.right)
  {
      x = y;
      y = y.parent;
   }
return y;
}
Another one is about merging a few time intervals
Collapse(List<Tuple<int,int>> intervals)
{
var cmp = new IntervalComparator();
intervals.sort(cmp); //
var s = new Stack<Tuple<int,int>>();
s.Push(interval[0]);
for (int I = 0; I< intervals.count; I++)
{
var top = s.top();
if (top.end < interval[I].start)
    s.push(interval[I];
else if (top.end < interval[I].end){
        top.end = interval[I].end;
        s.pop();
        s.push(top);
}
}
while (!s.empty())
{
Interval t = s.top();
console.writeline("{0}-{1}",t.first, t.second);
s.pop();
}
}

Another one is about finding max subarray:
int GetMaxSubarray(List<int> items)
{
int x = 0; // sum
int y = 0; // minimum sum
int z = 0; // maximum sum
for( int I =0 ; I < items.Length; I++)
{
x  = x+ items[I];
if (x < y)
     y = x;
if (x-y > z)
    z = x-y;
}
return z;
}

Another one is about beating the stock market. We are given  an array for which the ith element is the price of a given stock on day i. If we were only permitted to buy one share of the stock and sell one share of the stock, we have to find the best times to buy and sell to get the best deal.
int GetBestDeal(List<int> prices)
{
int min = 0;
int deal = -1;
for (int I = 1; I < prices.Count; i++)
{
if (prices[i] < prices[min])
    min = i;
if (prices[i] - prices[min] > deal)
    deal = prices[i] - prices[min];
}
return deal;
}

Find all pair paths in a graph
We use backtracking for finding all the paths.
void allpaths(int[,] graph, int n, int src, int dest, int threshold, ref List<int> candidatePath ...
for (int i = 0; i < adjacencies(src).Count; i++)
{
   // avoid cycles
   // avoid those exceeding threshold
   candidatePath.Add(adjacencies(src)[i]);
   candidateDist.Add(distances[i]);
   allpaths(graph, n, adjacencies(src)[i], dest, threshold, candidatePath ...
   candidatePath.Remove(adjacencies(src)[i]);
   candidateDist.RemoveAt(candidateDist.Count - 1);
}

Lets look at a few coding problems:
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

 we can use dynamic programming approach here:
int[] dp = new int[n+1];
for(int i = 1; i<n; i++)
   for(int j=1; j< i+1; j++){
       if (i+j<=n)
          dp[i+j] = Math.max(Math.max(dp[i],i)*Math.max(dp[j],j), dp[i+j]);

return dp[n];

We review a problem we discussed earlier to see another solution
Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n]inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

We said earlier that there is a dynamic programming approach :
If the range of sums that can be generated using the first k numbers in nums is from 0 to r, and the next number has value x, then either:
• x <= r+1 and it is possible to generate any sum from 0 to r+x using the first k+1 numbers, or
• x > r + 1 and it is not possible to generate the sum r + 1, since x and all the following numbers have greater values.
We keep adding x=r+1 and counting such additions until r meets or exceeds n.
We can say this another way. Let x be the smallest number that cannot be formed by the sum of the elements in the array . All elements 0< number < x can be formed. x starts at 1. If the next number is <= x, then the boundary is increased to x+next_number. If the next number is greater than x, then that means there is a gap and we need to insert a number. Inserting x is a choice is then that doubles the boundary and covers every number between the boundaries.
 int GetMinPatches(List<int> nums, int n)
{
int count = 0;
int x = 1;
int I = 0;
while (x < n)
{
     if (I < nums.Count && nums[I] <= x){
         x= x + nums[I];
         I++
        } else{
         x = x+ x;
         count++;
     }
}
return count;
}

Top ten programming interview questions visited
Today I found a list of problems discussed as the most often asked interview questions and could not resist bringing them up here albeit briefly:
They are:
Evaluate Reverse Polish Notation, Longest Palindromic Substring, Word Break,
Word Ladder, Median of Two Sorted Arrays, Regular Expression Matching, Merge Intervals, Insert
Interval, Two Sum, 3Sum, String to Integer, Merge Sorted Array, Valid Parentheses, Implement
strStr()(), Set Matrix Zeroes.

SetMatrixZeroes - Given a m * n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Hint: Use the first row and first column to mark the zero row and column. We only need to remember what the final states for first row and column should be, then we can use the markings there to flip the values.

Implement strStr() Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Hint: Use O(N^2) naive implementation or a pattern matching algorithm such as KMP or the matchHere() method discussed earlier in this blog.

Valid Parentheses: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not. Hint: Use a map with key-values as opening and closing brackets respectively and a stack for the occurrences pushing the opening and checking the values.

Merge sorted array - There are two sorted arrays that need to be merged into one. If you order the arrays by their lengths, you can have fewer instructions for your code.

StringToInteger Here the first character could be + or - aside from the edge cases. The regular representation can then multiply the result by 10 and add the next character.

3Sum - Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Hint: Use combinations that are 3 integers long and then select the ones that sum to zero.

2Sum - This does not involves generating combinations because the complement of the current number can be found as O(N^2).

InsertInterval - Insert into non-overlapping ranges, merge if necessary. Hint:  By insertion we handle the cases when an overlap with the current range. If there are more than one range that has overlap with the new, we split the new range at the point where the start of an existing range occurs in the new.
void Merge(Tuple<int, int> current, Tuple<int, int> new)
{
assert (previous.overlap(new));
var insert = new Tuple<int,int>{ Math.min(previous.first, new.first, previous.), Math.max(previous.second, math.second))}
return insert;
}


MergeIntervals - Given a collection of intervals, merge all overlapping intervals.
This does not involve O(N^2). We could do it linear if we keep the ranges sorted with a comparator that checks the start of each element. Then we can find out the ends that overlap and merge as above.

Regular Expression Matching - There is a LeetCode solution for this that handles the pattern lengths 0 and 1 separately and case as follows:
            int len = s.length();
            int i = -1;
            while(i<len&& (I < 0 || p.charAt(0) == '.' || p.CharAt(0) == s.charAt(I))){
                 if (isMatch(s.substring(I+1), p.substring(2)))
                     return true;
                 i++;
            }
            return false;

Median of two sorted arrays - This was already discussed in the previous post.
WordLadder: Given a dictionary find the minimum of one-letter substitution transformations between one word to another. Breadthfirst traversal will help with the tree search to get from one node to another.

wordbreak - this was already discussed. The Leetcode solution suggests a dynamic approach with
Define an array t[s.length+1] such that t[i]==true => 0-(i-1) can be segmented using dictionary
Initial state t[0] == true
        for(int i=0; i<s.length(); i++){
            //should continue from match position
            if(!t[i])
                continue;

            for(String a: dict){
                int len = a.length();
                int end = i + len;
                if(end > s.length())
                    continue;

                if(t[end]) continue;

                if(s.substring(i, end).equals(a)){
                    t[end] = true;
                }
            }
        }

        return t[s.length()];

Longest Palindromic substring already covered in previous post
Reverse polish notation - Here we use a stack and push the numerals. When we encounter an operator, we pop the stack and apply the operation.

 

#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(",")