Friday, November 23, 2012

Given an array of positive integers, rearrange them so that they together form the largest number


#include<iostream>

#define SIZE 4
using namespace std;

bool decide(int a,int b)
{
int ta=a,tb=b;
int pa=1,pb=1;
while(a>0)
{
a/=10;
pa*=10;
}
while(b>0)
{
b/=10;
pb*=10;
}
int a_b=ta*pb+tb;//Append b after a.
int b_a=tb*pa+ta;//Append a after b.
if(a_b>b_a)
{
return false;
}
else
{
return true;
}
}

int main()
{
int A[SIZE]={87,181,9,5};
//Use any sorting technique but the decide function is the key.
for(int i=0;i<SIZE;i++)
{
for(int j=0;j<SIZE-i-1;j++)
{
if(decide(A[j],A[j+1]))
{
int t=A[j];
A[j]=A[j+1];
A[j+1]=t;
}
}
}
for(int i=0;i<SIZE;i++)
{
cout<<A[i]<<" ";
}
cout<<endl;
}
Input:
87 181 9 5
Output:
9 87 5 181

Thursday, November 22, 2012

Reverse the adjacent nodes in a linked list

Reverse the adjacent nodes of a linked list as described below in the sample input and output:
Input 1: 1->2->3->4->5
Output1: 2->1->4->3->5
Input2: 1->2->3->4->5->6
Output2: 2->1->4->3->6->5

#include<iostream>
#include<stdlib.h>
using namespace std;

struct node
{
int data;
struct node* next;
};

struct node* createlist(int length)
{
struct node *root=NULL,*end=NULL;
for(int i=1;i<=length;i++)
{
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data=i;
new_node->next=NULL;
if(i==1)
{
root=new_node;
end=root;
}
else
{
end->next=new_node;
end=new_node;
}
}
return root;
}
struct node* reverseadjacent(struct node* root)
{
int length=0;
struct node *temp=root;
while(temp!=NULL)
{
length++;
temp=temp->next;
}
if(length<2)
{
return root;
}
struct node *first=root,*sec=first->next,*third=sec->next;
root=first->next;
if(length==2)
{
sec->next=first;
first->next=NULL;
}
else if(length%2==0)
{
while(third!=NULL)
{
first->next=third->next;
sec->next=first;
first=third;
sec=third->next;
third=sec->next;
}
sec->next=first;
first->next=NULL;
}
else
{
while(third->next!=NULL)
{
first->next=third->next;
sec->next=first;
first=third;
sec=third->next;
third=sec->next;
}
sec->next=first;
first->next=third;
}
return root;
}
void printlist(struct node* root)
{
struct node* temp=root;
while(temp!=NULL)
{
cout<<temp->data<<"->";
temp=temp->next;
}
cout<<endl;
}
int main()
{
struct node* root=createlist(5);
cout<<"The given list\n";
printlist(root);
struct node* new_root=reverseadjacent(root);
cout<<"The new list\n";
printlist(new_root);
}

Tuesday, November 20, 2012

Printing all nodes at a given distance from a starting node in a binary tree


#include<iostream>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* createnode(int x)
{
struct node* new_node=new struct node;
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
return new_node;
};
int printKDistance(node* root,node* start,int k,int *found)
{
if(root)
{
//cout<<root->data<<endl;
if(k==0)
{
cout<<root->data<<endl;
}
else if(root==start || *found==1)
{
*found=1;
printKDistance(root->left,start,k-1,found);
printKDistance(root->right,start,k-1,found);
return 1;
}
else if(*found==0)
{
int ldist = printKDistance(root->left,start,k,found);
//cout<<"ldist="<<ldist<<endl;
int rdist=0;
if(*found==0)
{
rdist = printKDistance(root->right,start,k,found);
}
if((ldist == k || rdist == k) && *found==1)
{
cout<<root->data<<endl;
}
else
{
if(ldist!=0 || rdist!=0)
return ldist>rdist?1+ldist:1+rdist;
}
}
else
{
return 0;
}
}
else
{
return 0;
}
}
int main()
{
struct node* root=createnode(1);
root->left=createnode(2);
root->right=createnode(3);
root->left->right=createnode(4);
root->left->left=createnode(5);
root->right->right=createnode(6);
root->right->left=createnode(7);
root->right->right->left=createnode(8);
//root->right->right->left->left=createnode(10);
root->right->right->right=createnode(10);
int k=2;
//struct node* start = root->right->right->left;
struct node* start = root->right->left;
cout<<"start node="<<start->data<<endl;
cout<<"k="<<k<<endl;
int a=0;
int *found=&a;
printKDistance(root,start,k,found);
}
Output:
start node=7
k=2
Node: 1

