#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
A blog on programming and software design interview problems and solutions. Also there are some application development related stuff.
Pages
Friday, November 23, 2012
Given an array of positive integers, rearrange them so that they together form the largest number
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
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
Subscribe to:
Posts (Atom)