# Code Puzzle : Making Anagram problem

Problem statement: Calculate the minimum number of characters to be removed from any of the given two strings so that they become anagram.

Strategy: Store the frequency of occurrence of every characters (from a-z) of each of the strings in separate arrays, then the summation of difference in frequency of each character gives you the solution, abs(count1[str1[i]-‘a’] – count2[str2[i]-‘a’])

Here is the code,

```
#include <iostream>

using namespace std;

int min_remove_anagram(string a, string b) {
int char_count_a[26]={0}, char_count_b[26]={0}, num_needed=0;
// Count the frequencies of all characters in string a and b
for(int i=0; i < a.size(); i++) {
char_count_a[a[i] - 'a']++;
}
for(int i=0; i < b.size(); i++) {
char_count_b[b[i] - 'a']++;
}

// The difference in the frequency count of all the characters is the solution.
for(int i = 0; i < 26; i++) {
num_needed += abs(char_count_a[i] - char_count_b[i]);
}
return num_needed;
}

int main()
{
string str1 = "bcadeh", str2 = "hea";
cout << min_remove_anagram(str1, str2);
return 0;
}
```

# Dynamic Programming : Making change for an given amount with least number of coins

Helloooooooooo !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Its been sometime since the last blog … loads of em are struggling to come out of the drafts 😛 I’ve been working on Dynamic programming concepts for a while now , So i thought of sharing my insights on the same by taking up the problem of finding  change for the given amount using  least possible no of currencies , and in the process i would love to explain what Dynamic programming is all about . Without wasting lot of time lets get into solving the problem .

Let me take an example scenario . Lets say you gotto make change for  11 cents and you have coins of 1,2,5  cents.  Now the question is what are various ways(the last step)  to reach to 11 cents considering you have coins of 1,2 and 5 cents ??? hmmm, thats not tough!

Add a 2 cents coin after having change for   9 cents  (9 + 2 )= 11 cents |  add 1 cents after having change for  10 cents ( 10 +1)=11cents |  add 5 cents after having change for  6 cents (6 + 5)= 11 cents  . Now we have 3 ways ( 9 + 2 , 10 + 1 , 6 + 5 ) But amongst these 3 approach which one would consist of minimal number of currencies or coins to make it to 11 ?? Hmm ….

Thats tricky !!!!! Well , that inturn depends on number of coins in the change for 9 , 10 and 6 cents. we have to consider the minimum amongst the 3 cases below

case 1: No.of.coins to make it to 9 cents (x) +  one  coin of 2 ceeents

case 2: No.of.coins to make it to 10 cents(y) + one coin of 1 cents (1)

case 3: No.of.coins to make it to 6 cents (z) + one coin of 5 cents (1)

In short we have to consider min(x+1 , y+1, z+1)

Now lets set  arbitrary values for x,y,z to be {3,2,2} respectively and Lets translate this logic into code for this particular value of amount for which we are supposed to find change using coins of 1,2,5 cents

Here is the code and explanation follows it , The names of variable used reflects their purpose . If you quickly want to execute and mess around with the code here is link https://ideone.com/M9qq4f . Here is the Github link of the code

```amntForWhichChangeIsToBeFound = 11

coinsWeHaveUsingwhichChangeHastoBeFound = [1,2,5]

LastcoinUsedToGetChangeArray = [0]*(amntForWhichChangeIsToBeFound+1)

numberOfCoinsUsedForChange = [0]*(amntForWhichChangeIsToBeFound+1)

coinCount = 11
#In the worst the change will contain 11 coins with all of them ,obviously  lastCoinUsedForChange also  one being 1 cent
LastCoinUsedforChange = 1

numberOfCoinsUsedForChange[9] = 3

numberOfCoinsUsedForChange[10] = 2

numberOfCoinsUsedForChange[6] = 2

for j in [c for c in coinsWeHaveUsingwhichChangeHastoBeFound if c<=amntForWhichChangeIsToBeFound]:
#List comprehension in python , iterates only through values of array which satisfies if condition
if numberOfCoinsUsedForChange[amntForWhichChangeIsToBeFound - j] + 1 < coinCount:
coinCount = numberOfCoinsUsedForChange[amntForWhichChangeIsToBeFound - j] + 1
LastCoinUsedforChange = j
numberOfCoinsUsedForChange[amntForWhichChangeIsToBeFound] = coinCount
LastcoinUsedToGetChangeArray[amntForWhichChangeIsToBeFound] = LastCoinUsedforChange
print (numberOfCoinsUsedForChange)
print (LastcoinUsedToGetChangeArray)
```

