Django middleware vs Openresty: 

Django is a python framework suitable for building and deploying production quality web application software. It enables model, view controller framework out of the box for fast web application development. In addition, it integrates seamlessly with rest_framework and documentation support to provide documented REST based APIs.  Django also provides what is called a middleware to enable http modules or plugins to be written that can modify the request or response or mutate the View parameters. This is defined as a sequence of classes in the settings file. The hooks that middleware classes uses for their processing include request , response, view, template_response and exception. Django middleware are typically used for sessions, authentication, CSRF protection and GZipping content . 

OpenResty is a full-fledged web application server that bundles the core and modules of Nginx that opens it up for developers to configure via Lua programming/scripting language.  These modules and the core are written in C and are therefore highly performant and cross platform compatible. This web server is able to handle 10K plus connections. Openresty enables a developers server side web application to be run entirely within Nginx server. Nginx is known to support asynchronous IO not only with http clients but also with database backends. 

To compare the two, we review a common use case – the ability to route REST API calls to different API providers. This functionality is often referred to as an API gateway. 

Only some of the tradeoffs are presented as follows:
Features                         Django Middleware                          OpenResty bundle 
Support request and 
response modification                          Yes                                                Yes 

Support authentication and 
authorization including OAuth             Yes                                               Yes 

Support large number 
of connections                                       Yes                                               Yes, but this is faster 

Support on a wide                          More popular by
variety of hardware                        virtue of LAMP stack                          Not as popular 

Production quality and 
quality control                          More tested in commercial                        Less tested 

Memory and Disk I/O                          Can be large                                   Aims to be more 
                                                                                                                    performant with little
                                                                                                                    memory footprint 

Software support                          Generally not needed. Some                 Requires workarounds 
                                                  legacy platforms are still in use                and fixes
                                                  without issues, more reliable 


Today we continue to do some more coding exercises.
Let us look at a Skyline problem. This appeared in Leetcode challenge.  A city's skyline is the outer contour formed by the buildings. The buildings are given by (Li, Ri, Hi) where Li is the x-coordiante of the building's left edge and Ri is the x-coordinate of the building's ending edge. Hi is the height of the building.  The buildings are arranged left to right in increasing order of their left edges.
The output is a list of key points where the contour changes direction. The number of building is guaranteed to be less than 10000. There must be no consecutive horizontal line of equal height and should appear merged instead.

public class Solution {
    public IList<int[]> GetSkyline(int[,] buildings) {
     var ret = new List<int[]>();
     int x = 0;
     int y = 0;
     var stk = new Stack<int>();
     for (int i = 0; i < buildings.Length; i++){
         if (buildings[i][2] > y) {
                if (stk.isEmpty() == false) {
                         int j = stk.Pop();
                          if (building[i][1] < building[j][1])
                                   x = building[j][1];
                                   AddToList(ref ret, x, y);
                                   y = 0;
                                   AddToList(ref ret, x, y);
                        }
               stk.Push(i);
               x = buildings[i][0];
               AddToList(ref ret, x, y);
               y = buildings[i][2];
               AddToList(ref ret, x,y);
        }
        else
        {
               if (buildings[i][1] < buildings[stk.Peek()][1))
                     continue;
               int j = stk.Pop();
               x = buildings[j][1];
               AddToList(ref ret, x, y);
               y = buildings[i][2];
               AddToList(ref ref, x, y);
               stk.push(i);
         }
     }
     
    }
    private static void AddToList(ref List<int[]> ret, int x, int y)
    {
         var current = new int[2];
         current[0] = x;
         current[1] = y;
         ret.Add(current);
    }
}

Trie data structure:
A trie is also referred to as a prefix tree or radix tree and unlike B-Trees which store the keys in the node, a trie uses the position of the node to construct the prefix. All the descendants of a node have a common prefix associated with that node. The prefix starts out empty at the root and gets appended as we descend down the children. The term 'trie' comes from retrieval. A trie comes in very useful for auto-complete and spell-checker.
A trie stores words with the letters on the edges and as we walk down, we read one letter at a time. Words can end or be a prefix of others. To do a lookup,  we just walk down the tree letter by letter and then see if the node has an ending $ to the node. If we get to a null pointer, we know that the word is not there. To efficiently save the prefixes, paths that don't branch into a single edge are compressed and only split when needed.
To lookup the words, we use radix sort.
 void RadixSort(Array A, int digits)
{
for (int i = 1; i <= digits; i++)
      InsertionSort(A, i);
}

