Heapsort in Python

def parent(i):
return i/2

def  left(i):
return 2*i

def  right(i):
return 2*i+1


def heapify(A,i,n):
l=left(i)
r=right(i)
largest=i
if l<=n and A[l]>A[largest]:
largest=l
if r<=n and A[r]>A[largest]:
largest=r
if largest!=i:
A[i],A[largest] =A[largest],A[i]
heapify(A,largest,n)


def length(A):return len(A)-1

def buildheap(A):
n=length(A)
for x in xrange(n/2,-1,-1):
print x
heapify(A,x,length(A))

def heapsort(A):
buildheap(A)
heapsize=length(A)
for i in xrange(heapsize,0,-1) :

A[0],A[i]=A[i],A[0]
heapsize=heapsize-1
heapify(A,0,heapsize)

A=[4,8,1,2,11,3,9]
heapsort(A)
print A

insertion sort in Python

def insertion(A):
x=1
while(x<len(A)):

key=A[x]
i=x-1
while (i>=0)and (A[i]>key):
A[i+1]=A[i]
i=i-1
A[i+1]=key
x+=1
a=[3,2,1,4]
insertion(a)

Check if Expression is Balanced or Not using Stack in Python

import re
balance1 ='2+4-5+[(7+8)-[]]'
balance=list(balance1)
stack=[]
flag=1;

for x in balance:
if re.match('[\(\[\{]',x):
stack.append(x)
else:
if re.match('\)\}\]',x) and stack==[]:
flag=0
break
elif stack!=[]:
if x==')'and stack.pop()!='(':
flag=0
break
if x=='}'and stack.pop()!='{':
flag=0
break
if x==']'and stack.pop()!='[':
flag=0
break
if flag:
print("balanced")
else:
print("Not balanced")

Number of paths with exactly k coins-dynamic programming

#include <string>
#include <iostream>
using namespace std;
int countpath(int mat[][3],int m,int n,int k)
{
if(m<0||n<0)return 0;
if(m==0&&n==0)
{
return (k==mat[0][0]);

}
else
{
return countpath(mat,m-1,n,k-mat[m][n])+countpath(mat,m,n-1,k-mat[m][n]);
}
}
int main()
{
int  mat[3][3] = { {1, 2, 3},
                    {4, 6, 5},
                    {3, 2, 1}
                  };
                  int k=12;
     cout<<countpath(mat,2,2,k);
}

Check if two given strings are isomorphic

#include <string>
#include <iostream>
using namespace std;
int MAX_CHARS=256;
int isomer(string a,string b)
{
int n=a.length();
int m=b.length();
if(n!=m)
return 0;
int map2[MAX_CHARS];
bool map1[256]={false};
int i=0;
while(i<n)
{
if(map1[a[i]]&&b[i]!=map2[a[i]])
return 0;
if(!map1[a[i]])
{
map1[a[i]]=true;
map2[a[i]]=b[i];
}
i++;
}
return 1;
}
int main()
{
string s="abca",s1="xxzz";

cout<<isomer(s,s1);
}

Reverse an array without affecting special characters

#include <string>
#include <iostream>
using namespace std;

int isalpha(char c)
{
return ((c>='a'&&c<='z')||c>='A'&&c<='Z');
}
int main()
{
string s="a,bc";
int n=s.length()-1;
int i=0;

while(i<n)
{
if(isalpha(s.at(i))&& isalpha( s.at(n)))
{
char t=s.at(i);
s.at(i)=s.at(n);
s.at(n)=t;i++;n--;
}
else if(!isalpha(s.at(i))&&isalpha(s.at(n)))
i++;
else if(!isalpha(s.at(n))&&isalpha(s.at(i)))
n--;
else
i++,n--;
}
cout<<s;
}

Distance between two vertices in Graph

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;

struct graph
{
int e,v;
std::vector< vector <int> > vec;
};