In 5 and line 7 of the above code there is declaration and initialization to 0

```LastcoinUsedToGetChangeArray = [0]*(amntForWhichChangeIsToBeFound+1)

numberOfCoinsUsedForChange = [0]*(amntForWhichChangeIsToBeFound+1)
```

The array element numberOfCoinsUsedForChange[i] contains the minimum number of coins used to obtain change for i cents . Thats is , numberOfCoinsUsedForChange[1] contains the minimum number of coins used to obtain change for 1 cent , numberOfCoinsUsedForChange[6] contains the minimum number of coins used to obtain change for 6 cent and it follows . But for now i have assigned arbitrary values to numberOfCoinsUsedForChange[6] , numberOfCoinsUsedForChange[9] , numberOfCoinsUsedForChange[10] , but in practical these values are to be computed .

Also the LastcoinUsedToGetChangeArray[i] contains the last coin used to get the change for i cents . LastcoinUsedToGetChangeArray[11] contains the last coin used in the change for 11 cents .

This sounds Ok , but You have now hard coded and assigned arbitrary values for inumberOfCoinsUsedForChange[6] , numberOfCoinsUsedForChange[9] , numberOfCoinsUsedForChange[10]  , but in real how do i have to compute in runtime ,how do i compute them ??

Yes , There are two ways to compute them . It can be recursively computed using top-down approach or iteratively computed using bottom-up approach . In the complete code sample later in the article ill be using the iterative approach .So using one of these approach the values are computed and the arrays are filled .
So now in this case to compute minimum number of coins required for change of 11 cents we need minimum number of coins required for change of 10,9 and 6 cents and those values are  in turn are dependent on others(10 is dependent on 10 – [1,2,5],9 is dependent on 9 – [1,2,5] and so on …..) , so to solve this inter dependency ,one amongst either recursive or  iterative approach can be used .

That sounds cool , but Size of both the arrays used is equal to the amount for which im finding change for , LastcoinUsedToGetChangeArray = [0]*(amntForWhichChangeIsToBeFound+1) allocates and initializes array of size = (amntForWhichChangeIsToBeFound+1) , why are we wasting so much of memory ??

Yes , in the previous question above I spoke about the interdependencies , these arrays are used to store these interdependencies to avoid re-computation . These re-computations are avoided by storing these values and using them instead of recomputing them every-time . Yes , This needs more memory to be able to store these values , but this is traded off with the speed , This potentially can bring an exponentially time complexed algorithm down to polynomial and this is the core idea of Dynamic Programming . Yes the full program later First we’ll build the numberOfCoinsUsedForChange[] array from bottom-up approach . That is first we’ll compute  numberOfCoinsUsedForChange[1] , numberOfCoinsUsedForChange[2], numberOfCoinsUsedForChange[3] and so on and these stored values are used to compute the later values because these serve as dependencies and recomputation is avoided .

Now analyze the output of the above program ,

In the output LastcoinUsedToGetChangeArray[11] contains value 1 , so 1 cent is the last coin used in the change . Now we know that the last coin is 1 cent , If we could find the last coin used in change for 10 cents (11 -1 )  this gives us one more coin in the minimum change for 11 cents , and this is stored in LastcoinUsedToGetChangeArray[10] , if this process is recursively followed all the coins used in getting the change can be obtained . Using this process PrintCoin function is written which prints out the coins used .

Phewwwwwwww!! Now i believe i spoke about enough of background work required to understand the logic easily , now lets scale it up to be able work with any value .

