RADIX TREE

/* This is a program to implement RADIX tree. For more details on radix tree please refer to the link below -
http://en.wikipedia.org/wiki/Radix_tree

This program implements as shown in below figure. All the child nodes will be neighbors to first child

*/

NOTE: Please add the words in a file named dict,txt and keep in the same folder as the this program

/* program start*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define ALLOC_NODE (NODE *)malloc(sizeof(NODE))
#define ALLOC_CHAR(len) (char *) malloc(len+1)
#define ALLOC_LINK  (LINK*)malloc(sizeof(LINK))

typedef struct _node
{
char *str;
struct _node *nxt,*nbr;
}NODE;

typedef struct link
{
NODE *node;
struct link *prv;
}LINK;

void radix_create(NODE *node);
void radix_traverse(NODE *node, char *str);
NODE *radix_new_node(int len);
int radix_cmp(char *str1,char *str2);

NODE *radix_new_node(int len)
{
NODE *temp;
temp = ALLOC_NODE;
temp->nbr = NULL;
temp->nxt = NULL;
temp->str = ALLOC_CHAR(len+1);

return temp;
}


main()
{
NODE root;

root.nbr =NULL;
root.nxt = NULL;
root.str = NULL;
radix_create(&root);

return 0;
}

void radix_create(NODE *node)
{
FILE *fp;
char str[20];
NODE *tmp;

fp = fopen("dict.txt","r");
while(1)
{
if(EOF == fscanf(fp,"%s",str))
{
break;
}
else
{
if(node->nxt == NULL)
{
tmp = radix_new_node(strlen(str));
strcpy(tmp->str,str);
node->nxt = tmp;
}
else
{
radix_traverse(node->nxt,str);
}
}
}
return;
}

void radix_traverse( NODE *node, char *str)
{
NODE *temp1,*temp2;
int len,len1,len2;
char *tmp_str;

len = radix_cmp(node->str,str);
len1 = strlen(node->str);
len2 = strlen(str);
// already string is inserted
if(str[0]=='\0')
return;

if(len == 0)
{
// No match
if(node->nbr !=NULL)
{
radix_traverse(node->nbr,str);
}
else
{
temp1 = radix_new_node(len2);
strcpy(temp1->str,str);
node->nbr = temp1;
}
}
else if((len <len1) || (len == len1 && node->nxt == NULL))
{
// partial match or full match without leaves
temp1 = radix_new_node(len1-len);
temp2 = radix_new_node(len2-len);
memcpy(temp1->str,node->str+len,len1-len+1);
memcpy(temp2->str,str+len,len2-len+1);

temp1->nbr = temp2;
temp1->nxt = node->nxt;
node->nxt = temp1;

tmp_str = ALLOC_CHAR(len);
memcpy(tmp_str, node->str,len);
tmp_str[len] = '\0';
free(node->str);
node->str = tmp_str;
}
else
{
//full match
memcpy(str,str+len,len2-len+1);
radix_traverse(node->nxt,str);
}

return;
}

int radix_cmp(char *str1, char * str2)
{
int i=0;
while( str1[i] !='\0' && str2[i] != '\0' && str1[i] == str2[i])
{
i++;
}

return i;
}

/* END */

Dijkstra's algorithm for finding shortest path from source

/*DIJKSTRA's ALGORITHM*/
/* Following programs finds the shortest paths from a given node to all nodes in a graph*/
/*Make DEBUG 1 to get interactive program */
/*  Sample input
5 -> number of nodes
2 -> number of nodes conneceted to first node
1 10 2 5 -> node number, edge weight
2
4 1 2 2
3
4 9 3 2 1 3
2
4 6 0 7
1
3 4
2 ->source node
End */

/* Sample output

Shortest paths from Node2 are as below -
 Node0 => 9
 Node1 => 3
 Node2 => 0
 Node3 => 2
 Node4 => 4

End */