void addEdge(graph *&g,int s,int d)
{
g->vec[s].push_back(d);g->vec[d].push_back(s);
}
graph *create(int v,int e)
{
graph *g=new graph;
g->v=v;
g->e=e;
g->vec.resize(v);

return g;
}
void bfs(graph *g,int k1,int visited[],int dist[])
{
queue <int > s;
s.push(k1);
visited[k1]=1;

for(int i=0;i<100;i++)
dist[i]=-1;
dist[k1]=0;
int k;
while(!s.empty())
{
k=s.front();
s.pop();
cout<<k<<" -> ";

for(int j=0;j<g->vec[k].size();j++)
{
if(dist[g->vec[k][j]]==-1)
{
s.push(g->vec[k][j]);
visited[g->vec[k][j]]=1;
dist[g->vec[k][j]]=dist[k]+1;
}
}
}
}

 int main()

{
int visited[100];

graph*g=create(5,7);
addEdge(g, 0, 1);
    addEdge(g, 0, 4);
    addEdge(g, 1, 2);
    addEdge(g, 1, 3);
    addEdge(g, 1, 4);
    addEdge(g, 2, 3);
    addEdge(g, 3, 4);
   
    cout<<endl;
    int dist[100];
    for(int i=0;i<100;i++)
visited[i]=0,dist[i]=-1;
    bfs(g,2,visited,dist);
    cout<<" Shortest distance between 2 and 0 is "<<dist[0];
return 0;
}

Detect Cycle in Graph

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

struct graph
{
int e,v;
std::vector< vector <int> > vec;
};

void addEdge(graph *&g,int s,int d)
{
g->vec[s].push_back(d);
}
graph *create(int v,int e)
{
graph *g=new graph;
g->v=v;
g->e=e;
g->vec.resize(v);

return g;
}

int  dfs(graph *g,int k,int visited[],int recstack[])
{

if(!visited[k]){
recstack[k]=1;
visited[k]=1;

for(int j=0;j<g->vec[k].size();j++)
{


if(!visited[g->vec[k][j]]&&dfs(g,g->vec[k][j],visited,recstack))
{
return 1;
}
else if(recstack[g->vec[k][j]])
return 1;
}
}
recstack[k]=0;
return 0;
}
 int main()
{
int visited[100],recstack[100];

graph*g=create(5,7);
addEdge(g, 0, 1);
    addEdge(g, 0, 4);
    addEdge(g, 1, 2);
    addEdge(g, 1, 3);
    addEdge(g, 1, 4);
    addEdge(g, 2, 0);
    addEdge(g, 3, 4);
   
    for(int i=0;i<100;i++)
{
recstack[i]=0;
visited[i]=0;
}
for (int i = 0; i < 5; i++)
{
for(int i1=0;i1<100;i1++)
{
recstack[i1]=0;
visited[i1]=0;
}
   if(dfs(g,i,visited,recstack))
   {
    cout<<" Cycle present ";
    break;
   }
 
}

return 0;
}

DFS and BFS of undirected graph

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

struct graph
{
int e,v;
std::vector< vector <int> > vec;
};

void addEdge(graph *&g,int s,int d)
{
g->vec[s].push_back(d);g->vec[d].push_back(s);
}
graph *create(int v,int e)
{
graph *g=new graph;
g->v=v;
g->e=e;
g->vec.resize(v);

return g;
}
void bfs(graph *g,int k,int visited[])
{
queue <int > s;
s.push(k);
visited[k]=1;
while(!s.empty())
{
k=s.front();
s.pop();
cout<<k<<" -> ";
for(int j=0;j<g->vec[k].size();j++)
{
if(!visited[j])
{
s.push(j);
visited[j]=1;
}
}
}
}
void dfs(graph *g,int k,int visited[])
{
stack <int > s;
s.push(k);
visited[k]=1;
while(!s.empty())
{
k=s.top();
s.pop();
cout<<k<<" -> ";
for(int j=0;j<g->vec[k].size();j++)
{
if(!visited[j])
{
s.push(j);
visited[j]=1;
}
}
}
}
 int main()
{
int visited[100];
for(int i=0;i<100;i++)
visited[i]=0;
graph*g=create(5,7);
addEdge(g, 0, 1);
    addEdge(g, 0, 4);
    addEdge(g, 1, 2);
    addEdge(g, 1, 3);
    addEdge(g, 1, 4);
    addEdge(g, 2, 3);
    addEdge(g, 3, 4);
    dfs(g,0,visited);
    cout<<endl;
    for(int i=0;i<100;i++)
visited[i]=0;
    bfs(g,2,visited);
return 0;
}

vertical redundancy check binary example