Here is the code which finds out the number of coins used and the coins used to find change for given amount with given set of coins . Again if you quickly want to execute and hack around here is the link of the code on cloud IDE https://ideone.com/eHhAcB. If you want to fork and mess around with the code here is the link of the code on Github Github link of the code

```def printCoins(amntForWhichChangeIsToBeFound,LastcoinUsedToGetChangeArray):
coin = amntForWhichChangeIsToBeFound
while coin > 0:
LastCoinForCoinCent = LastcoinUsedToGetChangeArray[coin]
print(LastCoinForCoinCent)
coin = coin - LastCoinForCoinCent

def main():
amntForWhichChangeIsToBeFound = 68
#edit it for the value you want it for
coinsWeHaveUsingwhichChangeHastoBeFound = [1,5,10,21,25]
LastcoinUsedToGetChangeArray = [0]*(amntForWhichChangeIsToBeFound+1)
numberOfCoinsUsedForChange = [0]*(amntForWhichChangeIsToBeFound+1)
for cents in range(amntForWhichChangeIsToBeFound+1):
#This loop starts finding change from 1 cent, then 2,3,4..amntForWhichChangeIsToBeFound
coinCount = cents
LastCoinUsedforChange = 1
for j in [c for c in coinsWeHaveUsingwhichChangeHastoBeFound if c <= cents]:
if numberOfCoinsUsedForChange[cents - j] + 1 < coinCount:
coinCount = numberOfCoinsUsedForChange[cents - j] + 1
LastCoinUsedforChange = j
numberOfCoinsUsedForChange[cents] = coinCount
LastcoinUsedToGetChangeArray[cents] = LastCoinUsedforChange
#print (numberOfCoinsUsedForChange)
#print (LastcoinUsedToGetChangeArray)
print("Number of coins used: "+ str(numberOfCoinsUsedForChange[amntForWhichChangeIsToBeFound]))
print("Here are the coins used ")
printCoins(amntForWhichChangeIsToBeFound, LastcoinUsedToGetChangeArray)

main()
```

Finallllllllly!! I’ll following up with few more posts on Dynamic programming and Golang implementation of HTTP/2 in the further posts to come …. Till then , Happy Coding 😀

# Preparing to land on C++ core of NodeJS: Sharpening the weapons – Using C++ Templates

Ahhhhhhhhhhhhhhh!!!!!! Travelling 700Kms without music or books on Technology is so pissing off!!!!This is what i call as “Throw away your frustration blog”  😛 😛 Enough !!!!
In the last blog i started out the series on Peeking into the Source code of node.Js .And also i promised to get into the C++ core of NodeJs while i had restricted myself to the
top most layer of node , that is the Javascript layer of it , dont remember ?? :PThen take a look at this .
So you might be thinking now “Yaay, its now time to start with the C++ core of NodeJs”….But when i started out with the defination of GetCIphers() of the TLS node module inside the C++ core ,the C++ lines of code written were just mindblowing. If you check the lines between 4807-4823 in this link from source of node you’ll understand C++ sophistication that lies beneath. It was important to get back to few important C++ concepts before landing on the C++ core of Node.So this post is on Preparing to land on NodeJs C++ Core..To be precise get Ready for a glimpse on C++ Templates and meddling around with them .C++ templates are widely used within the NodeJs core , so its vital to understand them thoroughly

Being into Hardcore Javascript development from past 15 months the term “template” reminds me of ReactJs , AngularJs Templates ,Jade , EJS ,Handle bars and Underscore Templates .Like Templates in Javascript libraries are used to generate dynamic html ,templates in C++ are used to write “generic programs ” where in the same piece of code can deal with variety of datatypes .

Still confused ??? Ill illustrate an example Lets say your are building a class which provides all the functionalities of a calculator .
Here is the link for the code on github .You can execute the code with cloud C++ IDE by clicking on this link

```
#include <iostream>
using namespace std;
class calculator {
public:
int multiply(int x,int y);

};

return x+y;
}

int calculator::multiply(int x,int y){
return x*y;
}
int main(){
calculator instance;
cout<<instance.multiply(5,2)<<endl;
}
```

