C Program to delete the node in the linked list where you will be given the node to delete but not the head pointer .

1->2->3->4->5->6->7->NULL

Consider the above linked list and you are given the node 4 and you have to delete that node . In this scenario you don't have the head pointer . At some point you might think that this is not possible . Because we need to make its previous node 3 to point it to the node 5  like this      1->2->3->5->6->7->NULL and you dont have reference to node 3 . Think about it .......

Is there any way to do it !!! ??? Yes there is a way to do it .

Steps are given below .

1. You have reference to node 4 and you can traverse nodes 5,6,7 . Now copy the data from node 5 and store it in node 4 . So it will become

1->2->3->5->5->6->7->NULL . 

2.Now delete the 5th node . you have its previous node and next node . so deleting will be simple .

1->2->3->5->6->7->NULL.

But there is an Exception 

Deleting the last node is not possible .If the linked list is 1->2->3->4->NULL and if you want to delete 4th node its not possible .

Code :(in C)

Please let me know if you have any questions .

Iterative code for Inorder Traversal in C - Binary Tree

Iterative code for inorder traversal uses Stack to print the tree in inorder. The idea behind this code is to push the elements into stack , popping and printing it . 

Steps are given below 

     1. Get the root element and left side children and push it into stack .

     2. Pop the element from stack , print it and check whether is has right child or not . If it has push right child and its left children into stack . 

     3. Continue step 2 until there is no element in stack . 

For the above diagram inorder traversal is 

1 2 3 4 5 6 7 

Code :(in C)

Please let me know if you have any questions . 

Simple C Program to get the kth node from last in a linked list

This can be done in single traversal using two pointers . First move to the kth node from first and point it using temp pointer . Point the head node using another pointer called kthnodefromlast .Now Move the temp pointer and kthnodefromlast to next node till temp node reaches the end of the linked list.

Example:

 1->2->3->4->5->6->7->NULL

 For the above linked list kth(k=3) node from last is 5.

 Code:(in C)
Time Complexity : O(n)
Space Complexity: O(1)

 Please let me know if you have any questions .

C Program to swap kth node from first and kth node from last in a Linked List

Consider you have the following linked list and you want to swap second node from first and second node from last .

The steps are given below .

     1)Get the size of the linked list . If the size is less than k you can't swap the element . And in the above linked list if k value is 3 you dont need to swap the element .
     2)The two pointers kthnodefromfirst and kthnodefromlast used to point the nodes that we need to swap and its previous nodes are pointed using previous1,previous2.
     3)swap the two nodes . And while swapping you need to check whether you are swapping the head or not . Its one of the important test case .

Code:(in C)

Time Complexity : O(n)
Space Complexity: O(1)

Please let me know if you have any questions .

Simple C Program to check whether the given Binary Tree is Binary Search Tree or not

This can be done in many ways . The simplest way is by using the Inorder Traversal . If we traverse a binary search tree using inorder traversal all the elements are in sorted order .

For the above binary search tree Inorder traversal is

 1  2  3  4  5  6  7

In the following code flag is used like a boolean varible . In the Inorder traversal if the elements are not in sorted order flag is set to 0 . The variable 'min' is used to store the previous value in inorder traversal . Initially it is assigned to the mininum integer value possible which is -32768.

Code :(in C)

Please let me know if you have any questions .

Find an element in a sorted 2D array using saddleback search in C

Consider the following sorted 2D array and you want to find an element .
1  2  3
4  6  9
7  8  10

Rows and columns are sorted and assume that its elements are unique . if u want to find an element ,the simplest and easiest approach is to use saddleback search algorithm . This algorithm starts searching from first row last element . If the value is less than the element that you are searching move left otherwise move down . Continue this step until you find the element .

Example.

1) Start from the first row last element(3) .
2) Consider you want to find the element k=8 . It is bigger than 3 , so go down to the second row last element 9.
3) K=8 value is less than 9 . so move left and check boundary condition . Element here is 6 which is less than k . so again move down and check boudary condition .
4) Now the k value is found .

Code:(in C)

Please let me know if you have any questions .

Program to print last 10 lines of a file in Java

There are two ways to print the last 10 lines of a file.
            1.Go through the file and count the number of lines in that file . Lets say a file contains 100 lines. Read the file again and print the lines from 91 to 100 . Here you need to traverse the file two times .
            2.Create a string array to store the latest 10 lines when you are reading the file and print last 10 lines finally. Second method is given below .

Code : (in JAVA)
Please let me know if you have any questions .

C Program to Print level order traversal of a binary tree using queue.

To print the level order traversal of the tree we need to use Queue .For the above binary tree in the diagram level order traversal is ABCDEFG .
Solution is very simple . The steps are
1.Add root node to the queue using enqueue function
2.Get a node from queue using dequeue function and print it . If the node has children add it to the queue (enqueue)
3.Continue the step 2 until the queue is empty.

Assume that enqueue(node) funtion adds node into queue and dequeue() function deletes the node from the queue and returns node.And dequeue() function returns null when there is no node in the queue .

Code: (in C)

For the above tree execution will be
in queue : A             output:
in queue : BC           output:A
in queue : CDE         output:AB
in queue : DEFG       output:ABC
in queue : EFG         output:ABCD
in queue : FG           output:ABCDE
in queue : G             output:ABCDEF
in queue :                output:ABCDEFG

Please let me know if u have any questions .

C program to print first n fibonacci numbers

Fibonacci series is formed by adding two of its previous numbers .The first 2 fibonacci numbers are 0 and 1 . Series 0,1,1,2,3,5,8... is an example of fibonacci series .

Input   : 7
Output: 0 1 1 2 3 5 8