vertical redundancy check binary example

add 0 at the end of data block if

- no of 1's are even and parity is given 'even'.

add 1 at the end of data block if

-no of 1's are odd and  parity is given 'even'

for 'odd' parity given do opposite of above.

for eg.

data block is      1100101 parity ='even';

no of 1's = 4;

case 1 matched so, add 0 at the end and

output to be sent will be

                                                

                                            11001010.

eg.

if data block =1010100 parity is even

then,

no of 1's = 3

odd no of 1's and even parity

add 1 at the end

output will be

                                             10101001.

Left View of a Binary Tree

#include <iostream>
using namespace std;
struct node
{
int data;
node *left,*right;
};

void print(node *t)
{

if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}
void create(node *&t,int a)
{

if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a>=t->data)
{
create(t->right,a);
}
else
{
create(t->left,a);
}
}

void leftview(node *t,int level,int &maxlevel)
{
if(!t)
return;
if(maxlevel<level)
{
cout<<t->data<<" ";
maxlevel=level;
}

leftview(t->left,level+1,maxlevel);
leftview(t->right,level+1,maxlevel);
}
int main()
{

int k=0;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,-20,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<endl;
int h=0;
leftview(t,1,h);
return 0;
}

Check if All Leaf Nodes are at same Level in Binary tree

#include <iostream>
using namespace std;
struct node
{
int data;
node *left,*right;
};

void print(node *t)
{

if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

void create(node *&t,int a)
{

if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a>=t->data)
{
create(t->right,a);
}
else
{
create(t->left,a);
}
}
int max(int a,int b)
{
if(a>b)return a;
return b;
}
int height(node *t)
{
if(t==NULL)return 0;
else
return 1+max(height(t->left),height(t->right));
}
int atsamelevel(node *t,int c,int k)
{
if(!t)return 1;
if(!t->left&&!t->right)
if(c==k)return 1;
else return 0;

return (atsamelevel(t->left,c+1,k)&&atsamelevel(t->right,c+1,k));

}
int main()
{

int k=0;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<endl;
int h=height(t);
cout<<atsamelevel(t,0,h-1);
return 0;
}

Node at K distance from root Binary Tree

#include <iostream>
#include <fstream>
using namespace std;
int sum[100];
struct node
{
int data;
node *left,*right;
};

void print(node *t)
{

if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

void create(node *&t,int a)
{

if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a>=t->data)
{
create(t->right,a);
}
else
{
create(t->left,a);
}
}

void atk(node *t,int k,int c)
{
if(t==NULL)
return ;
if(k==c)cout<<t->data<<" ";
atk(t->left,k,c+1);
atk(t->right,k,c+1);

}
int main()
{

int k=2;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,1,2,34,23,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<endl;
atk(t,k,0);
return 0;
}

Width of Binary Tree

#include <iostream>
#include <fstream>
using namespace std;
int sum[100];
struct node
{
int data;
node *left,*right;
};

void print(node *t)
{

if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

void create(node *&t,int a)
{

if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a>=t->data)
{
create(t->right,a);
}
else
{
create(t->left,a);
}
}
int max(int a,int b)
{
if(a>b)return a;
return b;
}
int height(node *t)
{
if(t==NULL)return 0;
else
return 1+max(height(t->left),height(t->right));
}
int width(node *t,int l)
{
if(t==NULL)
return 0;
if(l==1)return 1;
if(l>1)
{
return width(t->left,l-1)+width(t->right,l-1);
}
return 0;
}
int treewidth(node *t)
{
int h=height(t);
int maxwidth=0;
for(int i=1;i<=h;i++)
{
int w=width(t,i);
if(w>maxwidth)
maxwidth=w;
}
return maxwidth;
}
int main()
{

int k=0;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<endl;
cout<<treewidth(t);
return 0;
}

Diameter of a Binary tree