.
So whats the issue here.
You can clearly see that the member functions Add and Multiply of the class Calculator
can work only on integer datatypes. They return int , the add take int values as
their parameters .
What if this decision on the data type to be worked upon could have made dynamic ??
What if the a same piece of code can dynamically make the same piece of code work for
various datatypes . Yes , its possible by the use of C++ class templates.
By using C++ class templates any given member function can be made flexible enought to be
able to work on various datatypes . Here is how to do it .Here is the implementation using
C++ template classes .
Here is the link of the code on Github.Click here to execute the same code using online C++ editor

```template <typename Type> class calcultor{
public:
Type multiply(Type x,Type y);
}

template <typename Type> Type calc<Type>::add(Type x,Type y)
{
return x+y;
}

template <typename Type> Type calc<Type>::multiply(Type x,Type y)
{
return x*y;
}

calcultor <int> instance1;
claculator <double> instance2;
```

baffled ??? 😛
Here is the detailed explanation ,

```template <typename Type> class calculator {}
```

is the declaration of the template class , here template and typename are the keywords and
this should be followed after the typename keyword , a placeholder name has to be given
to the variable datatypes that is sent during the creation of the object of the template class.
but it has to be made sure that the same placeholder name has to be used to refer to the
datatype in its member function .

```Type multiply(Type x,Type y);
```

by using this declaration the return type and the parameters of the member functions are also
made dynamic and are ot predefined like it is in the first case .

this is the format for writing the defination for the member functions of a template class .

```template <typename [namespace]> return_type parent_class<[namespace]>::member_function(parameters);
```

and Both the parameters and return Type can itself be dynamic template varialbles (as it is the case
the template class code example )

now while creating the new instance of the object you have the freedom to choose and set the
datatype on which the member functions process upon .

```calculator <int> instance1;
```

Now the ‘Type’ will be set to int , so this is equivaluent to

```class calculator {
public:
int multiply(int x,int y);

}

return x+y;
}

int calculator::multiply(int x,int y){
return x*y;
}
```

now ,

```calculator <double> instace2;
```

this is equivalent to

```class calculator {
public:
double multiply(double x,double y);

}

return x+y;
}

double calculator::multiply(double x,double y){
return x*y;
}

```

The same analogy can be applied to create functions templates .It is illustrated in the code below .

```#include <iostream>
#include <typeinfo>
using namespace std;
template <typename Type> void test_template(Type x){
cout << x <<endl;
cout << typeid(Type).name() << endl;
}
int main()
{

test_template<int>(2);
test_template<double>(3.0);
return 0;
}
```

## More Meddling with Class templates

### Using class templates as function arguments parameters

Here is a piece of code where Template classes are sent as arguments , the comments give a clear explanation on the syntax.Here is the link of the code on Github.Click here to execute the code on Cloud IDE.

```#include <iostream>

template<class Type>
class Other {

public:
Type x;
Other(Type y){
x = y;
}
};

void first(const Other<int>& o) {/*One way of specifying the formal parameter*/

std::cout << o.x << '\n';
}

template<typename T> void second(const Other<T>& o) {/*Other way of specifyin formal parameter*/
/*Has to be decalred as templated function*/
std::cout << o.x << '\n';
}

int main(){
Other<int> other(123);/*initializing template class constructor*/
first(other);/*sending templated class as parameters*/
second(other);
}

```

Now you know how template classes are sent as function parameters and how the actual and formal parameters are defined .
The C++ core of NodeJs contains magnificent pieces of C++ writing and its very essential to have a strong hold of C++ to be able to comprehend the lines written and this blog was an attempt at helping you guys achieve it .We are Getting closer and closer to land on the planet on NodeJs C++ core ….Its just matter of time !!!
Till then …………….As Usual , Happy Coding 😀

# Algorithms using python:Graph Algorithms-1:Depth First search

Firstly hello to all the readers !!After the last and its previous post on node.js , Here is the first post of the series of posts to come related to algorithms using python.In this post Ill be discussing about popular tree traversal algorithm Depth First Search . Using python makes the implementation of the algorithm relatively easy because of the availability of numerous built in data structures like hashes(dictionaries) ……….In this this blog post ill be using dictionaries as the main data structure for most of the operations .I’ve tried my best to enhance the degree of detailing in the post so that folks with even least acquaintance with python can understand the code . So then what are we waiting for??? Lets begin 😛