Code: (in C)

Please let me know if you have any questions .

Amazon question - Schedule a meeting based on given work timings

Consider the following input and output . In the input, first line contains number of input 5 and the time you need to schedule (120 minutes) . Next five lines contains the work timings of that person , so he is busy at these times . And the output shows the list of available timings. This question is asked by amazon in interviewstreet.com . First the timings are sorted using bubble sort based on start time .And you need to compare timings to get the available timings .

Sample Input:
5 120
16 00 17 00
10 30 14 30
20 45 22 15
10 00 13 15
09 00 11 00

Sample Output:
00 00 09 00
17 00 20 45

Code: (in JAVA)

Please let me know if you have any questions .

Simple Recursive Program to find factorial of a given number in C

Finding factorial of a given number is very easy . Recursive code is given below . Consider you are passing a value 5 to this function .
so its execution will be
5*factorial(4)
5*4*factorial(3)
5*4*3*factorial(2)
5*4*3*2*factorial(1)
5*4*3*2*1
=120

Code: (in C)

Please let me know if u have any questions .

Simple C Program to solve n queens problem

This can be solved using using backtracking algorithm . It is almost same like sudoku solving . Every row in NxN matrix should be filled with queen and it should satisfy the following condition .One Queen should not interfere another queen in the matrix . 

Code: (in C)

In the above code checkColumn checks the column to find whether the column already has a queen or not and checkDiagonal is used to check the diagonal elements and it is not implemented here.

Please let me know if u have any questions .. 

Simple C Program to solve sudoku game using backtracking

Sudoku can be solved by using backtracking algorithm . As said, "Backtracking is a refinement of the brute force approach, which systematically searches for a solution to a problem among all available options".

Consider you are passing 9x9 matrix to a function called solve().  If the position is filled already no need to worry to about that and fill the empty places . Check every position in the matrix and when you encounter an empty position fill the appropriate value from 1-9  . Before filling the value in the empty position it's corresponding row , column and 3x3 box should not contain the same value . If the row,column and box doesn't contain the value (let's say 1) , 1 will be filled to that position and you can move to next empty position . Remember this can be backtracked and value can be changed (In future if 1 is not suitable backtrack and change it to value from 2-9 which is suitable) .  

Code :(in C)

//call this function to solve sudoku(solve(0,0)) . Here array is global.

void solve( int row, int col)

   {   int num;

       if( row > 8 )

         {   display();

              exit(0);

         }

      if( array[row][col] != 0 )

          next( row, col ) ;

      else

      {

          for( num = 1; num < 10; num++ )

          {

              if( checkRow(row,num) && checkCol(col,num) && checkBox(row,col,num) )

              {

                     array[row][col] = num ;

                      next( row, col ) ;

              }

         }

        array[row][col] = 0 ;

      }

   }

void next( int row, int col )

   {

      if( col < 8 )

         solve( row, col + 1 ) ;

      else

         solve( row + 1, 0 ) ;

   }

int checkRow( int row, int num )

   {

      int col;

      for( col = 0; col < 9; col++ )

         if( array[row][col] == num )

            return 0;

      return 1;

   }

  int  checkCol( int col, int num )

   {  int row;

      for(row = 0; row < 9; row++ )

         if( array[row][col] == num )

            return 0;

      return 1;

   }

 int checkBox( int row, int col, int num )

   {  int r,c;

      row = (row / 3) * 3 ;

      col = (col / 3) * 3 ;

      for(r = 0; r < 3; r++ )

         for(c = 0; c < 3; c++ )

            if( array[row+r][col+c] == num )

                return 0;

      return 1;

   }

Please let me know if you have any questions or doubts . 

Amazon question-Program to Find the number of connected graphs in the given matrix

consider the following diagram.

if the adjacent position is 1 we can traverse through that element and we can form a graph.So the number of graphs that we can form is 2.The solution for this question is very simple . Check every element in the matrix and if the element is 1 increase the count by 1 and change its connected elements (or nodes) to 0 .

Code: (in C)

int find_no_of_graphs(int** array,int rows,int cols)
{
    int i,j,count=0;
    for(i=0;i < m;i++)
   {
            for(j=0;j < n;j++)
           {
                 if(array[i][j]==1)
                {
                       //if the element is 1 increment the graph count and set it's connected elements to 0.
                         find_connected_positions(array,i,j);
count++;
                  }
              }
       }
     return count;
}

void find_connected_positions(int** array,int i,int j,int rows ,int cols)
{
      array[i][j]=0;
      if(i-1>=0)
     {
if(array[i-1][j]==1)
find_connected_positions(array,i-1,j,rows,cols);
if(j-1>=0)
{
if(array[i-1][j-1]==1)
find_connected_positions(array,i-1,j-1,rows,cols);
}
if(j+1 < cols)
{
if(array[i-1][j+1]==1)
find_connected_positions(array,i-1,j+1,rows,cols);
}
       }
    if(i+1 < rows)
   {
if(array[i+1][j]==1)
find_connected_positions(array,i+1,j,rows,cols);
if(j-1>=0)
{
if(array[i+1][j-1]==1)
find_connected_positions(array,i+1,j-1,rows,cols);
}
if(j+1 < cols)
{
if(array[i+1][j+1]==1)
find_connected_positions(array,i+1,j+1,rows,cols);
}
       }
     if(j-1>=0)
     {
if(array[i][j-1]==1)
find_connected_positions(array,i,j-1,rows,cols);
       }
      if(j+1 < cols)
     {
if(array[i][j+1]==1)
find_connected_positions(array,i,j+1,rows,cols);
       }
}

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

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.