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


}

Today's blogpost is about answers to coding problems:

Print concentric squares of a given square matrix.

void PrintConcentricSquare(int [,] m, int n) //params: matrix and dimension
{
  if (n%2 == 1)
  {
   int center =n/2;
   int numSquares = center + 1;
   for (int i =0; i < numSquares; i++)
   {
         for (int x=center-i;x<=center+i;x++)
           for(int y=center-i;y<=center+i;y++)
              Console.Write('{0} ',m[x,y]);
         Console.Writeline();
   }
   }
   else
   {
       int center = n/2;
       int numSquares = center;
       for (int i =0; i < numSquares; i++)
       {
         for (int x=center-i-1;x<center+i+1;x++)
           for(int y=center-i-1;y<center+i+1;y++)
              Console.Write('{0} ', m[x,y]);
         Console.WriteLine();
       }
   }
}
The above algorithm can be modified to print just the boundary of the concentric squares. When x is not at the lower or upper limit and y is not at the lower or upper limit, escape printing the cell value.


#codingexercise 
Double  GetNthRootProductEachTermRaisedPMinusQ (Double [] A,Double  p, Double q)
{

If ( A== null) return 0;

Return A.NthRootProductEachTermRaisedPMinusQ(p, q);

}

Some coding question and answers: 

Permutations of  a string: 
Void Permute (String a, StringBuilder b, bool[] used) 
{ 
  If ( b.Length == a.Length)  { print b.ToString(); return;} 
  For (int I = 0; I < a.Length ; i++) 
  { 
    If (used[i]) continue; 
     used[i] = true; 
     B += A[i]; 
     Permute(a, b, used); 
     B [B.Length – 1] = ‘/0’; 
     used[i] = false; 
  } 
} 

Combinations of  a string 
Void Combine (String a, StringBuilder 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.ToString(); 
       If (I < a.Length) 
            Combine(a,b, start+1,level+1) 
       B[level] = ‘/0’; 
   } 
} 

Void ReverseAlternateChunks InSinglyLinkedList(Node root, int chunksize) 
{ 
  Node ret = root; 
  Node prev = NULL; 
  Node cur = root; 
  Bool reverse = false; 
  Int chunkCount = 0; 
  While (cur != null) 
  { 

If (reverse) 
{ 
       cur = Reverse(cur, chunkSize); 
       If (prev)    
          Prev.next = cur; 
       Else 
          Ret = cur; 
        Reverse = false; 
} 
For (int i = 0; I < chunkSize; i++) 
{ 
      Prev = cur; 
      Cur = cur.next; 
      If ( cur == NULL) break; 
} 
chunkCount++; 
If (chunkCount %2 ==0) { reverse = true}         
} 
Return ret; 
} 

GetZigZagBinaryTree(Node root) // ZigZag is the same level wise printing of nodes except alternate levels of Node(s) are reversed
{
if (root == NULL) return;
var Q = new Queue();
Q.Enqueue(root);
Q.Dequeue(NULL);
int level = 0;
var S = new Stack();
while(Q.Empty() == false)
{
    var cur = Q.Dequeue();
    if (cur)
    {
         if (level %2 == 0) {S.Push(cur);}
         else
         {
               while (S.empty() == false) print S.pop().data;
               print cur.data;
          }
         if (cur.left) Q.Enqueue(cur.left);
         if (cur.right)Q.Enqueue(cur.right);
    }
    else
    {
          Q.Enqueue(NULL);
          level ++
    }
}
while (S.empty() == false) print S.pop().data;
}

#codingexercise 
Double  GetNthRootProductEachTermRaisedPTimesQ (Double [] A,Double  p, Double q)
{

If ( A== null) return 0;

Return A.NthRootProductEachTermRaisedPTimesQ(p, q);

}

Hash tables are very popular data structures. They store values that can be looked up by keys in constant time. When the number of keys is smaller than the total number of possible keys, this becomes very effective for lookup, insertion and deletion. If we are able to allocate an arraywhere is there one position for every possible key, we have what we call direct addressing. When the array index is computed from the key, we may have collisions which we solve by chaining values against the same key. Open addressing is another way to deal with collisions. When the search for a value takes constant time even in worst case, we have perfect hashing. The set of keys don't change once stored. Fixed hash functions are vulnerable  to malicious attacks where no keys hash to the same slot and degrading the performance to O (n) for lookups. This is resolved with universal hashing which picks out a hashing function at random from a set of hash functions at the beginning of the execution.  One such family is given by (((ak+b) mod p) mod m) where p is a prime number to denote the number of keys and is much larger than m the number of slots. Next, with open addressing the elements are not chained and they are stored in empty slots of the hash table itself. The sequence of positions probeddepend on the keys because they are associated with a permutation of the slots. We  make the assumption that each key is just as likely as the other based on the permutation. This is called uniform hashing. In practice the distribution of keys is not uniform and keys may not even be independent of each other.Three techniques are commonly used to compute the probe sequence required open addressing. These are linear, quadratic and double hashing. Double hashing gives the maximum number of probe sequences and hence better results. It takes theform h (k,i) = (h1 (k) +ih2 (k)) mod m. On order to improve the hashing to the constant time even for worst case such as for perfect hashing, we could use two levels of hash tables.

#codingexercise 
Double  GetNthRootProductEachTermRaisedPDividedQ (Double [] A,Double  p, Double q)
{

If ( A== null) return 0;

Return A.NthRootProductEachTermRaisedPDividedQ(p, q);

}