void InsertionSort(A, d) {
for (int i = 1; i <= n; i++)
{
var x = A[i];
int j = i -1;
while (j >= 0 && A[j] > x)
{
// like arranging a hand of playing cards.
A[j + 1] = A[j];
j = j - 1;
}
 A[j + 1] = x;
}
}

We now look at inserting words into a trie. When we add a word to a vertex, we will add word to the corresponding branch of vertex cutting the leftmost character of the word. If the needed branch does not exist, we will have to create it.

class TrieNode:
         def addword(self, word):
                if len(word) == 0:
                    self.isWord = True
                    return
                 key = word[0]
                 word = word [1:]
                 if self.next.has_key[key]:
                     self.next[key].add_item(input)
                 else:
                      node = TrieNode()
                      self.next[key] = node
                      node.add_item(string)

         def dfs (self, sofar = None):
                # we print in two cases
                if self.next.keys() == []:
                    print 'Match:'+sofar
                       # this could be modified to look for similar words by backtracking to the parent and looking for siblings
                if self.isWord:
                    print 'Match:' + sofar
                for key in self.next.keys():
                    self.next[key].dfs(sofar)

        def autocomplete(self, word, sofar=""):
                if len(word)  == 0:
                    if self.isWord:
                        print 'Match:', sofar
                    for key in self.next.keys():
                        self.next[key].dfs(sofar)     
               else:
                    key = word[0]
                    word = word[1:]
                    if self.next.has_key(key):
                        sofar = sofar + key
                        self.next[key].autocomplete(word, sofar)
                 
    

courtesy:sarathlakshman.com

WebAPIs often use various authentication methods such as basic authentication, token authentication, or even session authentication. However, applications using the webAPIs may also require sessions to associate the resources for the same user using the same user-agent* (defined in RFC 2616).  For example, consider the Cart API. To get the items in the shopping cart of a user the application may have to use the GET method on the Cart API as follows:
GET  Cart/ API 
“X-Merchant-ID:  client_key”
“X-Session: <user session identifier>”
The application can also add or edit items in the shopping cart or delete it. This example illustrates the need for the application to associate an identifier for the scope of a set of webAPI calls. 
This session identifier is usually obtained as a hash of the session cookie. And is provided by the authentication and authorization server.  The session identifier can be requested as part of the login process or by a separate API Call to a session endpoint. An active session removes the need to re-authenticate. It provides a familiar end-user experience and functionality. The session can also be used with user-agent features or extensions to assist with authentication such as password-manager or 2-factor device reader.
The session identifier is usually a hash of the session. It is dynamic in nature, for external use and useful only for identifying something that is temporary. It can be requested based on predetermined client_secrets.
Sessions can time out or be explicitly torn down – either by the user or by the system forcing re-authentication. Therefore session management must expire/clear the associated cookie and identifiers. 
Sessions will need to be protected against csrf attack and clickjacking just as they are for other resources.
Sessions are treated the same as credentials in terms of their lifetime.The user for the session can be looked up as follows:
{HttpCookie cookie = HttpContext.Current.Request.Cookies[FormsAuthentication.FormsCookieName];
FormsAuthenticationTicket ticket = FormsAuthentication.Decrypt(cookie.Value);
SampleIdentity id = new SampleIdentity(ticket);
GenericPrincipal prin = new GenericPrinicipal(id, null);
HttpContext.Current.User = prin;} 

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);
}

Today we review the increasing subsequence problem similar to the previous two subsequences problems yesterday. Consider a bookshelf with 12 volumes of encyclopedia. Their order has become quite random:
                11, 1, 10,  4, 3, 2, 8, 7, 12, 6, 9, 5
In one move we can take out one volume and insert it anywhere in the row of volumes (shifting some volumes if needed) What is the minimal number of moves necessary to order the volumes from left to right.
The hint provided here is : what is the largest set of volumes that may be left and not moved at all.

