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

Given a 2–d matrix , which has only 1’s and 0’s in it. Find the total number of connected sets in that matrix.

Explanation:

Connected set can be defined as group of cell(s) which has 1 mentioned on it and have at least one other cell in that set with which they share the neighbor relationship. A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it. Neighbors can be defined as all the cells adjacent to the given cell in 8 possible directions ( i.e N , W , E , S , NE , NW , SE , SW direction ). A cell is not a neighbor of itself.

/*CODE*/

#include<stdio.h>
#define SIZE 1010
void disable_connected(int i, int j);
int matrix[SIZE][SIZE]={0};

main()
{
int t,size,i,j,k,num_connected=0;

    scanf("%d",&t);
    while(t)
    {
        t--;
        num_connected = 0;
        scanf("%d",&size);
        for(i=0;i<=size+1;i++)
        {
            matrix[0][i] = matrix[size+1][i]= matrix[i][0] = matrix [i][size+1] = 0;
        }
        for(i=1;i<=size;i++)
        {
            for(j=1;j<=size;j++)
            {
                scanf("%d",&matrix[i][j]);
            }
        }

        for(i=1;i<=size;i++)
        {
            for(j=0;j<=size;j++)   
            {
                if(matrix[i][j] == 1)
                {
                    disable_connected(i,j);
                    num_connected++;
                }
            }
        }
        printf("%d\n",num_connected);
    }

return 0;
}

void disable_connected(int i, int j)
{
int p,q;
       
    matrix[i][j] = 2;
    for(p=i-1;p<=i+1;p++)
    {
        for(q=j-1;q<=j+1;q++)
        {
            if(matrix[p][q] == 1)
            {
                matrix[p][q] =2;
                disable_connected(p,q);
            }
        }
    }

return ;
}