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


}