monitoring and alerts

Systems have to be monitored round the clock for availability and readiness. Sincethis is a tedious time consuming process, each component that is added to thesystem is responsible for its own health and to attract attention when somethinggoes wrong. While there may be many ways to call for attention, they systemadministrator can facilitate a sink for collecting such monitoring information. Forexample, a logging handler or an email handler can be added to the system. Ofcourse, components will have to judiciously use levels for the alarms they raise.However monitoring need not be intrusive or inlined by the components. Healthchecks such as whether an application is running or suspended or crashed can bedetermined by the platform it is running on. These non-invasive handlers work at a layer different from the one for the components.  
Take dtrace for example and this gives great visibility to the platform it operates on, but it requires turning on instrumentation and targeting the malfunctioning item – both of which have their own overheads. Instrumentation overheads and impact involves: 

Slowing down the system 

Setting or targeting the malfunctioning item

Affect the timing of certain operations where problems don’t surface anymore 

Require tremendous amount of setup especially when trying to nail the culprit. 

And above all else, it works against the performance of the system.  

If the components give out some kind of response, then tools such as packet sniffers give a lot of information without being intrusive. Such non-intrusive techniques are often preferred over intrusive ones because they don’t affect the system and the same time, have the ability to capture all the requests and responses for analysis. 

It is not recommended however to require periodic API requests and responses for a notion of heartbeat or pulse on the application.  Such requests and responses are unnecessary when the same information can be gleaned via the levers provided by the sophisticated platform or engine with which the application runs. 

Monitoring can be automated so that human intervention can not always berequired but certain actions are required to attract attention and these are called alerts. Monitoring and alerts often go hand in hand allowing administrators to focus on investigating the system only when there is a problem. The alerts are typically preferred to be in mail format but even banner messages, pop-ups and flash can be used. The information in these alerts are more actionable than just the monitoring results. Typically they advice on the remedy actions as well. These therefore are complimentary to the monitoring efforts. An example of the monitoring and alertsinfrastructure can be seen inhttp://1drv.ms/1BPk7Hn 

#codingexercise
Count the number of prefixes in a dictionary using a trie 

Pseudocode :
Struct trie {
Integer words;
Integer prefixes;
Reference edges [26];
}

countPrefixes(vertex, prefix) k=firstCharacter(prefix)
 if isEmpty(word)
      return vertex.prefixes
 else if notExists(edges[k])
      return 0
 else cutLeftmostCharacter(prefix)
      return countWords(edges[k], prefix)

Today we continue with one more problem solving discussion. We look at  box stacking problem. We are given a set of n types of rectangular three dimensional boxes of length Li width WI and height hi . We have to stack the boxes so they for tallest tower. Each box must sit on top of a bigger or equal box and there can be many boxes of the same size. A rectangular box can be rotated so that it can lay on any of its faces.
This problem is similar to the previous increasing subsequence we have seen. We generates all the three base areas for a rectangle of a box. Then we sort them in increasing order. At this point, the pro lem is that of finding the longest common subsequence of height hi
Let MSH (i) be the  max height of the tower.
MSH (i) = max ( MSH (j) + height hi)  when w × l (j) is bigger and j < I and
If no such MSH (j) exists then MSH (i) = h (i)
This we can write as