To answer the hint, we say that those that form an increasing subsequence in the given sequence are already sorted. Then we can insert all the remaining volumes in their correct positions.
Therefore, the requested number of moves = the length of the sequence - the length of its longest subsequence.
Now to find the longest subsequence, we do the following:
for each element, we find the increasing subsequence upto that element and note its length. Then we take the maximum of such lengths.
For 11 and 1, this length is 1. For 10 this length is 2.  The same holds fror the next three elements. For 8 this is 3 and for 12 this is 4 the maximum. For 6 this is 3. For 9 this is 4 as well. (1,2,6,9)
Generally, for each element x, either:
x can be a single-element increasing sequence or
x can be appended at the end of the longest increasing subsequence ending at some y provided that y precedes x and y < x
Therefore the table looks like this:
Volume       11, 1, 10,  4, 3, 2, 8, 7, 12, 6, 9, 5
Length of     1   1    2   2  2  2  3  3   4   3  4, 3
subsequence
Hence, the smallest number of moves = 12 - 4 = 8.
Note that this is not a single problem of a longest increasing subsequence but a whole table of such problems. The dependencies between increasing subsequence ending at that element makes it easier to calculate their lengths With dynamic programming, the time complexity is O(n^2) where n is the number of volumes. This is better than n times O(nlogn) times complexity using the classical
solution for the longest increasing subsequence.

Heavy Encyclopedia
Let us now modify the problem to say that the encyclopedia volumes are so heavy that they cannot be shifted or taken one position to the other. Instead we want to order the volumes only by swapping the adjacent volumes on the shelf. What is the minimal number of such moves ?
The hint here is that we move the first volume to the first position by swapping with all of the volumes in between the current position and the first. Then we eliminate first and repeat with the second. This will correctly give the minimal number of moves because we are only going to move this volume in one direction and given that there is only one step the total number of moves doesn't change from i-1. Moreover if the volume 1 is not at its intended destination, it will be swapped for subsequent volumes and that will not result in an optimal solution. We therefore use the hint and do successive elimination after each volume makes it to its destination position.
Given this we can print a table of sequences after each volume makes it to its intended positon incrementally.  The total number of moves will come out to be Sum (CurrentPosition(i)-1) for i = 1 to 12 = 31
Without going through the table of sequences, we can total from the given sequence by saying that we add the number of moves needed to position volume x equal the number of such volumes y that y > x and y is to the left of the x in the original problem. Therefore volume 11 will have zero moves.
Here we are using greedy programming when swapping and divide and conquer rule when eliminating.

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

Yesterday's post we discussed continuous subsequence.
Let us now generalize the above to finding subsequence ( that are not necessarily continuous and those that can repeat and should be counted as many times when there are duplicate subsequences at different positions) and again we want the subsequences whose sum is divisible by a number N.
In this case too we find prefixes. Note that the prefixes for subsequences are formed by taking the prefixes upto but not including the last element of the current prefix and then adding the set of prefixes formed by including this last element in each of the previous set of prefixes. for example, a set 3, 2 has empty set, 3, 2 and 3,2 as the prefixes when prefix length is two. We find and count this number of prefixes for all the prefix length 0 to N-1.
We use the principle that the number of sequences of the prefix , for which the sum of elements modulo 5 equals K, = sum of the same target for prefix shorter by one position
and the number of subsequences of a prefix shorter by one position for which the sum of elements modulo 5 equals K-x where is the last element of the given prefix.
We now calculate the number of subsequences for all the prefixes as a table where we take different prefix lengths as columns ranging for 0 to N-1 and remainders 0 to N-1 as rows
for example the first cell would correspond to 1 because an empty set satisfies the condition
the second cell with prefix length 1 would include this empty set plus the number of subsequences whose sum modulo 5 equals 5 - 3= 2 which in this case is 0 and consequently, the second cell is also 1. the last cell will have the answer to the question.

Now let us apply that to coin counting.  If we are given a set of coins with the following denomination:
                  1,1,2,5,7,17,17,35,83
we have to find the smallest positive integer for the amount of money that cannot be paid by the given coins.
Intuitively, the sum of the coins plus one would be that amount but how do we prove that this is so with the principle we just discussed.
Using just two coins we can pay any amounts upto 2. Using the next coin together with these two  extends the amount to 4. Using the next coin, we can pay any amount 0 to 4 with the first set of coins and not use the coin 5 and if we use the coin 5 we can pay from 0 to 9. if x is the amount  between 5 to 9, we use coin 5 and the coins from 5 -x to pay. This we can generalize as follows:
If the range of amounts that can be paid using the first k coins is from 0 to r, and the next coin has  value x, then either :
x <= r + 1 and it is possible to pay any amount from 0 to r+x using the first k+1 coins
x > r + 1 and it is not possible to pay r + 1 since x and all the next coins are greater values.
Using this principle we can now generate the table of values with each incremental denomination as follows:
           denomination    1   1   2   5   7    17   17    35    83
           max amount      1   2   4   9   16  33   50    85    168
And therefore the maximum amount that we cannot pay with the coins is 168 + 1 = 169.

Courtesy: Kubica and Radoszewski