Saturday, November 17, 2012

Integer Expression Evaluator using Infix-to-Postfix conversion and evaluation of Postfix expression


#include<iostream>
#include<string.h>
#include<ctype.h>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

class stack
{
private:
int top;
char A[100];//operator stack array
int B[100];//operand stack array
public:
char pop_oprt();
void undopop_oprt();
void push_oprt(char);
int get_top();
void displayoprt();
void init();
void push_opnd(int);
int pop_opnd();
};
void stack::init()
{
top=-1;
}
char stack::pop_oprt()
{
if(top==-1)
{
return 0;
}
else
{
char t = A[top];
top--;
return t;
}
}
void stack::push_oprt(char val)
{
top++;
A[top]=val;
}
void stack::undopop_oprt()
{
top++;
}
int stack::pop_opnd()
{
int t = B[top];
top--;
return t;
}
void stack::push_opnd(int val)
{
top++;
B[top]=val;
}
int stack::get_top()
{
return top;
}
void stack::displayoprt()
{
for(int i=top;i>=0;i--)
{
cout<<A[i]<<" ";
}
cout<<endl;
}
int prcd(char a)
{
if(a=='(')
{
return 0;
}
else if(a=='+')
{
return 1;
}
else if(a=='-')
{
return 1;
}
else if(a=='/')
{
return 2;
}
else if(a=='*')
{
return 2;
}
}
int evaluator(char post[100][10],int cnt)
{
stack opnd;
opnd.init();
int i=0;
while(i<cnt)
{
if(isdigit(post[i][0]))
{
opnd.push_opnd(atoi(post[i]));
//opnd.displayoprt();
}
else
{
int val2 = opnd.pop_opnd();
int val1 = opnd.pop_opnd();
if(post[i][0]=='*')
{
opnd.push_opnd(val1*val2);
}
else if(post[i][0]=='+')
{
opnd.push_opnd(val1+val2);
}
else if(post[i][0]=='-')
{
opnd.push_opnd(val1-val2);
}
else if(post[i][0]=='/')
{
opnd.push_opnd(val1/val2);
}
}
i++;
}
return opnd.pop_opnd();
}
int main()
{
//char A[100] = "4/2*2+2/2*4";
char A[100] = "(11+2)*(3+4)";
stack oprt;
oprt.init();
char post[100][10];
int cnt=00;
for(int i=0;i<strlen(A);)
{
//oprt.displayoprt();
//getchar();
int curr_num=0;
if(isdigit(A[i]))
{
while(isdigit(A[i]))
{
curr_num = curr_num*10 + A[i]-48;
i++;
}
itoa(curr_num,post[cnt],10);
cnt++;
}
else if(A[i]=='(')
{
oprt.push_oprt(A[i]);
i++;
}
else if(A[i]==')')
{
while(oprt.pop_oprt()!='(' && oprt.get_top()>-1)
{
oprt.undopop_oprt();
post[cnt][0]=oprt.pop_oprt();
post[cnt][1]=0;
cnt++;
}
i++;
}
else
{
//oprt.diplayoprt();
if(oprt.get_top()==-1)
{
oprt.push_oprt(A[i]);
//cout<<oprt.pop_oprt()<<endl;
}
else if(prcd(A[i])>prcd(oprt.pop_oprt()))
{
oprt.undopop_oprt();
oprt.push_oprt(A[i]);
}
else
{
oprt.undopop_oprt();
post[cnt][0]=oprt.pop_oprt();
post[cnt][1]=0;
cnt++;
oprt.push_oprt(A[i]);
}
i++;
}
}
while(oprt.get_top()>=0)
{
post[cnt][0]=oprt.pop_oprt();
post[cnt][1]=0;
cnt++;
}
cout<<"post-fix"<<endl;
for(int i=0;i<cnt;i++)
{
cout<<post[i]<<endl;
}
cout<<"Final value"<<endl;
cout<<evaluator(post,cnt)<<endl;
}
Output: 91