for (int i = 1; i < n; i ++)

     for (int j = 0; j <i; j++)

         if (w (j)*l(j) > w (i)*l (i) && max (MSH (j) + h (i)) > msh (i)
                MSH (i) = max (MSH (j) + h (i))

To get the maximum overall stack height, we return the max (MSH (i)) where 0 < I < n

We now look at a problem that involves backtracking instead of dynamic programming.
Let us say we want to color the map of United States such that no two bordering states have the same color.  We are allowed to use four colors : red orange green and blue
Let us say we number the states say from  1 to 50 and we denote the current state with the number n
Let us say we consider each color for a state say denoted by c. If its' valid we choose the color and try to recursively find solutions applying that color for the n+1 going forward. If we found a solution applying this color or during the termination check when n == 50 then we return true. For backtracking, we remove the color and proceed with the next color as candidate. Finally we return false if we didn't find a solution using up all the available colors.

bool findColors(int n, Pair<int,color> states)
{
 if (n == 51) { 
    printColors();
    return true;
}
    foreach (color c in colors) {
      if (isValid(c,n)){
           states[n] = c; //apply color
           if (findColors(n+1, states))
              return true;
           states[n] = '/0';//remove color
        }
    }
  return false;
}
Back tracking never considers an invalid option and reduces the number of options from the permutations.

Today we look at a few more problem solving.
First we look at a balanced partition of an array C of numbers such that the same of the two partitions have very little difference.  Typically the partitions have half the total sum The numbers are each in the range 0 < x < k
This is also a dynamic programming problem. We create a boolean array T of size N + 1. T[x] will be true only if and only if there is a subset whose sum = x when we have this boolean array, we take the T[N/2] value. If this is true then there is a subset that adds up to this value.
We take C[i] and look at the table T. When we consider a new number C[i], we could simply ignore the number or include it. It may be possible to make the sum without including it. Now consider some location T[j] that has a one in it. It corresponds to some subset of numbers that adds up to the required sum. When we include C[i], we get a new sum C[i] + j and the corresponding T[j+sum(C[i])] should be set to true as well.
for (int i = 0; i < n; i ++)
     for (int j = N - C[i]; j>= 0; j--)
         if (T[j] ) then T[j+C[i]] = true;

return T[n/2]

N is the total sum
T is the boolean array with the first element set to True and everything else False.

#codingexercise

Double  GetNthRootProductAlternateTermRaisedPPlusQoverPTimesQ (Double [] A,Double  p, Double q)

{

If ( A== null) return 0;

Return A.NthRootProductAlternateTermRaisedPPlusQoverPTimesQ(p, q);

}

Today we review some more coding problems. Let us take a look at uni-color triangles. You are given  10 points in a plane such that no three of them are collinear Each pair is connected by a green dash or a blue solid line How many uni color triangles with vertices at the given points are possible.
Since we know that it takes three points to form a triangle, the total number of triangles possible is 10 choose 3 = 120. This number three is helpful. In a multicolored triangle, two edges of the triangle will be the same color. Moreover, multicolored triangles + unicolor triangles = 120.  Therefore we attempt to find unicolor triangles by finding the number of multicolored triangles. We make a table of the number of green and blue edges incident on each vertex. For e.g.:
Point   1 2 3 4 5 6 7 8 9 10
Blue    3 2 5 6 5 3 3 2 7 4
Green  6 7 4 3 4 6 6 7 2 5
We can now multiply the number of green and blue edges incident to the given points, and sum the products to find all possible multicolored triangles but each multi color triangle is counted twice because the ways to choose two edges of the same or different color still results in the same triangle. Therefore the number of uni-color triangle possible is 120 - 174/2 = 33 for the given table.
The problem is reduced from nChoose2 with complexity of O(n3) to counting n choose two edges O(n^2)  for each of the vertices.
Thus instead of writing a combinatorial coding solution as

Void CombineToTriangles (Edges a, EdgeBuilder b, int start, int level) 
{ 

   For (int I  = start ; I < a.Length; i++) 
   {  
       If (b.Length == a.Length) print b; 
       b[level] = a[i]; 
       Print b.ToTriangles(); 
       If (I < a.Length) 
            CombineToTriangles(a,b, start+1,level+1) 
       b[level] = ‘/0’; 
   } 
} 
we can reduce the problem to n!/(n-3)!3! - Sum-for-i-from-1-to-n(Blue-i * green-i / 2)

#codingexercise
Double  GetNthRootProductAlternateTermRaisedPPlusQoverPDividedQ (Double [] A,Double  p, Double q)
{
If ( A== null) return 0;
Return A.NthRootProductAlternateTermRaisedPPlusQoverPDividedQ(p, q);

}

Today we briefly revisit the bridge problem and see how to apply the longest increasing subsequence.
Let us say the cities on both sides of the river are 2, 3, 1 and 1, 2, 3.
from the previous discussions on the longest increasing subsequence, we can find it recursively by including the last element or not.
Let us keep track of the indices in an array
we take the first sequence and iterate from left to right. say i = 0
for an increasing subsequence of size j=1 and i = 0 upto and inclusive of 2, the minumum value of the length of the increasing subsequence is one greater than the length of the longest prefix at this element and now equals 1
we initialize IndexArray at 1 to be 1 and update the longest subsequence encountered so far to be 1

for an increasing subsequence of size j =1  and i = 1 upto and inclusive of 3, the minimum value by binary search is that for first element plus 1 which now equals 2

for the last element, the binary search points to the second element and has not changed  the length L computed so far and updated last with 2.

If it increases the current sum, the element is included Thus we use a greedy strategy here

Formally,

Let X[i] represent the sequence 2, 3, 1
Let M[j] store the index k of the smallest value X[k] so that there is an increasing subsequence of length j ending at X[k] on the range k <=i and j <=k <= i.  j represents the length of the increasing subsequence and k represents the index of termination.
and Let P[k] store the index predecessor of X[k]
The longest Increasing subsequence  at any given point is given by X [M [1]], X [M [2]], ... X [M [L]] and if there is an increasing subsequence at i then there is one at i-1 which is X [P [M[i]]] and between these two bounds we can do a logarithmic search for j <=k <= i
Therefore the steps are:
P = array of length N  - all initialized to zero
M = array of length N + 1 // pad on the left so that we can use zero based index.
L = 0
for i in range 0 to N-1:
      Binary search for the largest positive j <= L
      such that X[M[j]] < X[i]
      lo = 1
      hi = L
      Binary Search between lo and hi adjusts lo and hi
      After searching lo is 1 greater than the length of the longest prefix
      newL = lo
      The predecessor of X[i] is the last index of the subsequence of length newL-1
      P[i] = M[newL -1]
      M[newL] = i
      if newL > L:
          if we found a subsequence longer than L, update L
          L = newL

   // Reconstruct the longest increasing subsequence
S = array of length L
k = M[L]
for i in range L-1 to 0:
    S[i] = X[k]
     k = P[k]

return S

For the bridge problem, we find the longest increasing subsequence first for the north side and then for the south side of the river and take the smaller of the two.

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

Today we look at a few more interesting problems. We discuss Anti-Binary Sets. The problem is stated this way:
Let  Z = { 1,2 . .17}. Let us consider such subsets A (is a subset of Z) that for every x belongs to A, we have 2x belongs to A. Such subsets of A are called anti-binary. What is the largest anti-binary subset of Z? How many anti-binary subsets are there ?
The hint provided here is that we can create graphs with the vertices labeled from 1 to 17, and edges connecting m and 2m (for m = 1 to 8)
if we choose m = 1, we have a graph with five vertices and edges (1,2,4,8,16)
If we choose m = 3, we have a graph with three vertices and edges ( 3,6,12)
If we choose m  = 5, we have a graph with two vertices and edges ( 5, 10)
If we choose m = 7, we have a graph with two vertices and edges (7, 14)
The vertices that don't have connecting edges are 9, 11, 13, 15, 17.
The definition of Anti-Binary sets is that it cannot contain elements connected by an edge. We can consider each path separately, since they are not connected with each other. First, we can select all five single vertices. These are 9,11,13, 15, and 17. From the graphs with two vertices, we can select only one vertex, from the graphs with three vertices , we can select the ends and from the graph with five vertices, we can select the ends and the mid point. The maximum number of vertices that can form a binary set is a collection of these vertices.
Let us denote An as the number of anti binary sets of a path of size n. Then A1 = 2 and A2 = 3. For larger n, we split all the anti-binary sets possible into two groups - one that contains the last vertex and another that doesn't.  The number of latter ones is simply An-1 and the one containing the last vertex doesn't contain its predecessors which is An-2.
Therefore An  = An-1 + An-2
and this is the Fibonacci series.
Therefore An = Fibonacci(n+2).
The total number of anti-binary subsets of Z equals 2^5.3^2.5.13 = 18720
Courtesy:Kubica and Radoszewski

Returning back to our discussion on webhooks and callbacks, let us consider callbacks as something that each API can accept and process. The APIs should all have a predetermined method and parameters to perform for that callback. Different such sets can be specified for each API Callback

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

Webhooks and callbacks
REST based APIs can implement a publisher subscriber notification mechanism with web hooks. This can be implemented with the following:
* Storing subscriptions in a database with subscription details such as

• event names, 
• user relationship, 
• target URL to send payloads, and 
• active versus inactive state for the subscription 

* API to modify subscriptions that includes:

• GET /api/v1/subscription/ to list 
• POST /api/v1/subscription/ to create 
• GET /api/v1/subscription/:id/ to lookup 
• PUT /api/v1/subscription/:id/ to edit 
• DELETE /api/v1/subscription/:id to delete a subscription 

* List and implement event types

• a name in the name.verb syntax. 
• a payload to simply mirror the representation from the standard API. 

* send hooks with POST to each of the target URLs for each matching subscription

• compiling and POSTing the combined payload for the triggering resource and hook resource 
• sending to known subscribers where X-Hook-Secret header has a unique string and one that matches what was issued. 
• confirming the hook legitimacy with a X-Hook-Signature header 
• Handling responses like the 410 Gone and optionally retrying connection or other 4xx/5xx errors.

#coding exercise

Building bridges dp problem

Consider a 2D map with a river flowing from left to right through the center. There are n cities to the south of the river and same number on the northern bank. We have to bridge city i on the northern bank to city i on the southern bank however the order of cities can be random on both the northern and southern bank. We have to draw as many bridges without having them cross each other.

Solution:

When we put down the co-ordinates, we see that the bridges won't cross only if we pick increasing numbers on both and north and south banks. This means we are trying to find the longest common subsequence.
The length of the longest common subsequence c[i,j] is :
1. 0 if i = 0 or j = 0
2. c[i-1, j-1] + 1if i,j > 0 and xi = yj
3. max(c[i,j-1], c[i-1, j]) if i, j  > 0 and xi != yj

for i = 1 to n
     c[i, 0] = 0
for j = 0 to n
     c[0,j] = 0
for i = 1 to n
      for j = 1 to n
            if xi == yi
               c[i,j] = c[i -1, j-1] + 1
               b[i,j] = up-left
            elseif c[i-1,j]  >= c[i, j-1]
               c[i,j] = c[i-1, j]
               b[i,j] = up
            else c[i,j] = c[i,j-1]
               b[i,j] = left
return c and b

The problem above assumes the bottom row of the cities is sorted.
Otherwise we could use the longest increasing subsequence.

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