gautam714
BAN USERGeneric code when no of independent arrays = (ROW*COL/row*col) is an integer.
#include<stdio.h>
#include<stdlib.h>
void matrixToArray(int arr[][6],int ROW,int COL,int row,int col)
{
if((ROW*COL)%(row*col)!=0)
{
printf("No splitting possible\n");
return;
}
int noArrays=ROW/row;
int rowBound=0;
int colBound=0;
while(noArrays--)
{
int i=0,j=0;
for(i=rowBound;i<rowBound+row;i++)
for(j=colBound;j<colBound+col;j++)
printf("%2d ",arr[i][j]);
printf("\n");
for(i=rowBound;i<rowBound+row;i++)
for(j=(col-colBound);j<(COL-colBound);j++)
printf("%2d ",arr[i][j]);
printf("\n");
rowBound+=row;
}
}
int main()
{
int A[4][6]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24};
matrixToArray(A,4,6,2,3);
getchar();
return 0;
}
Below is the code in C.Comments and suggestions are welcome.
/*************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct tstnode
{
char data;
int isEnd;
struct tstnode *left,*mid,*right;
};
struct listnode
{
char *word;
struct listnode *next;
};
struct queue
{
struct listnode *front;
struct listnode *rear;
};
/*Functions related to TST*/
struct tstnode *newtstnode(char data)
{
struct tstnode *temp=(struct tstnode *)malloc(sizeof(struct tstnode));
temp->data=data;
temp->isEnd=0;
temp->left=temp->mid=temp->right=NULL;
return temp;
}
int compareChar(const void *a,const void *b)
{
return *(char *)a-*(char *)b;
}
void insert(struct tstnode **root,char *word)
{
if(*root==NULL)
(*root)=newtstnode(*word);
if((*word)<(*root)->data)
insert(&(*root)->left,word);
else if((*word)>(*root)->data)
insert(&(*root)->right,word);
else
{
if(*(word+1))
insert(&(*root)->mid,word+1);
else
(*root)->isEnd=1;
}
}
int isAnagram(struct tstnode *root,char *dupWord)
{
if(root==NULL)
return 0;
if((*dupWord)<root->data)
return isAnagram(root->left,dupWord);
else if((*dupWord)>root->data)
return isAnagram(root->right,dupWord);
else
{
if(!(*(dupWord+1)))
return (root->isEnd==1);
else
return isAnagram(root->mid,dupWord+1);
}
}
/*End of functions related to TST*/
/*Functions related to queue*/
struct queue *createQueue(void)
{
struct queue *Q=(struct queue *)malloc(sizeof(struct queue));
Q->front=NULL;
Q->rear=NULL;
return Q;
}
int isEmptyQueue(struct queue *Q)
{
return (Q->front==NULL);
}
void enQueue(struct queue *Q,char *word)
{
struct listnode *temp=(struct listnode *)malloc(sizeof(struct listnode));
if(temp==NULL)
{
printf("No enough memory remains to creat more nodes");
return;
}
temp->word=(char *)malloc((strlen(word)+1)*sizeof(char));
memset(temp->word,0x00,(strlen(word)+1)*sizeof(char));
strcpy(temp->word,word);
temp->next=NULL;
if(Q->front==NULL&&Q->rear==NULL)
Q->front=Q->rear=temp;
else
{
Q->rear->next=temp;
Q->rear=temp;
}
}
char *deQueue(struct queue *Q)
{
if(isEmptyQueue(Q))
return NULL;
char *word=NULL;
struct listnode *temp=Q->front;
word=(char *)malloc((strlen(temp->word)+1)*sizeof(char));
memset(word,0x00,(strlen(temp->word)+1)*sizeof(char));
strcpy(word,temp->word);
Q->front=temp->next;
if(Q->front==NULL)
Q->rear=Q->front;
free(temp);
return word;
}
/*End of functions related to queue*/
void printAnagrams(struct queue *Q,struct tstnode *root)
{
char *dupWord=NULL,*word=NULL;
printf("Anagrams present in the queue are:\n");
while(!isEmptyQueue(Q))
{
word=deQueue(Q);
dupWord=(char *)malloc((strlen(word)+1)*sizeof(char));
memset(dupWord,0x00,(strlen(word)+1)*sizeof(char));
strcpy(dupWord,word);
qsort(dupWord,strlen(dupWord),sizeof(char),compareChar);
if(isAnagram(root,dupWord))
printf("%s\n",word);
free(word);
free(dupWord);
dupWord=NULL;
word=NULL;
}
}
/*Here I am taking words of size upto 20 to store in TST.you can allocate memory dynamically to create
words of size greater than this.*/
int main()
{
int i;
char buffer[20];
char word[5][20]={"RubyandPearls","ItisAwesome","Careercupquestions","Amazoninterview","RubyonRails"};
struct queue *Q=createQueue();
struct tstnode *root=NULL;
for(i=0;i<5;i++)
{
qsort(word[i],strlen(word[i]),sizeof(char),compareChar);
insert(&root,word[i]);
}
/*For understanding I am enqueueing only 8 words.One can keep on enqueueing till memory doesnot
get exhausted by slightly modifying the below code.*/
fflush(stdin);
for(i=0;i<8;i++)
{
gets(buffer);
enQueue(Q,buffer);
}
printAnagrams(Q,root);
getchar();
return 0;
}
/***********************************************************************/
Algo:
1)Construct a trie or TST(your choice) .I would preferably choose TST because of less memory waste as it is not mentioned that words are only made of alphabets.
2)Sort the 5 words(individually) and insert in the trie or TST (whatever you choose).
3)Dequeue word from the front ,save it in a temporary character array ,sort the temporary array and then match it with the 5 words stored in the trie or TST.
4)If you reach at the end for any particular word stored in the trie or TST just print the original dequeued word.
I hope this helps.I will soon post the actual code in C.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left,*middle,*right;
};
struct node *newNode(int data)
{
struct node *temp=(struct node *)malloc(sizeof(struct node));
temp->data=data;
temp->left=temp->middle=temp->right=NULL;
return temp;
}
void ternaryTreetoLL(struct node *root,struct node **prev)
{
if(root==NULL)
return;
ternaryTreetoLL(root->left,prev);
root->left=*prev;
(*prev)=root;
ternaryTreetoLL(root->middle,prev);
ternaryTreetoLL(root->right,prev);
}
void printList(struct node *head)
{
if(head==NULL)
return;
while(head!=NULL)
{
printf("%d ",head->data);
head=head->left;
}
}
int main()
{
struct node *root=newNode(10),*prev=NULL;
root->left=newNode(6);
root->middle=newNode(9);
root->right=newNode(13);
root->left->left=newNode(7);
root->left->middle=newNode(8);
root->left->right=newNode(5);
ternaryTreetoLL(root,&prev);
printList(prev);
getchar();
return 0;
}
I have solved this problem using greedy tachnique for max overlapping.Willingly I have taken int as birth or death year for dinosaurs.One can modify it for covering more ranges
- gautam714 February 02, 2013