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 .