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

}

Huffman codes enable compression. It is a technique that can result in savings of 20 to 90% depending on the data being compressed. It scans the text to populate a table of frequencies of the occurrence of characters and then builds an optimal way of representing them. Let us say that the entire text was formed of three characters and that the first character appears the majority of the time, then there can be significant savings if there were fewer bits to represent the first character. Thus this technique uses a greedy strategy.
The characters can be represented by fixed-length codes or variable length codes. The variable-length codes will have more savings. That we know so far but how do we decode such compressed data. We make the assumption that the codes are such that no codeword is also a prefix of some other codeword. Such codes are called prefix codes. When reading a prefix code, we can now decipher the first character unambiguously.  Then we can repeat the decoding.
The representation of the prefix code is possible with a binary tree where the characters are the leaves of the trees and the path from the root to leaf is the prefix code. The prefix is appended 0 for going to the left child and 1 to go to the right child.  These are not Binary Search Trees because they need not be sorted and the internal ones don’t have character keys. Trees correspond to the coding schemes. The optimal code is always represented by a full binary tree.
Now that we know the prefix codes can be obtained by constructing the tree, we build it up in a bottom-up manner. We take a set of C leaves and perform a sequence of C-1 merging operations to create the final tree. A min priority queue Q, keyed on f, is used to identify the two least-frequent objects to merge together. The result of the merger of two objects is a new object whose frequency is the sum of those merged.
HUFFMAN(c)
N <- C
Q <-C
For I in range (n-1):
      Do allocate a new node z
       Left[z] = x = EXTRACT-MIN(Q) // removes from Q
       Right[z] = y = EXTRACT-MIN(Q)
       f[z] = f[x] + f[y]
      INSERT(Q, Z)
Return EXTRACT-MIN(Q) // root of the tree