1.REPRESENTATION OF GRAPH USING DICTIONARIES IN PYTHON

A graph will represented using a JSON like structure . here is an example …

Consider the following graph

Here node A is connected to nodes B,C and E and this is represented as described below

{

‘A’:{‘B’:1,’C’:1 }

}

Using the similar approach here is the representation of the complete graph

{

‘A’:{‘B’:1,’C’:1,’E’:1},

‘B’:{‘A’:1,’D’:1,’F’},

‘C’:{‘A’:1,’G’:1},

‘D’:{},

‘E’:{‘A’:1,’F’:1},

‘F’:{‘B’:1,’E’:1},

‘G’:{}

}

• Declaration of a dictionary

Declaring an empty dictionary in python very simple , the line below illustrates it

`      example_dictionary = {}             `

Now lets see given tuples containing the pair of codes between which there exists an edge , how to convert them into graph

representation given above and store them in dictionaries ,Here is the tuple representation of connected nodes of the above graph

[(‘A’,’B’),(‘A’,’C’),(‘A’,’E’),(‘B’,’D’),(‘B’,’F’),(‘C’,’G’),(‘E’,’F’)]

```def make_link(G,node1,node2):
if node1 not in G:
G[node1]= { }
(G[node1])[node2]= 1
if node2 not in G:
G[node2]= {}
(G[node2])[node1]= 1
return G
anil_akg rediff

connections = [('a','g'),('a','d'),('d','g'),('g','c')]
G = {}

print G

```

Here are the key points that could help you understand the above operations on dictionary G

```G= {} #initializes the empty dictionary
G['A'] = {} #Creates a key 'A' in the dictionaries and assigns the key to a value of another empty hash
(G['A'])['B'] = 1 #Creates a Sub-Hash for key 'A' of the hash,Sub-hash is {'B':1}
print G
```

Here is the screen shot with the above mentioned operations , this will help you understand the process of representing a Graph similar to JSON using dictionaries .

2.Concept of Depth first search

As wikipedia quotes “Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Now let us traverse the above graph using Depth-First-Search.Lets start from node ‘A’ and then move to any of its neighbouring nodes,lets say ndoe ‘C’ , mark these nodes when you visit them for the first time , ‘C’ has only one neighbour ‘G’,so move to node ‘G’ .’G’ has no neighbours so now start backtracking,move to the previous node , that is node ‘C’,node has no more unvisited neighbours , ‘G’ has already been visited.So now backtrack to ‘A’ ,since ‘C’ has already been visited now move on to an unvisited node of ‘A’ , lets say ‘B’ , this process repeats till all the nodes of the graph are visited ,Here is the python code to achieve the some

```def make_link(g,node1,node2): #function to construct the graph in JSOn like format
if node1 not in G:
G[node1]={}
(G[node1])[node2]=1
if node2 not in G:
G[node2]={}
(G[node2])[node1]=1

G={} #initializing the empty grapgh
connections = [('A','B'),('A','C'),('A','E'),('B','D'),('B','F'),('C','G'),('E','F')] #tuples representing the connections

for x,y in connections:make_link(G,x,y) #constructing the graph using tuple representation

print G

def dfs(G,node,traversed):
traversed[node]=True #mark the traversed node
print "traversal:"+ node
for neighbour_nodes in G[node]: #take a neighbouring node
if neighbour_nodes not in traversed: #condition to check whether the neighbour node is already visited
dfs(G,neighbour_nodes,traversed) #recursively traverse the neighbouring node

def start_traversal(G):
traversed = {} #dictionary to mark the traversed nodes
for node in G.keys(): #G.keys() returns a node from the graph in its iteration
if node not in traversed: #you start traversing from the root node only if its not visited
dfs(G,node,traversed); #for a connected graph this is called only once

start_traversal(G)

```

