Reverse the String in such a way that if the input is 'i am the best' output should be 'best the am i'.

This question was asked to me in Athena Health Interview . The solution is same as rotate array by k times .

Steps:

1. reverse the whole string (tseb eht ma i).
2. reverse the strings separated by space (best the am i).

Assume that isspace() funtion looks like this
int isspace(char ch)
{
   // ascii value of space is 32
     if((int)ch==32)
        return 1;
     return 0;
}

Code:(in C)

void reverse(char* str)
{
int length=strlen(str);
if(length < 2 )
return;
reverse_string(str,0,length-1);
int temp=0,first,last;
while(true)
{
while(isspace(str[temp]))
temp++;
if(str[temp]=='/0')
break;
first=temp;
while(! isspace(str[temp]) && str[temp]!='/0')
temp++;
last=temp-1;
if(first < last) 
reverse_string(str,first,last);
}
}

void reverse_string(char *str,int first,int last)
{
char temp;
while(first < last )
        {
temp=str[first];
str[first]=str[last];
str[last]=temp;
}
}

Please let me know if there is any bug in the above code and your suggestions are always welcome .

Simple C Program to check if the given linked list is palindrome

Consider the following linked list

a->b->c->c->b->a->null is palindrome .
there are two ways to find out whether the given linked list is a palindrome or not

1. Use stack . push the first half of the linked list into stack and pop elements from stack & check it with the second half .But it needs extra space.

2. Reverse the second half of the linked list .so it will become a->b->c->a->b->c->null .Compare the first half with the second half . Here u need to find the length of the linked list and reverse of linked list .Its already posted in this site. That's of the beauty of writing functions . U can reuse it whenever u want . Refer it here if u want
i)  Length of the linked list
ii) Code to reverse the linked list .

Code: (in C)

int check_palindrome(struct node* head)
{
int length=size_of_linkedlist(head),middle;
if(length < 2)
return 1;
struct node* first_half=head,second_half=head,reversed_second_half,temp;

  // find the middle element and move the second_half pointer to second half
if(length%2==0)
middle=length/2+1;
else
middle=length/2+2;
while(--middle!=0)
second_half=second_half->link;

//reverse the second half of the linked list
temp=reversed_second_half=reverse(second_half);

//compare first half and second half
while(temp!=null)
{
if(temp->data != first_half->data)
{
second_half=reverse(reversed_second_half);
return 0;
}
temp=temp->link;
}

//reverse again the second half so that original list wont be changed .
second_half=reverse(reversed_second_half);
return 1;
}

Please let me know if there is any bug in the above code and your suggestions are always welcome .

Simple recursive code to find the size of linked list and binary tree

Finding the size of the linked list and binary tree is very easy using recursion . U just need to traverse every node and increment count.

Code: (in  C)

Size of Linked list:

int size_of_linkedlist(struct node* node)
{
if(node==null)
return 0;
return 1+size_of_linkedlist(node->link);
}

Size of Binary tree:

int size_of_binarytree(struct node* node)
{
if(node==null)
return 0;
return 1+size_of_binarytree(node->left)+size_of_binarytree(node->right);
}

Please let me know if u find any bug in above code and your suggestions are always welcome .

A Simple C Code for Binary Tree Traversal

Three traversal methods
     i)   preorder traversal
     ii)  inorder traversal
     iii) postorder traversal

This post may seem very simple . But to solve the problems related to binary trees you should have clear understanding of these traversals . For an example ,creating mirror image of the tree depends on postorder traversal .
Consider the following tree

 Preorder  :  A B C D E F G
 Inorder   :   C B D A F E G
 Postorder : C D B F G E A

 Code :(in C)

 Preorder Traversal :

 void preorder_traversal(struct node * node)
 {
if(node!=null)
{
printf("%d ",node->data);
preorder_traversal(node->left);
preorder_traversal(node->right);
}
 }

 Inorder Traversal :

 void inorder_traversal(struct node * node)
 {
if(node!=null)
{
inorder_traversal(node->left);
printf("%d ",node->data);
inorder_traversal(node->right);
}
 }

 Postorder Traversal :

 void postorder_traversal(struct node * node)
 {
if(node!=null)
{
postorder_traversal(node->left);
postorder_traversal(node->right);
printf("%d ",node->data);
}
 }

Please let me know if there is any bug in the above code and your suggestions are always welcome .

C Program to Rotate array by k times

Lets assume you have array of n=7 elements . And if u rotate it by k=3 times the input and output will be
I/P :  1 2 3 4 5 6 7
O/P: 5 6 7 1 2 3 4

This can be done in 3 steps.

Steps are:
i) reverse the whole array  ( 7 6 5 4 3 2 1 ).
ii)reverse first k elements ( 5 6 7 4 3 2 1 ).
ii)reverse the remaining n-k elements (5 6 7 1 2 3 4).

Note : And here's the thing. You have the reverse module in common .So write it as a separate function  ( modularity ) and it can be reused ( reusability ) . And if k is greater than we don't need to rotate it k times. For an example if u rotate the array by 7 times the output will be 1 2 3 4 5 6 7 (same as input) . so if k is 9 it is equal to rotating array by 2 times.