Thursday, November 15, 2012

Finding the Lowest Common Ancestor of two given nodes in a Binary Tree


#include<iostream>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
struct node* next;
};
struct node* createnode(int x)
{
struct node* new_node=new struct node;
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
new_node->next=NULL;
return new_node;
};
int help_anc(struct node* root,node* n1,node* n2)
{
if(root)
{
if(root==n1)
{
return 1;
}
else if(root==n2)
{
return 1;
}
else
{
return help_anc(root->left,n1,n2)+help_anc(root->right,n1,n2);
}
}
else
{
return 0;
}
}
struct node* Ancestor(node* root,node* n1,node* n2)
{
if(root)
{
int lf = help_anc(root->left,n1,n2);
int rf = help_anc(root->right,n1,n2);
if(lf==1 && rf==1)
{
return root;
}
else
{
node* lca = Ancestor(root->left,n1,n2);
if(lca!=NULL)
{
return lca;
}
lca = Ancestor(root->right,n1,n2);
return lca;
}
}
else
{
return NULL;
}
}
int main()
{
struct node* root=createnode(1);
root->left=createnode(2);
root->right=createnode(3);
root->left->right=createnode(4);
root->left->left=createnode(5);
root->right->right=createnode(6);
root->right->left=createnode(7);
root->right->right->left=createnode(8);
//root->right->right->left->left=createnode(10);
root->right->right->right=createnode(10);
struct node* n1 = root->right->right->right;
struct node* n2 = root->left->left;
struct node* lca=Ancestor(root,n1,n2);
if(lca)
{
cout<<lca->data<<endl;
}
}
Output:
1

Tuesday, November 13, 2012

Inorder, Preorder and Postorder Successor and Predecessor Functions inC++


#include<iostream>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
struct node* next;
};
struct node* createnode(int x)
{
struct node* new_node=new struct node;
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
new_node->next=NULL;
return new_node;
}
void inord_succ(struct node* root,struct node** prev)
{
if(root)
{
inord_succ(root->left,prev);
if(*prev!=NULL)
{
(*prev)->next = root;
*prev = root;
}
else
{
*prev = root;
}
inord_succ(root->right,prev);
}
}
void inord_pred(struct node* root,struct node** prev)
{
if(root)
{
inord_pred(root->left,prev);
root->next=*prev;
*prev=root;
inord_pred(root->right,prev);
}
}
void preord_succ(struct node* root,struct node** prev)
{
if(root)
{
if(*prev!=NULL)
{
(*prev)->next=root;
*prev=root;
}
else
{
*prev=root;
}
preord_succ(root->left,prev);
preord_succ(root->right,prev);
}
}
void preord_pred(struct node* root,struct node** prev)
{
if(root)
{
root->next=*prev;
*prev=root;
preord_pred(root->left,prev);
preord_pred(root->right,prev);
}
}
void postord_succ(struct node* root,struct node** prev)
{
if(root)
{
postord_succ(root->left,prev);
postord_succ(root->right,prev);
if(*prev!=NULL)
{
(*prev)->next=root;
*prev=root;
}
else
{
*prev=root;
}
}
}
void postord_pred(struct node* root,struct node** prev)
{
if(root)
{
postord_pred(root->left,prev);
postord_pred(root->right,prev);
root->next=*prev;
*prev=root;
}
}
void inorder(struct node* root)
{
if(root)
{
inorder(root->left);
cout<<root->data<<" ";
if(root->next)
{
cout<<root->next->data<<endl;
}
else
{
cout<<endl;
}
inorder(root->right);
}
}
void preorder(struct node* root)
{
if(root)
{
cout<<root->data<<" ";
if(root->next)
{
cout<<root->next->data<<endl;
}
else
{
cout<<endl;
}
preorder(root->left);
preorder(root->right);
}
}
void postorder(struct node* root)
{
if(root)
{
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
if(root->next)
{
cout<<root->next->data<<endl;
}
else
{
cout<<endl;
}
}
}
int main()
{
struct node* root=createnode(1);
root->left=createnode(2);
root->right=createnode(3);
root->left->right=createnode(4);
root->left->left=createnode(5);
root->right->right=createnode(6);
root->right->left=createnode(7);
root->right->right->left=createnode(8);
//root->right->right->left->left=createnode(10);
root->right->right->right=createnode(10);
struct node* ptr = NULL;
//inord_succ(root,&ptr);
//inord_pred(root,&ptr);
//inorder(root);
//preord_succ(root,&ptr);
//preord_pred(root,&ptr);
//preorder(root);
//postord_succ(root,&ptr);
postord_pred(root,&ptr);
postorder(root);
cout<<endl;
}

