Shashi
BAN USER- 0of 0 votes
AnswersYou are given two Strings lets say "S" which consist Upper Case albhabets and '?' character only and p. You are required to replace '?' with some alphabet so that resulting string have maximum number of "p" in it. You can replace '?' with any alphabet.
2. Replace '?' such that it should be lexicographically sorted.
Example
S="ABAAMA????MAZON????????"
p="AMAZON"
The final string S = "ABAAMAZONAMAZONAAAMAZON"
S="?????"
p="ABCD"
Final Result="AABCD"
Soln:- Proceed from the end of the String.
- Shashi in United States#include<stdlib.h> #include<stdio.h> #include<string.h> int main() { char S[]="ABAAMA????MAZON????????"; char p[]="AMAZON"; printf("%s \n",S); int i,j,flag=0; i=i=strlen(S)-1; while(i>=0) { int k=i; for(j=strlen(p)-1;j>=0;j--) { if(S[k]==p[j] || S[k]=='?') { k--; flag=1; } else { flag=0; break; } } int m=i if(flag==1) { for(j=strlen(p)-1;j>=0;j--) { if(S[m]=='?') S[m]=p[j]; m--; } } else { if(S[i]=='?') S[i]='A'; } i--; } printf("%s",S); }
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer String Manipulation
Implementation Of above approach:
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
struct graph
{
int value;
int leftLPL;
int rightLPL;
struct graph *left;
struct graph *right;
}*root,*lpr;
struct graph *creategraph(int k)
{
struct graph *temp=malloc(sizeof(struct graph));
temp->value=k;
temp->left=NULL;
temp->right=NULL;
return temp;
}
int m=0;
int max(int a, int b)
{
if(a>b)
return a;
else
return b;
}
struct graph *FindRootOfLP(struct graph *r)
{
if(r!=NULL)
{
if(r->left!=NULL)
FindRootOfLP(r->left);
if(r->right!=NULL);
FindRootOfLP(r->right);
if(r->left==NULL)
r->leftLPL=0;
else
r->leftLPL=max(r->left->leftLPL,r->left->rightLPL)+1;
if(r->right==NULL)
r->rightLPL=0;
else
r->rightLPL=max(r->right->leftLPL,r->right->rightLPL)+1;
if(r->leftLPL+r->rightLPL>m)
{
m=r->leftLPL+r->rightLPL;
lpr=r;
}
}
return lpr;
}
void PrintRightST(struct graph *R)
{
if(R==NULL)
return;
printf("%d ",R->value);
if(R->leftLPL>R->rightLPL)
PrintRightST(R->left);
else
PrintRightST(R->right);
}
void PrintLeftST(struct graph *L)
{
if(L==NULL)
return;
if(L->leftLPL>L->rightLPL)
PrintLeftST(L->left);
else
PrintLeftST(L->right);
printf("%d ",L->value);
}
void printLP(struct graph *l)
{
struct graph *tempL=l->left;
struct graph *tempR=l->right;
PrintLeftST(tempL);
printf("%d ",l->value);
PrintRightST(tempR);
}
void printLongestWalk(struct graph *k)
{
struct graph *lpr1=FindRootOfLP(k);
//printf("%d\n",lpr1->value);
printLP(lpr1);
}
int main()
{
root=creategraph(11);
root->left=creategraph(4);
root->right=creategraph(15);
root->left->left=creategraph(3);
root->left->right=creategraph(8);
root->left->left->left=creategraph(7);
root->left->left->left->left=creategraph(1);
root->left->right->right=creategraph(10);
root->left->right->right->right=creategraph(3);
printLongestWalk(root);
}
#include<stdio.h>
#include<stdlib.h>
int B[100];
int j=0;
int largest(int *p[],int n, int r, int *counter)
{
int i;int max=*p[r];
for(i=r+1;i<n;i++)
{
if(*(p[i])>max)
{
max=*p[i];
}
}
for(i=0;i<n;i++)
{
if(max==*p[i])
{
p[i]--;
counter[i]++;
}
}
return max;
}
int main()
{
int x[4][6]={{2,5,7,9,14,16},
{3,6,8,10,15,21},
{4,7,9,15,22,35},
{7,8,9,22,40,58}};
int m=4;//number of rows
int n=6;//number of columns
int *p[4]={x[3]+5,x[2]+5,x[1]+5,x[0]+5};//array of pointer storing each rows
int i,s=0;
int counter[4];
int r=0;
int k=5;
for(i=0;i<m;i++)
counter[i]=0;
int kth;
while(s<k)
{
if(counter[r]==n)
r--;
kth=largest(p,m,r,counter);
//printf("%d\n",kth);
s++;
}
printf("%d\n",kth);
}
Do you really think it will work?? Logic is correct and that is already there in the problem itself. Thing that you need to worry about is manage pointers properly.
e.g 1->2->3->4->5->6 k=2, m=1;
head= 2, 1->next=3, 3->next=5 and soon. So, be careful when you write the code.
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
struct graph
{
int value;
struct graph *left;
struct graph *right;
}*root;
struct graph *creategraph(int k)
{
struct graph *temp=malloc(sizeof(struct graph));
temp->value=k;
temp->left=NULL;
temp->right=NULL;
return temp;
}
int Search(struct graph *root,struct graph *m, int diff)
{
struct graph *r=root;
while(r!=NULL)
{
if(r->value==diff && r!=m)
{
printf("First Node :%d\n",r->value);
return 1;
}
if(r->value<diff)
r=r->right;
else
r=r->left;
}
}
void Find2NodeSumisX(struct graph *k,int sum)
{
if(k==NULL)
return;
int i=0;
i=Search(root,k,sum-k->value);
if(i==1)
{
printf("Second Node Value: %d\n Found!!",k->value);
exit(0); // if You want to print all such combination of two node which give a sum of X remove exit(0)
}
if(k->value>=sum)
Find2NodeSumisX(k->left,sum); // if sum<=root->value the both required node must be in left subtree
else
{
Find2NodeSumisX(k->left,sum);
Find2NodeSumisX(k->right,sum);
}
}
int main()
{
root=creategraph(11);
root->left=creategraph(4);
root->right=creategraph(15);
root->left->left=creategraph(3);
root->left->right=creategraph(8);
root->left->left->left=creategraph(7);
root->left->left->left->left=creategraph(1);
root->right->left=creategraph(10);
root->right->right=creategraph(16);
root->right->right->right=creategraph(14);
root->right->left->left=creategraph(5);
root->right->right->right->right=creategraph(2);
int X=31;
Find2NodeSumisX(root,X);
}
#include<stdio.h>
#include<stdlib.h>
struct node
{
int val;
struct node *next;
}*head;
struct node* createnode(int k)
{
struct node *temp=malloc(sizeof(struct node));
temp->val=k;
temp->next=NULL;
return temp;
}
void printlist(struct node *h)
{
struct node *k=h;
while(k!=NULL)
{
printf("%d->",k->val);
k=k->next;
}
printf("NULL");
}
void KrvrseMtrvrse(struct node *h, int k, int m)
{
struct node* curr=h;
struct node *prev=NULL;
struct node *nxt,*last,*init;
int i;
int c;
c=0;
while(curr!=NULL)
{
i=0;
c++;
last=prev;
init=curr;
while(i<k && curr!=NULL)
{
nxt=curr->next;
curr->next=prev;
prev=curr;
curr=nxt;
i++;
}
if(c==1)
head=prev;
else
last->next=prev;
prev=init;
init->next=curr;
while(curr!=NULL && i<k+m)
{
curr=curr->next;
prev=prev->next;
i++;
}
}
}
int main()
{
head=createnode(1);
head->next=createnode(2);
head->next->next=createnode(3);
head->next->next->next=createnode(5);
head->next->next->next->next=createnode(9);
head->next->next->next->next->next=createnode(7);
head->next->next->next->next->next->next=createnode(4);
head->next->next->next->next->next->next->next=createnode(6);
head->next->next->next->next->next->next->next->next=createnode(12);
head->next->next->next->next->next->next->next->next->next=createnode(31);
head->next->next->next->next->next->next->next->next->next->next=createnode(11);
head->next->next->next->next->next->next->next->next->next->next->next=createnode(10);
printlist(head);
printf("\n");
KrvrseMtrvrse(head,3,2);
printlist(head);
}
My solution is :
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *right;
struct node *left;
}*root;
struct node *createnode(int k)
{
struct node *nwnode=malloc(sizeof(struct node));
nwnode->data=k;
nwnode->left=NULL;
nwnode->right=NULL;
return nwnode;
}
void PrintLevelNodeBottomUp(struct node *t)
{
if(t==NULL)
return;
struct node *List[20];
int m;
for(m=0;m<20;m++)
List[m]=NULL;
int i=0;
int j=0;
List[i++]=t;
struct node *pP=List[0];
List[i++]=createnode(-1);
while(pP!=NULL && List[j+1]!=NULL)
{
if(pP->right!=NULL && pP->data!=-1)
List[i++]=pP->right;
if(pP->left!=NULL && pP->data!=-1)
List[i++]=pP->left;
if(pP->data==-1)
List[i++]=createnode(-1);
pP=List[++j];
}
for(m=i-1;m>=0;m--)
{
if(List[m]->data==-1)
printf("\n");
else
printf("%d ",List[m]->data);
}
}
int main(int args,char *argv[])
{
root=createnode(11);
root->left=createnode(4);
root->right=createnode(15);
root->left->left=createnode(3);
root->left->right=createnode(8);
root->left->left->left=createnode(7);
root->left->left->left->left=createnode(1);
root->right->left=createnode(10);
root->right->right=createnode(16);
root->right->right->right=createnode(14);
root->right->left->left=createnode(5);
root->right->right->right->right=createnode(2);
PrintLevelNodeBottomUp(root);
}
It will take 0(n) time and O(nlogn) space , I am sure there is much better solution possible.
- Shashi January 25, 2013A general solution that can be used for any number(m) of sorted arrays of variable length: here m=4;
#include<stdio.h>
#include<stdlib.h>
int smallest(int *p[],int n, int *size, int *counter)
{
int i;int min=100;
for(i=0;i<n;i++)
{
if(counter[i]!=size[i])
if(*(p[i])<min)
{
min=*p[i];
}
}
for(i=0;i<n;i++)
{
if(counter[i]!=size[i])
if(min==*p[i])
{
p[i]++;
counter[i]++;
break;// Remove break if you want to remove duplicates
}
}
return min;
}
int main()
{
int a0[4]={2,5,7,9};
int a1[4]={3,6,8,14};
int a2[5]={4,7,9,11,22};
int a3[5]={7,8,9,22,40};
int m=4;//number of arrays
int *p[4]={a0,a1,a2,a3};//array of pointer storing each array pointer
int size[4]={sizeof(a0)/sizeof(a0[0]),sizeof(a1)/sizeof(a1[0]),sizeof(a2)/sizeof(a2[0]),sizeof(a3)/sizeof(a3[0])};
int i,k=0;
int counter[m];
int B[100];
int total_size=0;
for(i=0;i<m;i++)
{
counter[i]=0;
total_size+=size[i];
}
//printf("%d ",total_size);
while(k<total_size)
{
int s=smallest(p,m,size,counter);
//if(s==100) Add this if you are removing duplicates;
// break;
B[k++]=s;
}
for(i=0;i<k;i++)
printf("%d\n",B[i]);
}
My approach would be:
Assign 2 variables with each node- leftLPL and rightLPL
and calculate for every node recursively:
if(node->left!=NULL)
node->leftLPL=max(node->left->leftLPL,node->left->rightLPL)+1;
else
node->leftLPL=0;
if(node->right!=NULL)
node->rightLPL=max(node->left->leftLPL,node->left->rightLPL)+1;
else
node->rightLPL=0;
same time look for the node which has max (node->leftLPL+node->rightLPL)
return that node lets say LPR;
and then...
PrintDiameterofTree(LPR)
#include<stdio.h>
#include<stdlib.h>
int B[100];
int j=0;
void smallest(int *p[],int n, int r, int *counter)
{
int i;int min=*p[r];
for(i=r+1;i<n;i++)
{
if(*(p[i])<min)
{
min=*p[i];
break;
}
}
for(i=0;i<n;i++)
{
if(min==*p[i])
{
p[i]++;
counter[i]++;
}
}
B[j++]=min;
}
int main()
{
int x[4][6]={{2,5,7,9,14,16},
{3,6,8,10,15,21},
{4,7,9,15,22,35},
{7,8,9,22,40,58}};
int m=4;//number of rows
int n=6;//number of columns
int *p[4]={x[0],x[1],x[2],x[3]};//array of pointer storing each rows
int i,k=1;
int counter[4];
int r=0;
for(i=0;i<m;i++)
counter[i]=0;
while(k<m*n)
{
if(*p[r]==x[m-1][n-1])
break;
if(counter[r]==n)
r++;
smallest(p,m,r,counter);
k++;
}
B[j++]=x[m-1][n-1];
for(i=0;i<j;i++)
printf("%d\n",B[i]);
//
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char op[4]; // temporary array to store combination
int print(char *s,int k,int n)
{
int i;
static int count=0;
for(i=0;i<strlen(s);i++)
{
op[n]=s[i];
if(n==k-1)
{
printf("%s\n",op);
count++;
}
else
print(s,k,n+1);
}
return count;
}
{
int n;
printf("\n%d\n",print("abc",2,0));
}
A recursive solution which will create a doubly linked list of vertical sum of the tree:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int val;
struct node *next;
struct node *prev
}*head;
struct graph
{
int value;
struct graph *left;
struct graph *right;
}*root;
struct node* createnode(int k)
{
struct node *temp=malloc(sizeof(struct node));
temp->val=k;
temp->next=NULL;
temp->prev=NULL;
return temp;
}
struct graph *creategraph(int k)
{
struct graph *temp=malloc(sizeof(struct graph));
temp->value=k;
temp->left=NULL;
temp->right=NULL;
return temp;
}
void TreetoSumList(struct node *h, struct graph *r)
{
if(r==NULL)
return;
h->val=h->val+r->value;
if(r->left!=NULL)
{
if(h->prev==NULL)
{
h->prev=createnode(0);
h->prev->next=h;
}
TreetoSumList(h->prev,r->left);
}
if(r->right!=NULL)
{
if(h->next==NULL)
{
h->next=createnode(0);
h->next->prev=h;
}
TreetoSumList(h->next,r->right);
}
}
int main()
{
root=creategraph(3);
root->left=creategraph(2);
root->left->right=creategraph(7);
root->right=creategraph(4);
root->right->left=creategraph(1);
head=createnode(0);
TreetoSumList(head,root);
}
You may check question?id=15316686
- Shashi February 04, 2013