/*************** Program *************/
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100
#define TRUE 1
#define FALSE 0
#define DEBUG 0
typedef struct graph
{
int node_num;
int edge_len;
struct graph *next;
}graph;
typedef struct path
{
int len;
int valid;
}path;
graph *root;
int creat_graph(void);
void print_graph(int size);
void dijkstra(int size);
main()
{
int size;
size = creat_graph();
#if DEBUG
print_graph(size);
#endif
dijkstra(size);
return 0;
}

int creat_graph(void )
{
int size,i,num,j;
graph *temp,*new_temp;
#if DEBUG
printf("Enter number of vertices \n");
#endif
scanf("%d",&size);

root = (graph*)malloc(size*sizeof(graph));
for(i=0;i<size;i++)
{
root[i].node_num = i;
root[i].edge_len = 0;
root[i].next =NULL;
#if DEBUG
printf("Enter number of nodes connected to node %d\n",i);
#endif
scanf("%d",&num);
temp = &root[i];
for(j=0;j<num;j++)
{
#if DEBUG
printf("Enter node_number and edge length connected to node %d",i);
#endif
new_temp = (graph*)malloc(sizeof(graph));
scanf("%d %d",&new_temp->node_num, &new_temp->edge_len);
new_temp->next = NULL;
temp->next = new_temp;
temp = temp->next;
}
}
return size;
}
#if DEBUG
void print_graph(int size)
{
int i;
graph *temp;
for(i=0;i<size;i++)
{
printf("%d = ",root[i].node_num);
temp = root[i].next;

while(temp!=NULL)
{
printf("> [%d/%d]",temp->node_num,temp->edge_len);
temp = temp->next;
}
printf("\n");
}
}
#endif
void dijkstra(int size)
{
 path *temp;
 graph* temp_node;
 int i,j,k,node,source_node;

temp = (path*)malloc(size*sizeof(path));
for(i=0;i<size;i++)
{
temp[i].len = 0xffff;
temp[i].valid = TRUE;
}
#if DEBUG
printf("Enter source node\n");
#endif
scanf("%d",&node);
source_node= node;
temp[node].len =0;

for(i=0;i<size-1;i++)
{
temp_node = root[node].next;
while(temp_node!=NULL)
{
if((temp[temp_node->node_num].valid) &&
(temp[temp_node->node_num].len > (temp_node->edge_len + temp[node].len)))
{
temp[temp_node->node_num].len = (temp_node->edge_len + temp[node].len);
}
temp_node = temp_node->next;
}
temp[node].valid = FALSE;

for(j=0;j<size ;j++)
{
if(temp[j].valid)
{
node =j;
break;
}
}
for(k=j+1;k<size;k++)
{
if(temp[k].valid && temp[k].len < temp[node].len)
{
node = k;
}
}
#if DEBUG
for(j=0;j<size;j++)
{
printf("%d ", temp[j].len);
}
printf("- Itr %d \n",i);
#endif
}
printf("Shortest paths from Node%d are as below -\n ",source_node);
for(j=0;j<size;j++)
{
printf(" Node%d => %d\n ",j,temp[j].len);
}

}
/************* END ***********************/

BREADTH FIRST SEARCH of a GRAPH

/*A program to do breadth first search in a graph */

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int node_name;
int weight;
struct node *next;
}node;
node *graph;
typedef struct queue_list
{
int node_name;
struct queue_list *next;
}queue_list;

queue_list *queue = NULL,*queue_last=NULL;

int build_graph();
void print_graph(int size);
void breadth_first_search(int source_node);
int build_graph()
{
node *temp,*idx_graph;
int i,j,m,n;
//printf("Enter number of nodes in the graph\n");
scanf("%d",&n);
graph = (node*)malloc(sizeof(node)*n);
for(i=0;i<n;i++)
{  
graph[i].node_name = i+1;
graph[i].weight = -1;
graph[i].next=NULL;
//printf("Enter number of nodes connected to node %d\n",i+1);
scanf("%d",&m);
idx_graph = &graph[i];
//printf("Enter Node numbers connected to node %d\n",i+1);
for(j=0;j<m;j++)
{
temp = (node*)malloc(sizeof(node));
scanf("%d",&temp->node_name);
temp->weight =-1;
temp->next= NULL;
idx_graph->next = temp;
idx_graph = idx_graph->next;
}
}
return (n);
}

