#coding questions
1) Given a cost matrix cost[,] with positive integers find the minimum cost between a target cell and origin. The permitted moves are right, down and down right.
void GetMinCost(int[, ] cost, int rows, int cols, int x, int y, ref sum )
{
if ( x < 0 || y < 0 ||  x >= rows || y>= cols) {sum += INT_MAX; return;}
sum += cost[x,y];
if (x == 0 && y == 0) return;
sum += min( GetMinCost(cost, rows, cols, x-1,y-1, ref sum),
                   GetMinCost(cost, rows, cols, x,y-1, ref sum),
                   GetMinCost(cost, rows, cols, x-1,y, ref sum);
}

2) Buy or sell 1 stock many times on different days to maximize profit from a daily price list

int GetMaxProfit(List<int> prices)
{
int start = prices[0];
profit = 0;
for (int i = 1; i < prices.Count; i++)
{
if ( prices[i] < prices[i-1])
{
  profit += prices[i-1]-start;
  start = prices[i];
}
}
if (prices.Count > 0)
{int last = prices[price.Count-1] ;
   if (last > start)
       profit += last -start;
}
return profit;
}

Reverse a linked list
Node* reverse(node* root)
{
if (root == null) return null;
Node* prev = null;
Node* cur = root;
while(cur)
{
Node* next = cur->next;
cur->next = prev;
prev = cur
cur = next;
}
return prev;
}


1->2->3
3->2->1

Today we are going hiking down the Snoqualmie falls.

Design of an Email Campaign system:

Email Campaigns are often required in the lines of work that involves customers for the resources they request. Such campaigns often involve a subset of the people who are chosen based on some criteria. The mails to them also have different format and content depending on the nature of the campaign. Furthermore, email templates may need to be filled before they can be sent out and there may be retries involved.

A system that enables campaigns to be generated is a good candidate for automation as a background job. Let us look at this job in a bit more detail:

1)      First we need a way to specify the criteria for selecting the email recipients. This can be done with a set of logical conditions using ‘or’ and ‘and’ operators. Each condition is a rule and the rules may have some order to it. Consequently the rules do not necessarily fit in a table. They are best expressed as a stored procedure with versioning.  If the data to filter resides in a table such as say the customers table, then the stored procedure resides as close to the data as possible.

2)      The message may need to be formatted and prepared for each customer and consequently these can be put in a queue where they are appropriately filled and made ready. A message broker comes very useful in this regard. Preparation of emails is followed with sending them out consequently there may be separate queues for preparation and mailing out and they may be chained.

3)      The number of recipients may be quite large and the mails for each of them may need to be prepared and sent out. This calls for parallelization. One way to handle this parallelization would be to have workers spawned to handle the load on the queue. Celery is a good example of such a capability and it works well with a message broker.

4)      A web interface to generate campaigns can be useful for administrators to interact with the system.

The data flow begins with the administrator defining the campaign. This consists of at the very least the following: a) the email recipients b) the mail template c) the data sources from which to populate the databases and d) the schedule in which to send out the mails. 

The email recipients need not always be specified explicitly especially if they number in millions. On the other hand, the recipients may already be listed in a database somewhere. There may only be selection criteria for filtering the entire list for choosing the recipients. Such a criteria is best expressed in the form of a stored procedure. The translation of the user defined criteria into a stored procedure is not very hard. The user is given a set of constraints, logical operators and value inputs and these can be joined to form predicates which are then entered as is into the body of a stored procedure. Each time the criteria are executed through the stored procedure, the result set forms the recipients list. When the criteria change, the stored procedure is changed and this results in a new version.  Since the criteria and stored procedure are independent of the message preparation and mailing, they can be offline to the mailing process.  

The mailing process commences with the email list determined as above.  The next step is the data that needs to be acquired for each template. For example, the template may correspond to the resources that the recipients may have but the list of resources may need to be pulled from another database. It would be ideal if this could also be treated as SQL queries which provide the data that a task then uses to populate the contents of the email. Since this is per email basis, it can be parallelized to a worker pool where each worker grabs an email to prepare.  An email receives a recipient and content.  Initially the template is dropped on the queue with just the email recipient mentioned. The task then manages the conversion of the template to the actual email message before putting it on the queue for dispatch. The dispatcher simply mails out the prepared email with smtp.  

The task parallel library may hide the message broker from the parallelization. Celery comes with its own message broker that also allows the status of the enqueued items to be logged. However, a fully fledged message broker with a worker pool is preferred because it gives much more control over the queue and the messages permitted on the queue. Moreover, journaling and logging can with the automation. Messages may be purged from the queue so that the automation stops on user demand. 