Next we will review increasing subsequence.
But first a coding question:
 

Print Fibonacci int Fibonacci(int n)  { if (n == 0 ) return 0; int value = F(abs(n)-1) + F(abs(n)-2); if (n < 0) return power(-1, n+1) * (value);  return value; }

Today we cover a few more exercises:
 Detect the Y-intersection of two lists that may be of different lengths:
  Solution :  find the length of the first list
                    find the length of the second list
                    traverse the longer list by the number of nodes equal to the different in the two lengths above.
                    Then traverse both the lists one node at a time to detect when the next node is the same for both lists.

 Shuffle a deck of cards:
           Knuth Shuffling :
                  split the cards into 1 to I and I+1 to n-1.
                   pick a card from 1 to I randomly and uniformly (I times)
                   replace with random number card between I+1 to n-1

Continuous subsequence divisible by a number:
The number of prefixes divisible by the given divisor say 5 for a sequence say 1,1,3,2,4,1,4,5
We apply the principle that if there is a continuous subsequence divisible by the divisor, then it is composed of pre-fixes (leading fragments) that give the same remainder and vice versa. Let us group the pre-fixes of a given sequence by the remainders from modulo 5  of the sum of their elements  If there are k sub-sequences for some remainder, then the number of continuous subsequences with the sum of elements divisible by divisor is K choose 2 =  k(k-1)/2

Check if two strings s1 and s2 are rotated
   Return  (s1+s1).indexOf(s2)

#codingexercise


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


{



If ( A== null) return 0;



Return A.NthRootProductEachTermRaisedPTimesQoverPDividedQ(p, q);



}

Today we cover a few more exercises.
Depth-first-search of a binary tree:

DFS-VISIT (G,u)
{
time = time  + 1
u.d  = time
U.color = gray
For each vertex v in adj (u):
    If v.color == white
        DFS-VISIT  (G,v)
        V.pi = u
time  = time +1
u.f = time
u.color  = black
}

• Knight’s tour on a chess board (tour all positions on the chessboard)
• We use backtracking 
•  Void KnightsTour(board B, int row, int col, int countOfPositions) 
•  { 
•      B[row,col] = countOfPositions 
•      If (countOfpositions == row_max*col_max -1) return; 
•      For all possible moves to a new position p 
             if B[row,col] != NIL
•                 KnightsTour(B, p, countOfPositions + 1)
•    } 
• 
  

Four glasses are on square table corners. They have to be all up or down. The table can rotate by a random angle and a bell will ring if the glasses are all up or down.we can only feel two of the glasses.

Use diagonals and adjacent glasses alternatively in the moves
for example, if two diagonals are turned up , the table is rotated, you get back one of the diagonals for comparison with the adjacents. If the adjacent and diagonal corner in the next round are opposite, flip the down glass up. If they are same you have three glasses up.
if after two turns the bell doesn't ring flip two adjacents the other way and try again. This will put the two flipped glasses as adjacent for comparison with the others.
when we reverse the next two adjacent glasses the diagonals become opposite. The bell rings in the search finite moves.

#codingexercise 

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

{

If ( A== null) return 0;

Return A.NthRootProductEachTermRaisedPMinusQoverPPlusQ(p, q);

}

• Tree: Prune paths from root that don’t add up to a given sum = 12 Eg: 

62.                 2

63. 3

64. 7           9   7    13

65.          2   3 2    3  

66. Prune (2, 12,0)

67. bool Prune(Node root, int sum, int cur)

68. {

69.  If (root == NULL) return false;

70. If (root.data + cur > sum) { return false;}

71. If  (root.data + cur == sum) {

---

3 / 3

72.        Root.left = NULL;

73.        Root.right = NULL;

74.        Return true;

75. }

76. Cur += root.data;

77.  Bool leftHasPath = Prune(root.left, sum, cur);

78.  Bool rightHasPath = Prune(root.right, sum, cur);

79. If (leftHasPath == false &&

80.      rightHasPath == false)

81. {

82.     Root.left == NULL;

83.     Root.right = NULL;

84.   Return false;

85. }

86. If (leftHasPath == false) { root.left = NULL;}

87. If (RightHasPath == false) {root.right = NULL;}

88. Return true;

89. }

90.

Edit Distance:

Given a jumbled word, find the nearest dictionary word using edit distances. Usually you are given both the starting word and the ending word.

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) 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

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.

#codingexercise 

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

{


If ( A== null) return 0;


Return A.NthRootProductEachTermRaisedPPlusQoverPMinusQ(p, q);


}