void print_graph(int size)
{
node *temp;
int i;
for(i=0;i<size;i++)
{
temp = &graph[i];
printf("%c/%d-> ",temp->node_name+'r'-1,temp->weight);
temp = temp->next;
while(temp)
{
printf("%c ",temp->node_name+'r'-1);
temp = temp->next;
}
printf("\n");
}
return;
}
void breadth_first_search(int source_node)
{
node *temp;
int weight= 0;
queue_list* queue_temp;

queue = (queue_list*)malloc(sizeof(queue_list));
queue->node_name = source_node;
queue->next = NULL;
queue_last = queue;
graph[queue->node_name-1].weight = 0;
while(queue !=NULL)
{
temp = graph[queue->node_name-1].next;
while(temp !=NULL)
{
if(graph[temp->node_name-1].weight ==-1)
{
/*Create new element */
queue_temp = (queue_list*)malloc(sizeof(queue_list));
queue_temp->node_name = temp->node_name;
queue_temp->next = NULL;

/*Add new element to the queue*/
queue_last->next = queue_temp;
queue_last = queue_temp;
/*update weight of all connected nodes*/
graph[temp->node_name-1].weight = graph[queue->node_name-1].weight+1;
}
temp = temp->next;
}
/*Free first element and move to next element in the queue*/
queue_temp = queue->next;
free(queue);
queue = queue_temp;
}
return;
}
main()
{
int size =0,source_node;
size = build_graph();
print_graph(size);
//printf("Enter Source node\n");
scanf("%d",&source_node);
if(source_node<=size)
{
breadth_first_search(source_node);
}
else
{
printf("Source node is out of graph size\n");
}
printf("\n");
print_graph(size);
getchar();
getchar();
return 0;
}

Reverse links of K-th order in Linked List

 

/* Explanation

write a program to given a linked list and input k

10->20->30->40->50->60->70->80->90->100

if k=2

output: 20->10->40->30->60->50->80->70->100->90

if k=3

output:30->20->10->60->50->40->90->80->70->100

if k=4

output:40->30->20->10->80->70->60->50->100->90

*/

/*Code*/

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
    int key;
    struct node *next;
}NODE;

void print_link(NODE *p);
void reverse_link(NODE **root);
main()
{
NODE *root=NULL,*p,*q,*r,*s;
int key,i,iteration;

    printf("Enter Numbers and -9999 to end\n");
    do
    {
        scanf("%d",&key);
        if(key == -9999)
        {
            break;
        }
        else
        {
            p= (NODE *)malloc(sizeof(NODE));
            p->key = key;
            p->next = NULL;
            q = root;
            if(q==NULL)
            {
                root = p;
            }
            else
            {
                while (q->next !=NULL)
                {
                    q=q->next;
                }
            q->next = p;
            }
        }
    }while(1);
    printf("Enter K \n");
    scanf("%d",&key);
     printf("original\n");
    print_link(root);
    p = root;
    iteration =1;

    while(p!=NULL && key>=1)
    {
        q=p;
        for(i=0;i<key-1 && p->next!=NULL;i++)
        {
            p=p->next;
        }
        if(iteration == 1)
        {
            root = p;
            iteration++;
        }
        else
        {
            s->next = p;
        }
        r = p->next;
        p->next = NULL;
        s=q;
        reverse_link(&q);
       
        p=r;
    }
    s->next = p;

      
    printf("reversed \n");
    print_link(root);

}

void print_link(NODE *p)
{
    while(p!=NULL)
    {
        printf("%d ",p->key);
        p=p->next;
    }
    printf("\n");
    return;
}
void reverse_link(NODE **root)
{
    NODE *p,*q,*r=NULL;

    if(*root == NULL)
        return;

    p=*root;

    if(p->next != NULL)
    {
        q=p->next;
        p->next = NULL;
        while(q!=NULL)
        {
            r=q->next;
            q->next=p;
            p=q;
            q=r;
        }
        *root = p;
    }
    return;
}