Therefore data flows from data sources into the emails that are then mailed out.  The task that prepares the emails needs to have access to the database tables and stored procedures that determine who the recipients are and what the message is. Since they act on individual email basis, they are scalable.   

Conclusion: An Email campaign system can be written using a database, a message broker and celery.

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

void Interleave(Node root){
Node start = root
Node end = find_last(start);
int count = 0;
for(Node cur = start; cur; cur=cur.next) count++;
while ( count > 0)
{
    Remove(start, end);
    Insert(start, end);
    if (start.next)
    {
         start = start.next.next;
    }
    end = find_last(start);
    count -= 2;
}
}
Node find_last(Node start)
{
Node end = start;
for(Node cur = start; cur; cur=cur.next){
      end = cur;
}
return end;
}

void Remove(Node start, node end)
{
Node prev = start;
Node target = start.next;
for(Node cur = target; cur && cur.next; cur=cur.next){
      prev = cur;
}
assert(cur == end);
if (prev && prev.next == end)
     prev.next = end ? end.next : null;
}

void Insert(Node position, node end)
{
if (end)
{
    end.next = position.next;
}
position.next=end;
}

Today we revisit a few graph algorithms.
The breadth first search
BFS(G,s)
 for each vertex, initialize color, parent and distance
 set the start vertex color to gray
 enqueue the start vertex
 while the queue is not empty
       for each of the adjacent vertices of the dequeued vertex
        if its not been visited
               color the vertex as gray and set its parent and distance
               enqueue this vertex
       color the vertex as visited

DFS(G)
for each vertex u belonging to the graph, initialize it
for each vertex u belonging to the graph,
      if color of vertex is white,
          DFS-Visit(the vertex)

DFS-Visit(G,u)
for each adjacent vertex
     DFS-Visit(G,u)

MST-Kruskal
// This joins two distinct trees
A = null
for each vertex v in G
     Make-Set(v)
sort the edges of G, E into non-decreasing order by weight
for each such edge (u,v)
     if Find-set(u) <> Find-set(v)
        A = A union (u,v)
         Union(u,v)
return A

MST-Prim
// this grows a tree
A = null
for each vertex v in G, initialize the key and the parent
Initialize a min-priority queue Q with vertices
while the Queue is not empty
       extract the vertex with the minimum edge distance connecting it to the tree
       for each adjacencies v of this vertex u
              set the key to the weight(u,v) and parent

Dijkstra's shortest path algorithm
Other than source vertex, mark all as max distance no parent
Initialize a min-priority queue Q with vertices
while the Queue is not empty
     extract the minimum vertex u of Q
             add it to the shortest path
             for all vertices adjacent to u,
                   relax the vertices

All-Pairs-shortest-path (predecessor matrix, src, dest)
if src==dest
    print src
else if parent(dest) == null
    print "no path"
else all-pairs-shortest-path(predecessor matrix, I, parent-srcdest)
    print dest

Floyd-Warshall gives shortest path weighs matrix
dij with no intermediary vertices  =  edge weight
        = min(dij k-1 , dik k-1 + djk k-1 ) when # intermediary vertices k >=1

for k = 1 to n
   D for k be a new nxn matrix
   for I = 1 to n
      for j = 1 to n
         dij(k) = min(dij(k-1), dik(k-1) + dkj(k-1))

return Dn

int BuyOrSellOnce(List<int> prices, ref int start, ref int end)
{
int min = 0;
int min_index = start;
int max_index = start;
int max_profit = -1;
for (int i = start; i < end; i++)
{
if (prices[i] < min)
     min = prices[i]
if (prices[i] - min > max_profit){
    max_profit = prices[i] - min;
    max_index = i;
   }
}
start = max_index+1;
end = prices.Count -1;
return max_profit;
}
int BuyOrSellManyTimes(List<int>prices)
{
int start = 0;
int end = prices.Count-1;
int max_profit = -1;
int profit = BuyOrSellOnce(prices, start, end);
while (profit != -1) {
max_profit += profit;
profit == BuyOrSellOnce(prices, start, end);
}
return max_profit;
}

int main() {
//code
int* p = new int[5];
p[0] = 3;
p[1] = 1;
p[2] = 2;
p[3] = 4;
p[4] = 5;
printf(getminindex(p,5))
return 0;
}


int getminindex(int[] p, int n)
{
int min = 0;
for (int i = 0; i < n; i++ )
   for (int j = i+1; j < n; j++)
   {
     if (p[j] >= p[i] && j - i > min)
            min = j-i;
   }
return min;

}

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.