The comments in the code explains everything . The worst case time complexity of DFS is of order n*m , ‘n’ is the number of nodes and ‘m’ is no of edges .We’ll thats it for now,hope that this post helped you understand the implementation of D.F.S in python 😀 see you folks soon with more exciting posts,this is the link to the code from my GITHUB profile

# Function to Dynamically allocating memory to store set of strings using malloc in C

```char **str ; //global variable

void dynamically_alocate_memory_for_strings(int no_of_strings,int max_length_of_string ) {
int i ;
str = (char **)malloc(no_of_strings * sizeof(char *));
for(i=0;i < no_of_strings;i++) {
str[i]=(char *)malloc(max_length_of_string*sizeof(char *));
}
}

```

# C Program to add elements of an array using Divide and Conquer approach

#include<stdio.h>
#include<stdio.h>
int main()
{
int *a,n,i,sum,mid;
printf(“\NEnter the no.of.elements: “);
scanf(“%d”,&n);
a=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
scanf(“%d”,a+i);
printf(“\nSum=%d”,sum);
return 0;

}

{
int mid;
if(high==low)
return a[low];
mid=(low+high)/2;
}

# Implementation of Binary Tree in C

//Enter the direction of the node to be inserted
//The direction will be validated and then the node will be inserted
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node* NODE;
struct node
{
int info;
};
NODE insert_node(int item,NODE root)
{
NODE temp;
NODE cur;
NODE prev;
char direction[100];
int i;
temp=(NODE)malloc(sizeof(struct node));
temp->info=item;
if(root==NULL)
return temp;
printf(“\nEnter DIRECTION(Must be combination of (l/r)): “);
scanf(“%s”,direction);//A Potential Bufferoverflow Vulnerablity , Use fgets instead
prev=NULL;
cur=root;
for(i=0;i<strlen(direction) && cur!=NULL;i++)
{
prev=cur;
if(direction[i]==’l’|| direction[i]==’L’)
else if(direction[i]==’r’ || direction[i]==’R’)
else
{
printf(“\n\n\n****Invalid Direction Input:Please enter either ‘L’ or ‘R’****\n\n\n “);
return root;
}
}
if(cur!=NULL || i!=strlen(direction))
{
if(cur!=NULL)
{
printf(“\n\n***Element already exists in the node, Entered path too short****”);
return root;
}
else
{
printf(“\n\n**The entered Direction is too long***”);
return root;
}
}
if(direction[i-1]==’l’ || direction[i-1]==’L’)
else
return root;

}
void inorder(NODE root)
{
if(root==NULL)
return ;
printf(“%d\t”,root->info);

}
void postorder(NODE root)
{
if(root==NULL)
return ;
printf(“%d\t”,root->info);
}
void preorder(NODE root)
{
if(root==NULL)
return ;
printf(“%d\t”,root->info);
}
void display(NODE root,int height)
{
int i=1;
if(root==NULL)
return ;
while(i<=height)
{
printf(“**”);
i++;
}
printf(“%d\n”,root->info);
}

int main()
{
NODE root=NULL;
int element,choice;
while(1)
{
printf(“\n\n\t1.INSERT NODE\n\t2.INORDER\n\t3.POSTODER\n\t4.PREORDER\n\t5.DISPLAY\n\t6.EXIT”);
scanf(“%d”,&choice);
switch(choice)
{
case 1:printf(“\nEnter the element: “);
scanf(“%d”,&element);
root=insert_node(element,root);
break ;
case 2:if(root==NULL)
printf(“\n\n\n\t\t****Tree Empty***\n\n\n”);
else
{
printf(“\nThe INORDER: “);
inorder(root);

}
break ;
case 3:if(root==NULL)
printf(“\n\n\n\t\t****Tree Empty***\n\n\n”);
else
{
printf(“\nThe POSTORDER: “);
postorder(root);

}
break ;
case 4:if(root==NULL)
printf(“\n\n\n\t\t****Tree Empty***\n\n\n”);
else
{
printf(“\nThe PREORDER: “);
preorder(root);

}
break ;
case 5:if(root==NULL)
printf(“\n\n\n\t\t***Tree Empty****\n\n\n\t”);
else
display(root,1);
break ;
default : exit(0);

}
}
}