Tuesday, November 6, 2012

Number of closed rectangles in a matrix

Given a matrix containing only 1 and 0, find the number of closed rectangles. A closed rectangle is represented by at least one 0 surrounded by eight 1's. There is no overlap of closed rectangles.

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int rectangle(int A[][10],int i,int j,int d1,int d2,int cnt);
int A[][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,1,1,1,0,0,0},
{0,0,1,0,0,0,1,0,0,0},
{0,0,1,0,0,0,1,0,0,0},
{0,0,1,1,1,1,1,0,0,0},
{1,1,1,0,0,0,1,1,1,1},
{0,0,1,0,0,0,1,0,1,1},
{1,1,1,0,0,0,1,1,1,1}
};
int cnt=0;
for(int i=0;i<8;i++)
{
for(int j=0;j<10;j++)
{
cout<<A[i][j]<<" ";
}
cout<<endl;
}
for(int i=0;i<8;i++)
{
for(int j=0;j<10;j++)
{
if(A[i][j]>0)
{
cnt=rectangle(A,i,j,8,10,cnt);
}
}
}
cout<<"The number of closed rectangles is: "<<cnt<<endl;
}

int rectangle(int A[][10],int i,int j,int d1,int d2,int cnt)
{
cnt++;
int rnd=1;
if(i<d1-1 && j<d2-1 && A[i+1][j+1]==0)
{
j++;
while(j<d2 && i<d1-1 && A[i][j]==1 && A[i+1][j]==0)
{
A[i][j]=-1*cnt;
j++;
}
A[i][j]=-1*cnt;
rnd++;
}
if(i<d1-1 && j>0 && A[i+1][j-1]==0 && A[i][j]==-1*cnt)
{
i++;
while(i<d1 && j>0 && A[i][j]==1 && A[i][j-1]==0)
{
A[i][j]=-1*cnt;
i++;
}
A[i][j]=-1*cnt;
rnd++;
}
if(i>0 && j>0 && A[i-1][j-1]==0 && A[i][j]==-1*cnt)
{
j--;
while(j>=0 && i>0 && A[i-1][j]==0 && A[i][j]==1)
{
A[i][j]=-1*cnt;
j--;
}
A[i][j]=-1*cnt;
rnd++;
}
if(i>0 && j<d2-1 && A[i-1][j+1]==0 && A[i][j]==-1*cnt)
{
i--;
while(i>=0 && j<d2-1 && A[i][j+1]==0 && A[i][j]==1)
{
A[i][j]=-1*cnt;
i--;
}
A[i][j]=-1*cnt;
rnd++;
}
if(rnd!=5 || (A[i][j]!=0 && A[i][j]!=A[i][j+1]))
{
cnt--;
}
return cnt;
}
Output:
The number of closed rectangles is: 2