#include <iostream>
using namespace std;
struct node
{
int data;
node * left;
node *right;
};
int height(node *t);
int max(int a ,int b)
{
if(a>b)
return a;
else return b;
}
int diameter(node *t)
{
if(t==NULL)return 0;
int ld=diameter(t->left);
int rd=diameter(t->right);
int lh=height(t->left);
int rh=height(t->right);
return max((lh+rh+1),max(lh,rh));
}
void create(node *&t,int a)
{

if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;

}
else if(a<t->data)
{
create(t->left,a);
}
else {
create(t->right,a);
}


}
void print(node *t)
{
if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

int height(node *t)
{
if(t==NULL)
return 0;
return 1+max(height(t->left),height(t->right));
}

int main()
{int k;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<diameter(t);
return 0;
}

Given a N*N square matrix, return an array of its anti-diagonals

http://qa.geeksforgeeks.org/4151/return-an-array-of-all-the-anti-diagonals

int n=A.size();
    int N=n-1;
    vector<pair<int,int>> search;
    for(int i=0;i<n;i++)
    {
        search.push_back(make_pair(0,i));
    }
    for(int i=1;i<n;i++)
    {
        search.push_back(make_pair(i,n-1));
    }
    vector <vector <int> > v;
   
    for(int i=0;i<search.size();i++)
    {
        int x=search[i].first;
        int y=search[i].second;
        vector<int > v1;
        while(x<n&&y>=0)
        {
            v1.push_back(A[x][y]);
            x+=1;
            y-=1;
        }
        v.push_back(v1);
    }
    return v;

Sort a linked list that is sorted alternating ascending and descending orders

Input List:   10->40->53->30->67->12->89->NULL
Output List:  10->12->30->43->53->67->89->NULL

#include <iostream>
using namespace std;
struct node {
int data;
node *next;

};

void print(node *t)
{

while(t!=NULL)
{
cout<<t->data<<" ";
t=t->next;
}
cout<<endl;
}
void rev(node *&t)
{
node *temp=NULL;
node *next;
node *cur=t;
while(t!=NULL)
{
next=t->next;
t->next=temp;
temp=t;
t=next;
}
t=temp;
}
void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->next=NULL;

}
else
{
create(t->next,a);
}
}
node *merge(node *t1,node *t2)
{
node *t=t1;
node *head=t;
t1=t1->next;
while(t1&&t2)
{

t->next=t2;
t=t->next;
t2=t2->next;
if(t1&&t2&&t2->data>t1->data)
{
node *temp=t1;
t1=t2;
t2=temp;
}
}
if(t1!=NULL)
t->next=t1;
else if(t2!=NULL)
t->next=t2;
return  head;
}
int main()
{
int a1[]={10 ,40 ,53 ,30 ,67, 12, 89,'\0'};
int n=7;
node *t=NULL;
for(int i=0;i<n;i++)
{
create(t,a1[i]);
}
print(t);
node *t1=t;
node *h1=NULL;
node *h2=NULL;
while(t1!=NULL&&t1->next!=NULL)
{
create(h1,t1->data);
t1=t1->next;
create(h2,t1->data);
t1=t1->next;
}
if(t1!=NULL)
create(h1,t1->data);
print(h1);

//print(h2);
rev(h2);
print(h2);
t=merge(h1,h2);
print(t);
return 0;
}

Rearrange a given linked list in-place

#include <iostream>
using namespace std;
struct node {
int data;
node *next;

};

void print(node *t)
{

while(t!=NULL)
{
cout<<t->data<<" ";
t=t->next;
}
cout<<endl;
}
void rev(node *&t)
{
node *temp=NULL;
node *next;
node *cur=t;
while(t!=NULL)
{
next=t->next;
t->next=temp;
temp=t;
t=next;
}
t=temp;
}
void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->next=NULL;

}
else
{
create(t->next,a);
}
}
node *merge(node *t1,node *t2)
{
node *t=t1;
node *head=t;
t1=t1->next;
while(t1&&t2)
{

t->next=t2;
t=t->next;
t2=t2->next;
node *temp=t1;
t1=t2;
t2=temp;

}
if(t1!=NULL)
t->next=t1;
else if(t2!=NULL)
t->next=t2;
return  head;
}
int main()
{
int a1[]={2,23,4,15,6,17,8,'\0'};
int n=7;
node *t=NULL;
for(int i=0;i<n;i++)
{
create(t,a1[i]);
}
print(t);
node *a[100];
node *t1=t;
int i=0;
node *t2=t;

while(t2&&t2->next&&t2->next!=NULL)
{
t1=t1->next;
t2=t2->next->next;
}
if(t2!=NULL)
t1=t1->next;
t2=t;
while(t2->next!=t1)
t2=t2->next;
t2->next=NULL;
print(t);cout<<endl;
print(t1);
rev(t1);
t=merge(t,t1);
print(t);
return 0;
}