Given a paragraph of text, write a program to find the first shortest sub-segment that contains each of the given k words at least once. A segment is said to be shorter than other if it contains less number of words. Ignore characters other than [a-z][A-Z] in the text. Comparison between the strings should be case-insensitive. If no sub-segment is found then the program should output “NO SUBSEGMENT FOUND”.

/* CODE*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define DEBUG 0
#define START 0
#define END 1
#define LENGTH 2
#define OFFSET 3
#define MAX_STRING_LEN 15
#define MAX_WORD_LENGTH 200000
void parsed_string(char *input_word, char *output_word);
int find_min_seq(char *parsed_word,int parse_pos,char ref_word[][15],int ref_len);

int cmp_table[200000]={0};
int result_table[2] = {0,MAX_WORD_LENGTH};
char input_str[200000],parsed_str[200000]={'\0'};;
main()
{
    int parse_pos = 1,ref_len =0,result,i,j,k;
    char *orig_word,*temp_word,(*ref_word)[15],parsed_word[15],*temp_str,current_str[15];
    gets(input_str);
    scanf("%d",&k);
    temp_word = (char *)malloc(sizeof(char)*MAX_STRING_LEN*k);
    ref_word = (char (*)[MAX_STRING_LEN])temp_word;

    for(i=0;i<k;i++)
    {
        scanf("%s",current_str);
       
        for(j=0;j<ref_len;j++)
        {
            if(strcmp(current_str,ref_word[j])== 0)
                break;
        }
        if(j == ref_len)
            {
            strcpy(ref_word[ref_len++],current_str);
            }
    }
    orig_word = strtok(input_str," ");

    while(orig_word !=NULL)
    {       

        parsed_string(orig_word, parsed_word);
        strcat(parsed_str,parsed_word);       
        strcat(parsed_str," ");
        result = find_min_seq(parsed_word,parse_pos,ref_word,ref_len);
        if(result == 1)
            break;
        orig_word = strtok(NULL," ");
        parse_pos++;
    }

    if(cmp_table[LENGTH] != ref_len)
    {
        printf("NO SUBSEGMENT FOUND\n");
    }
    else
    {
        i = 1;
        temp_str = parsed_str;
        while(i <= parse_pos)
        {
            if(i >= result_table[START])
            {
                if(i < result_table[END])
                {
                   while(*temp_str != ' ')
                       printf("%c",*temp_str++);
                   printf(" ");
                }
                else
                {
                    while(*temp_str != ' ')
                        printf("%c",*temp_str++);
                    break;
                }
            }
            while(*temp_str++ != ' ');
            i++;
        }
     }
#if DEBUG
        printf("start : %d, End: %d\n", result_table[START],result_table[END]);
    getchar();getchar();
#endif
    return 0;
}

void parsed_string(char *input_word, char *output_word)
{
    int i=0,j=0;
    char ch;
    while(1)
    {
        ch = input_word[i++];
       
        if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
        {
            output_word[j++] = ch;
        }
        else if(ch == '\0')
        {
            output_word[j]='\0';
            break;
        }
        else
        {
            continue;
        }
    }
}

int find_min_seq(char *parsed_word,int parse_pos,char ref_word[][15],int ref_len)
{
    int result = 0;
    int i,j;

    for(i=0;i<ref_len;i++)
    {
        if(strcasecmp(parsed_word,ref_word[i]) == 0)
        {
            if(cmp_table[OFFSET+i] == 0)
            {
                cmp_table[LENGTH]++;
            }
           
            if(cmp_table[OFFSET+i] == cmp_table[START])
            {               
                cmp_table[OFFSET+i] = parse_pos;
                cmp_table[START] = get_min_value(ref_len);
            }
            else
            {
                cmp_table[OFFSET+i] = parse_pos;
            }
            cmp_table[END] = parse_pos;
           
            if(cmp_table[LENGTH] == ref_len)
            {
                if( (result_table[END]- result_table[START])> (cmp_table[END] - cmp_table[START]) )
                {
                    result_table[START] = cmp_table[START];
                    result_table[END] = cmp_table[END];
                }
                if(ref_len == (result_table[END]- result_table[START]+1))
                {
                    result = 1;
                }
                else
                {
                    result = 0;
                }
            }
            break;
        }
       
    }
#if DEBUG
    for(j=0;j<ref_len+OFFSET;j++)
        {
            printf("%d ",cmp_table[j]);
        }
        printf("\n");
#endif
    return(result);
}

int get_min_value(int len)
{
int min_val = cmp_table[OFFSET],i;

    for(i=OFFSET+1;i<len+OFFSET;i++)
    {
        if((cmp_table[i] !=0) && (min_val > cmp_table[i]))
        {
            min_val = cmp_table[i];
        }
    }

return(min_val);
}

Given a number K, find the smallest Fibonacci number that shares a common factor( other than 1 ) with it. A number is said to be a common factor of two numbers if it exactly divides both of them. Output two separate numbers, F and D, where F is the smallest fibonacci number and D is the smallest number other than 1 which divides K and F.

/* CODE*/
#include<stdio.h>

