We review another example of moving on a checkerboard . We are given an n by n checkerboard it's valid to move ftom any of the boxes on the bottom to goto any of the boxes in the top board.  A move can only be made to a square on the top left, directly above and a top right as long as they are within the square checkout  each move results in a positive or negative amount of money . We have to find the optimal set of moves that maximizes profit.
We apply dynamic programming by defining the opt optimal substructure.
The current position i,j can be moved to from one of three positions in the row below. Because we make an opt choice in this move, the previous set of Moves upto and inclusive of the previous position is also optimal.
Hence we define as recurrence relationship as

Next move = p [(i-1,j-1), (i,j)] + d (i-1,j-1)
                     = p [(i-1,j), (i,j)] +d (i-1,j)
                      =p[i-1, j+1 , (i,j)] + d (i-1, j+1)
And repeat for n steps.
The bottom up method would be like this:
let d[1..n, 1..n] and s[1 .. n-1, 2..n] be new tables for cost and index of optimal

for i = 1 to n

    d[i,i] = - infinity

for l = 2 to n // chain length

     for i = 2 to n-l+1

           j = i+l-1

           d[i,j] = - infinity

           q = max ( p [(i-1,j-1), (i,j)] + d (i-1,j-1)

                     , p [(i-1,j), (i,j)] +d (i-1,j)

                      , p[i-1, j+1 , (i,j)] + d (i-1, j+1))

                 if q > d[i,j]

                     d[i,j] = q

                     s[i,j] = k

return d and s


The top down strategy using recursion is as follows:

RecursiveStepping (i, j, d)

   If I == n-1
         Return d(i,j)
   Q = max (p [(i-1,j-1), (i,j)]+ RecursiveStepping (i-1,j-1,d)

                     , p [(i-1,j), (i,j)] +RecursiveStepping(i-1,j,d)

                      , p[i-1, j+1 , (i,j)] + RecursiveStepping (i-1, j+1, d))
    If q > d (i,j)
      D (i,j) = k
   Return d(i,j)

We review a coding question to determine the count of numbers that have 4 as a digit from 1 to n.

int getCount(int n)
{
  int count = 0;
  for (int i = 0; i < n; i++)
           if (has4(i)) count ++;
  return count;
}

bool has4(int n)
{
   while (x != 0)
   {
        if (x%10 == 4)
          return true;
        x = x / 10;
   }
   return false;
}

We review webhooks today. We discussed that they were useful for notifications in REST API implementation.

In addition, Web hooks do the following :
1) keep Data in sync
2) give other applications a chance to do something
3) provide necessary params on certain events

Web hooks take a URL to send the notification to. A "postbin" web service will receive and log the notifications so that it can monitor all POST HTTP requests it receives.  This URL is taken from a registration form hosted by the publisher.  When this notification arrives, the subscriber can choose to respond by making additional API calls based on the information in the notification.

If the registration is to be avoided, APIs can optionally take a callback parameter that takes in a URI. This way during the execution of this specific API, a POST method will be called on the URI provided with a predetermined template of information. This lets the caller subscribe and unsubscribe dynamically.