Point to next higher value node in a linked list with an arbitrary pointer

#include <iostream>
using namespace std;
struct node {
int data;
node *next;
node *arb;
};


void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->next=NULL;
t->arb=NULL;
}
else
{
create(t->next,a);
}
}

int main()
{
int a1[]={2,23,4,15,6,17,8,'\0'};
int n=7;
node *t=NULL;
for(int i=0;i<n;i++)
{
create(t,a1[i]);
}
print(t);
node *a[100];
node *t1=t;
int i=0;

while(t1!=NULL)
{
a[i]=t1;
t1=t1->next;
i++;

}

for (int i = 0; i < n-1; i++)
{
/* code */
for(int j=0;j<n-i-1;j++)
{
if(a[j]->data>a[j+1]->data)
{
node *temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}

}
i=0;
while(i<n-1)
{
a[i]->arb=a[i+1];
i++;
}
a[i]->arb=NULL;
while(t->arb!=NULL)
{
cout<<t->data<<" ";
t=t->arb;
}
cout<<t->data;
return 0;
}

print common nodes in BST

#include <iostream>
using namespace std;
struct node
{
int data;
node *left,*right;
};
void print(node *t)
{
if(t!=NULL)
{
cout<<t->data<<" ";
print(t->left);
print(t->right);
}
}
node *newnode(int a)
{
node *t=new node;
t->data=a;
t->left=t->right=NULL;
return t;
}
void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;

}
else
{
if(a<t->data)
create(t->left,a);
else
create(t->right,a);
}
}
void printcommon(node *t1,node *t2)
{
if(t1==NULL||t2==NULL)
return ;

if(t1&&t2&&t1->data==t2->data)
cout<<t1->data<<" ";
else if(t1->data>t2->data)
{
printcommon(t1,t2->right);
printcommon(t1->left,t2);
}
else if(t1->data<t2->data){
printcommon(t1->right,t2);
printcommon(t1,t2->left);
}

}
int main()
{
node *t=NULL,*p=NULL;
int a[]={34,12,35,2,46,8,23,95,24};
int b[]={4,12,5,2,46,8,23,9,24};
int n=sizeof(a)/sizeof(a[0]);
cout<<n<<" \n";
int i=0;

for(int i=0;i<n;i++)
{
create(t,a[i]);
create(p,b[i]);
}

printcommon(t,p);

}

Mirror Binary tree

#include <iostream>
using namespace std;
struct node
{
int data;
node *left,*right;
};
void print(node *t)
{
if(t!=NULL)
{
cout<<t->data<<" ";
print(t->left);
print(t->right);
}
}
node *newnode(int a)
{
node *t=new node;
t->data=a;
t->left=t->right=NULL;
return t;
}

bool is_mirror(node *t1,node *t2)
{
if(t1==NULL&t2==NULL)
return true;
else if(t1&&t2&&t1->data==t2->data&&is_mirror(t1->left,t2->right)&&is_mirror(t1->right,t2->left))
return true;
return false;
}
int main()
{
node *t=NULL;
int a[]={34,12,35,2,46,8,23,95,24};
int n=sizeof(a);
int i=0;
t=newnode(3);
t->left=newnode(2);
t->right=newnode(2);
t->left->left=newnode(3);

t->left->right=newnode(4);

t->right->left=newnode(4);

t->right->right=newnode(3);
for(int i=0;i<n;i++)
{
//create(t,a[i]);
}
print(t);
cout<<is_mirror(t,t);
}

Reverse a String Word wise

Given an input string, reverse the string word by word.

Example:

Given s = "the sky is blue",

return "blue is sky the".

#include <iostream>

#include <sstream>

#include <string>

using namespace std;

void reverseWords(string &A) {

       string str="";

       stringstream ss;

      string str1;

      ss<<A;

    while(ss>>str1)

    {

       

       if(str=="")

           str=str1;

        elsea

           str=str1+" "+str;

       

    }

    

    cout<<str;

    A=str;

}

int main()

{

  string str=" hello  hi    ola ----  world ";

  reverseWords(str);

  return 0;

}