Code : (in C) 

void rotate_array(int* array,int n,int k)
{
if(n < 1 || k < 1)
return ;
if(k > n)
k=k%n;
reverse_array(array,0,n-1);
reverse_array(array,0,k-1);
reverse_array(array,k,n-1);
}

void reverse_array(int* array,int first,int last)
{
if(first>=last)
return;
int temp;
while(first < last)
{
temp=array[first];
array[first]=array[last];
array[last]=temp;
first++;
last--;
}
}

Please let me know if there is any bug in the above code and your suggestions are always welcome .

C Program to Rotate 2D array by 90 degrees

This concept is used in rotating images .Rotating array by 180 degree is very easy .
For an example if the array is (let's assume 5x5 array)
1   2   3   4   5
6   7   8   9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

and if we rotate it by 180 degrees it will look like
21 22 23 24 25
16 17 18 19 20
11 12 13 14 15
6   7   8   9  10
1   2   3   4   5

we can acheieve it by swapping first row and last row , second row and fourth row.
But to achieve 90 degree rotation the steps are
 i) rotate array by 180 degrees first .
 ii)for every element(i,j) in 2D matrix , if i < j swap (i,j) and (j,i) .
So the output will be 90 degrees rotated
 21 16 11 6   1
 22 17 12 7   2
 23 18 13 8   3
 24 19 14 9   4
 25 20 15 10 5

 Note :Here we are doing it in place.This will work only if m and n are same. otherwise we need to create a new array of size nxm .

 Code : (in C)

  void rotate90Degrees(int **array,int m ,int n)  // mxn matrix
 {
     int i,j,rows=m-1,temp;
 
     //rotate array by 180 degrees
     for(i=0;i<=rows/2;i++)
     {
if(rows<=i)
break;
for(j=0;j < n;j++)
{
temp=array[i][j];
array[i][j]=array[rows][j];
array[rows][j]=temp;
}
rows--;
       }
 
      //swap elements to rotate array by 90 degrees
      for(i=0;i < m;i++)
     {
for(j=0;j < n;j++)
{
if(i < j)
{
temp=array[i][j];
array[i][j]=array[j][i];
array[j][i]=temp;
}
               }
       }
 }

Please let me know if there is any bug in the above code and your suggestions are always welcome .

Program to Check whether the given string is palindrome or not .

There are two ways . One method is by using stack and second method is by comparing characters 1,n(length of the string) and 2,n-1 and so. For first method space complexity is O(n) . But for the second method  space complexity is O(1) .So it is better to use the second method. And the time complexity for both method is O(n)

Code: (in C)
int is_palindrome(char *str)
{
          if(str==NULL)
                  return 0;
          int len = strlen(str),i=0,j=len-1;
          while (i  < j)
          {
                 if(str[i]!=str[j])
                       return 0;
                 i++;
                 j--;
            }
           return 1;
}

Input   :  ababa
Output : 1

Please let me know if there is any bug in the above code and your suggestions are always welcome .

Program to Segregate odd and even nodes in linked list .

Here odd element doesn't mean that the element in the odd position . If the data is odd , it is odd element . To segregate odd and even nodes the algorithm is given below . The simplest and easiest approach is to create two linked list and when you traverse odd element node add it to odd list and add even element nodes to Even list . Otherwise you need to change links and push even nodes to the end . However that's not a good idea .

Code: (in C)

struct node* segregate_odd_and_even_nodes(struct node* head)
{
  if(head==null)
return null;
struct node* head1=null,tail1=null,head2=null,tail2=null,node=head;
while(node!=null)
{
if(node->data%2!=0)
{
if(head1==null)
{
head1=node;
tail1=node;
}
else
{
tail1->link=node;
tail1=node;
}
}
else
{
if(head2==null)
{
head2=node;
tail2=node;
}
else
{
tail2->link=node;
tail2=node;
}
}
node=node->link;
}
if(tail1!=null)
tail1->link=head2;
if(tail2!=null)
tail2->link=null;
    if(head1!=null)
            return head1;
    else
            return head2;
}

Input:      2->3->1->4->NULL
Output:    3->1->2->4->NULL
So the odd nodes will always come first in the output .

Please let me know if there is any bug in the above code and your suggestions are always welcome .

Simple C Program to Find Loop in the Linked List

This is a famous question asked in many interviews . And you probably know the answer . The Idea to solve this problem is to use two pointers, where one pointers moves by one pointer and another pointer moves by two pointers . The general idea is if two people are running in  a circle if one person is running at 1x speed and another one is running at 2x speed they will meet after 2 rounds(person who is running at 1x speed will complete one round where other one completes 2 rounds ).

Code : (in C)
int detect_loop(struct node * head)
{
if(head==null && head->link==null)
return 0;
struct node* first,second;
first=head;
second=head->link;
while(first!=second)
{
first=first->link;
if(second->link==null || second->link->link==null)
return 0;
second=second->link->link;
}
if(first==second) // found the loop
return 1;
return 0;
}

if the function returns 0 that means there is no loop , otherwise there is a loop in the linked list .

please let me know if there is any bug in the above code.