#codingexercise
Write an efficient program to reverse the bits of a number.
We do this by looping through the number and testing each bit. If the bit is set at position i then we set the bit at total_number_of_possible_bits -1 - i in the reverse number.
unsigned int reverseBits(unsigned int num)
{
unsigned int number_of_possible_bits = sizeof(num) * 8;
unsigned int reverse_num = 0;
for (int i = 0; i < number_of_possible_bits; i++)
{
int temp = (num & (1 << i );
if (temp)
    reverse_num |= (1 << ((number_of_possible_bits - 1) - i));
}
return reverse_num;
}

Another coding interview question is how to count the number of binary search trees that are within a numerical range?.
This can be found by performing  a  traversal
If the subtrees are in range the root is also in range.

bool getCount(Node root, ref count)
{
if (root == NULL) return true;
Bool l = false;
Bool r = false;
if (root.left) l = getCount(root.left, count);
if (root.right) r = getCount(root.right, count);
if ( l && r && inRange(root.left, root.right))
  count++
return false;
}

Another interview problem is schedule a meeting
Given an employee array of a large number of employees, find a window of time with maximum duration for a meeting that suits all the employees in the input.
Since each employee has different availabilities we can first find the availability ranges for each employee. This may result in a number of time Slots greater than the number of employees. Then taking time as increments of  time slices such as a minute, we can write them down as sequences. After that we can find the longest common subsequence. This approach can scale to any length and number of time range of employees when the time slice increments are more granular. It also finds a maximum number of employees who can make it to a meeting when all cannot.

This problem can be attempted in many ways but we focus on one based on max flow algorithm. The reason we choose maximum flow is because we want to find the window that is maximum.  We consider Ford Fulkerson algorithm.
Before using Ford Fulkerson, we have to transform the problem from multisource multisink to single source single sink by adding a consolidated source and a consolidated sink.  Each flow is considered as a viability for an employee and the max flow is when we can augment this flow for all the employees. We consider granular time slots for augmenting this maximum flow. Then we add increment timeslots for maximum duration of the meeting.

Matrix-chain-order problem.

A matrix chain order determines the optimal number of scalar multiplications needed to compute a matrix chain product. Even though matrix multiplication is associative, the order of parenthesizing the product impacts the cost of the product. This is because the order determines the number of scalar multiplications to be performed because a matrix multiplication cost is based on the columns of the preceding matrix to be multiplied with the number of rows from the succeeding matrix. Therefore, by fully parenthesizing the matrix product of A1, A2, … An matrices we can compute the total cost and consequently the optimal solution will have an order of multiplication corresponding to the lowest cost.

To solve this problem, we apply dynamic programming by following the four-step sequence:

1.     Characterize the structure of an optimal solution

2.     Recursively define the value of an optimal solution

3.     Compute the value of an optimal solution

4.     Construct an optimal solution from computed information

The first step can be performed by arguing that finding the optimal solution of the product of A1, A2 … An  is the same as finding the optimal solution of two subproblems obtained by splitting the range into two involving A1…Ak and Ak+1 …An and then combining these optimal subproblem solutions.

Next the recurrence is described with a termination condition as zero cost multiplication when the chain consists of only one matrix. The progress condition can be described as the minimum cost for the range i to j as the minimum of the sum of the cost associated with the sub problems plus the scalar multiplication cost of the results where this sum is calculated one for each chosen k before taking the minimum.

Step 3 can be performed by using a bottom up approach. Given that each matrix Ai has pi-1  x pi dimensions, a bottom up approach solves incremental dimensions so that the solution of the matrix involving previous dimensions can be readily looked up. There are two tables maintained – one that stores the cost of computing a matrix chain product and another auxiliary table that records which index k achieved the optimal cost in computing the cost stored.

Finally we can compute the optimal solution using the auxiliary index table above.  We can find the k from the auxiliary table that stores it. We can determine the earlier matrix multiplications  recursively since s[1,s[1,n]] determines the last matrix multiplication when computing the preceding component and the s[s[1,n]+1,n] determines the last matrix multiplication when computing the succeeding  component of the product of the two subproblems. Again the termination condition is the single element chain.

Moreover, as with dynamic programming problems with bottom-up approach, there is also a corresponding recursive solution using a top down strategy and optional memorization to improve efficiency . That top down stragey is based directly on the recurrence mentioned above. We still maintain a table of costs but the order of filling the table is more like the order of recursion.

The bottom up strategy:
Matrix-Chain-Order(p)
n = p.length - 1
let m[1..n, 1..n] and s[1 .. n-1, 2..n] be new tables for cost and index of optimal
for i = 1 to n
    m[i,i] = 0
for l = 2 to n // chain length
     for i = 1 to n-l+1
           j = i+l-1
           m[i,j] = infinity
           for k = i to j-1
                 q = m[i,k] + m[k+1,j] + pi-1pkpj
                 if q < m[i,j]
                     m[i,j] = q
                     s[i,j] = k
return m and s

The top down strategy:
Recursive-Matrix-Chain(p, i, j)
if i == j
    return 0
m[i,j] = infinity
for k = i to j - 1
    q = recursive-matrix-chain(p,i,k) + recursive-matrix-chain(p, k+1,j) + pi-1pkpj
    if q < m[i,j]
       m[i,j] = q
return m[i,j]

#codingexercise

/***

Add 2 numbers represented as linked list and return the resulting sum as a linked list.

How are numbers represented as linked list?

Suppose we have 459, it is represented as:

4->5->9->null

So 4 is the head and 9 is the tail.

Say we are given 2 numbers like: 459 and 891, their sum is 1350. That will be represented as:

1->3->5->0.

Implement the function that takes head pointer of 2 numbers as linked list and

returns a head pointer to a new linked list, which is basically the sum of both the numbers.

***/

Node GetSum(Node root1, Node root2)

{

// read the value from root 1

int val1 = GetValue(root1);

// read the value from root 2

int val2 = GetValue(root2);

// write the value of root1 + root2

if ( val1 + val2 < val1 || val1 + val2 < val2) // overflow

   return NULL; // or raise exception

return WriteValue(val1 + val2);

}

Node WriteValue(int val)

{

  Node root = NULL;

  int v = val;

  int len = 0;

  while (v != 0 ) {

    len = len + 1;

    v  = v / 10;

  }

  v =  val;

  Node Prev = null;

  for ( i = 0; i < len ; i++)

  {

    var n = new Node();

    n.Data = (Math.floor(v / Power(10, len - i - 1))) % 10;

    n.Next = Null;

    if (Prev) {

        prev.next = n;

        prev = n;

    }

    else

        root = n;

       

  }

  return root;

}

int GetValue(Node root1)

{

Node cur = root1;

int val1 = 0;

int len = 0;

while(cur) 

{

  

   len = len + 1;

   cur = cur.Next;

}

// len = 2

cur = root1;

for ( i = 0; i < len; i++)

{

  val1 += cur.Data * Power(10, len - i - 1);

  cur = cur.Next;

}

// val1 = 29

}

NULL list2

list1 NULL

UnitValue List2

list1 UnitValue

ArbitraryValue List2

List1 ...

Overflow & Underflow

Codingexercise:
Given a linked list say
LL = 1-2-3-4 and the position k = 2, swap the nodes k and n-k such that the output now becomes:
1-3-2-4

Node Swap(Node left, Node right, Node prevleft, Node prevright, Node root)
{
  Assert(left != NULL  && right != NULL)
  // prevleft left leftnext prevright right nextright
  // prevleft right leftnext prevright left nextleft
  if (left == right) return root;
  Node leftnext  = left.next;
  Node rightnext  = right.next;
  left.next = rightnext;
  if(prevright && prevright != left) { Prevright.next  = left; }
  // if (prevright && prevright == left) {left.next = rightnext;}
  if (leftnext != right) right.next= leftnext;
  else {right.next = left;}
  if(prevleft) { Prevleft.next = right;}
  else return right;
  return root;
}

Node SwapKth(Node root, int K);
{
 int len = 0;
 Node cur = root;
 while(cur){
     len = len + 1;
     cur = cur.next;
 }
 Node left = root;
 Node Prevleft  = root;
 Node right = root;
 Node Prevright = root;
 if (K < 0) return root;
 if (K  > len) return root;
 for (int i = 0; i < K-1; i++){
     Prevleft = left;
     left = left->next;
     }  
 for (int i = 0; i <  len-K; i++){
     Prevright = right;
     right = right->next;
 }
 if (K > len - K)
 {
 temp = left;
 left = right;
 right = temp;
 temp=prevleft;
 prevleft = prevright;
 prevright = temp;
 }
 if (left && right)
   return Swap(left,right, prevleft, prevright, root);
 return root;  
}
Test cases:
Empty Set
NULL 1
1 NULL
1 2 ( checks in the swap function)
1 2 K = 0
1 2 K = 1
1 2 K = 2
1234 K = 2
Prevleft left right PrevRight
1          2    3    2
1          2    2    1
1          2    5    4  len = 6 K = 2
3          4    1    NULL  len = 4 K = 4
NULL       1    4    3

This was an actual interview question. How do you improve high availability  and low latency. My answer was you improve HA with fault tolerance and at least one fail over server. For low latency, you don't do anything as an application programmer. You delegate it to Web accelerators and data deduplicators. If the application was talking to another instance of itself, then it could make its protocol less chatty.

Today we discuss another LeetCode challenge. This is  a problem on Surrounded regions Give a  2D board containing X and O, capture all regions surrounded by X. A region is captured by flipping all O's in Xs
Here the O that lies on the boundary and those that are connected to it are exempt. Everything else can be captured. Consequently we work our way from outwards boundary and distinguish these Os by calling them say Y.After each boundary is considered, we eliminate it and repeat the step for the inner 2D board.

We use a method IsAdjacentAMatch(Position p, Piece  item) that tests each of the eight positions adjacent to the current position for a match with the given item  - say an X or a Y or a O.
For each of the elements on the border, we consider the adjacents and if they are O, we convert them to Y.
Finally for all the non-Ys we make a pass through the board and convert them to X.
void IsAdjancentAMatch( Position p, Piece item)
{ int x = P.x;
   int y  = P.y;

 // test x-1,y-1
 // test x-1,y
// test x-1, y+1

// test x, y-1
// test x, y+1

// test x+1, y-1
// test x+1, y
// test x+1,y+1

// In each of the test above for a match with Y or O, if its within the Board, mark it with Y
}

public class Solution {
    public void Solve(ref char[,] board, int top_left_x, int top_left_y, int bottom_right_x, int bottom_right_y) {
                    // termination condition
                    if (bottom_right > top_left) return
                   // Take the elements along the border of the board
                    // 0th row
                   // last col
                   // n-1th row
                   //  first col
                  If any element has an adjacency with Y, mark it Y
                     // Recurse with the inner board ( current board without the border)
                     Solve(ref b, top_left_x + 1, top_left_y + 1, bottom_right_x - 1, bottom_right_y -1)

    }
}

#codingexercise
Double  GetNthRootProductAlternateTermRaisedPDividedQoverPTimesQ PminusQ(Double [] A,Double  p, Double q)
{
If ( A== null) return 0;
Return A.NthRootProductAlternateTermRaisedPDividedQoverPTimesQPminusQ(p, q);
}