long long int common_factor(long long int a, long long int b);
main()
{

int t,a;
long long int temp,fib1,fib2,cf;

    scanf("%d",&t);
    while(t)
    {
        t--;
        scanf("%d",&a);

        fib1 = 1;
        fib2 = 2;   
        while(1)
        {
            cf = common_factor(a,fib2);
            if(cf == 1)
            {
                temp = fib2;
                fib2 = fib1+fib2;
                fib1 = temp;
            }
            else
            {
                printf("%lld %lld\n",fib2,cf);
                break;
            }

        }
    }

return 0;
}

long long int common_factor(long long int a,long long int b)
{
long long int temp;
    while(1)
    {
        if(b==0)
        {
            break;
        }
        else
        {
            temp = a%b;
            a=b;
            b=temp;
        }
    }
   
    return a;
}

Given M busy-time slots of N people, You need to print all the available time slots when all the N people can schedule a meeting for a duration of K minutes. Event time will be of form HH MM ( where 0 <= HH <= 23 and 0 <= MM <= 59 ), K will be in the form minutes.

 

/* CODE */
#include<stdio.h>
#include<stdlib.h>
#define DEBUG 0
#define MAX_TIME 1440
typedef struct time
{
int start_time;
int end_time;
struct time *next;
}TIME;

typedef enum EVENT_TYPE
{
    EVENT_TYPE_A,
    EVENT_TYPE_B,
    EVENT_TYPE_C,
    EVENT_TYPE_D,
    EVENT_TYPE_E,
    EVENT_TYPE_F
}EVENT_TYPE;

