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


}