typedef enum FLAG_TYPE
{
    FALSE,
    TRUE
}FLAG_TYPE;
void print_free_slots(TIME *root, int duration);
void adjust_time_link(TIME *root,int start_time, int end_time);
void print_link (TIME * root);
EVENT_TYPE check_event_type(int old_start,int old_end,int new_start,int new_end);
main()
{
int k,duration,input_time,start_time,end_time;
TIME *root;

    root = (TIME *) malloc(sizeof(TIME));
    root->next = NULL;
    root->start_time = -1;
    root->end_time = -1;

        scanf("%d%d",&k,&duration);
        while(k)
        {
            k--;

            scanf("%d",&input_time);
            start_time = input_time*60;
           
            scanf("%d",&input_time);
            start_time = (start_time+input_time)%MAX_TIME;
           
            scanf("%d",&input_time);
            end_time = input_time*60;
           
            scanf("%d",&input_time);
            end_time =(end_time+input_time)%MAX_TIME;
           
            if(start_time < end_time)
            {
                adjust_time_link(root, start_time, end_time);
            }
            else if(start_time > end_time)
            {
                if(end_time != 0 )
                {
                    adjust_time_link(root, 0, end_time);
                }
                adjust_time_link(root, start_time, MAX_TIME);
            }
#if DEBUG
print_link ( root);
#endif
        }
        print_free_slots(root->next,duration);
#if DEBUG
        getchar();getchar();
#endif
return 0;
}
void adjust_time_link(TIME *root,int start_time, int end_time)
{
    TIME *temp,*prv_temp,*new_temp;
    EVENT_TYPE event_type;
    FLAG_TYPE  flag = TRUE;
    if(root->next == NULL)
    {
        new_temp = (TIME *) malloc(sizeof(TIME));
        new_temp->next = NULL;
        new_temp->start_time = start_time;
        new_temp->end_time = end_time;
        root->next = new_temp;
    }
    else
    {
        temp = root->next;
        prv_temp = root;

        while(flag == TRUE)
        {
            event_type = check_event_type(temp->start_time,temp->end_time,start_time,end_time);
            flag = FALSE;

            switch(event_type)
            {
                case EVENT_TYPE_A:
                    new_temp = (TIME *) malloc(sizeof(TIME));
                    new_temp->start_time = start_time;
                    new_temp->end_time = end_time;
                    prv_temp->next = new_temp;
                    new_temp->next = temp;
                    break;

                case EVENT_TYPE_B:
                    temp->start_time = start_time;
                    break;

                case EVENT_TYPE_C:
                    if(temp->next == NULL)
                    {
                        temp->start_time = start_time;
                        temp->end_time = end_time;
                    }
                    else
                    {
                        temp = temp->next;
                        free(prv_temp->next);
                        prv_temp->next = temp;
                        flag = TRUE;
                    }
                    break;

                case EVENT_TYPE_D:
                    if(temp->next == NULL)
                    {
                        temp->end_time = end_time;
                    }
                    else
                    {
                        start_time = temp->end_time;
                        prv_temp = temp;
                        temp = temp->next;
                        flag = TRUE;
                    }
                    break;

                case EVENT_TYPE_E:
                    /*No change */
                    break;
                case EVENT_TYPE_F:
                    if(temp->next == NULL)
                    {
                        new_temp = (TIME *) malloc(sizeof(TIME));
                        new_temp->start_time = start_time;
                        new_temp->end_time = end_time;
                        temp->next = new_temp;
                        new_temp->next = NULL;
                    }
                    else
                    {
                        prv_temp = temp;
                        temp = temp->next;
                        flag =TRUE;
                    }
                    break;
                default:
                    break;
            }
        }
    }
    return;
}
EVENT_TYPE check_event_type(int old_start,int old_end,int new_start,int new_end)
{
    EVENT_TYPE event_type;

    if(new_start < old_start)
    {
        if(new_end < old_start)
        {
            event_type = EVENT_TYPE_A;
        }
        else if((new_end >= old_start) && (new_end < old_end))
        {
            event_type = EVENT_TYPE_B;
        }
        else
        {
            event_type = EVENT_TYPE_C;
        }
    }
    else if((new_start >= old_start) && (new_start < old_end))
    {
        if(new_end >= old_end)
        {
            event_type = EVENT_TYPE_D;
        }
        else
        {
            event_type = EVENT_TYPE_E;
        }
    }
    else
    {
        event_type = EVENT_TYPE_F;
    }
    return event_type;
}
void print_free_slots(TIME *root,int duration)
{
    int start_time = 0;
    while(root!=NULL)
    {
        if((root->start_time - start_time)>=duration)
        {
            printf("%02d %02d %02d %02d\n",start_time/60,start_time%60,(root->start_time/60)%24,root->start_time%60);
        }
        start_time = root->end_time;
        root = root->next;
    }
    if(start_time != MAX_TIME)
    {
        if((MAX_TIME - start_time)>=duration)
        {
            printf("%02d %02d %02d %02d\n",start_time/60,start_time%60,(MAX_TIME/60)%24,MAX_TIME%60);
        }
    }
    return;
}

#if DEBUG           
void print_link (TIME * root)
{

    while(root !=NULL)
    {
            printf("%02d %02d %02d %02d\n",root->start_time/60,root->start_time%60,root->end_time/60,root->end_time%60);
    root= root->next;
    }
    printf("\n");

}
#endif