Friday, 22 September 2017

C Program to Convert Infix Expression into Postfix

C Program to convert infix expression into postfix expression along with algorithm is given below.


ALGORITHM:

1. For i in range 0 to length(string)-1:
2.       If the scanned operator is character then output it.
3.       else:
3.1          If the precedence of the scanned operator is greater than the 
             precedence of the operator in the stack(or the stack is empty),
             push it.
3.2          Else, Pop the operator from the stack until the precedence of 
             the scanned operator is less-equal to the precedence of the operator 
             residing on the top of the stack. Push the scanned operator to the 
             stack.
4.       If scanned character is '(' Push it to stack.
5.       If the scanned character is an ‘)’, pop and output from the stack 
         until an ‘(‘ is encountered.
6.       Repeat the steps 2 to 6 until the infix expression is scanned.
7.       Pop out the stack and output it.


PROGRAM:

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std; 
int Prec(char ch)
{
   switch(ch)
   {
        case '+':
        case '-':
               return 1;
        case '*':
        case '/':
               return 2;
        case '^':
               return 3;
   }
   return -1;
}
bool check_precedence(char ch,stack<char> &st)
{
      if(st.empty())
      {
           return true;
      }
      if(st.top()=='(')
      {
          return true;
      }
   int pre_ch=Prec(ch);
   int pre_st=Prec(st.top());
   if(pre_ch<=pre_st)
   {
       return false;
   }
   else
   {
       return true;
   }

}
string infixtopostfix(string s)
{
   std::stack<char> st;
   string s2="";
   for(int i=0;i<s.size();i++)
   {
         if((s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z'))
         {
                 s2=s2+s[i];
         }
         else if(s[i]=='(')
         {
               st.push(s[i]);
         }
         else if(s[i]==')')
         {
               while(st.top()!='(')
               {
                        s2=s2+st.top();
                        st.pop();
               }
               st.pop();
         }
         else
         {
                bool result=check_precedence(s[i],st);
                if(result)
                {
                     st.push(s[i]);
                }
                else
                {
                     while(!check_precedence(s[i],st))
                     {
                           s2=s2+st.top();
                           st.pop();
                     }
                     st.push(s[i]);
                }
         }
   }
   while(!st.empty())
   {
       s2=s2+st.top();
       st.pop();
   }
   return s2;
}
int main()
{
   int t;
   cout<<"\n\nEnter the number of test cases:\n";
   cin>>t;
   while(t--)
   {
        std::string s;
        cout<<"\n\nEnter the string:\n";
        cin>>s;
        string result=infixtopostfix(s);
        cout<<"\nThe postfix expression is: \n";
        cout<<result;
        cout<<"\n";
   }
   return 0;
}


OUTPUT:




Wednesday, 20 September 2017

Difference Between Functional Testing and Non-Functional Testing

Functional Testing:

1.  In functional testing tester tests that how well the system performs.
2.  Functional testing is based on client requirements.
3.  In functional testing we test the application against the business requirements.
4.  Functional testing validates the behavior of an application
5.  Functional testing covers Unit testing, Integration testing, Sanity testing, Smoke testing, Regression testing and so on.
6. Functional testing means how your system performs.
7. Functional testing always concentrates on customer requirements.
8. It is a part of System testing.

Non-Functional Testing:

1. In Non- Functional testing tester tests that how well the system responds.
2. Non-Functional testing is based on client expectations.
3. Non-Functional testing refers to test the application against client and performance requirements.
4. It validates the performance of application.
5. This testing covers Load/Performance Testing, Stress/Volume Testing, Security Testing and installation testing and so on.
6. It means how your well your system is doing example performance and Stress testing.
7. Non-Functional testing always concentrates on customer expectations.
8. It is also a part of System testing.

Tuesday, 29 August 2017

DFS Implementation in Python

Depth First Search (DFS) algorithm is used to traverse a graph depthward motion. DFS Algorithm use data structure stack to remember to get the next vertex to start the search and we will requred an array to keep the track of vertex that it is visited or unvisited.



In DFS traversal we look start from the sorce, then we look for the adjacent unvisited vertices of the source. We display them, mark them visited and put them into the stack. If there is not remain any adjacent vertex which is unvisited. Then, we popped out the top element of the stack and do the same for the popped out element. We will repeat the same till the stack becomes empty.

Algorithm:


1. Display the source vertex and mark it as visited.
2. push the sourve vertex to the STACK
3. do While STACK is not empty:
4.      set: source=STACK.top()
5.      Update Stack by pop out top element of stack
6.    do For i=1 to n:
7.     If graph_matrix[source][i]=1 and vertex_status[i]=unvisited:
8.                    Display vertex 'i' and mark it as visited
9.                    Push the vertex 'i' to the STACK
10.    EndFor
11. EndWhile


PROGRAM:

from collections import defaultdict

class graph:
 def __init__(self):
  self.graph=defaultdict(list)

 def add_edge(self,u,v):
  self.graph[u].append(v)
  self.graph[v].append(u)

 def DFS(self,s):
  stack=[]
  visited=[False for i in range(len(self.graph))]
  visited[s]=True
  stack.append(s);
  while stack:
   source=stack.pop()
   print(source,end=' ')
   for j in self.graph[source]:
    if visited[j]==False:
     stack.append(j);
     visited[j]=True

g=graph()
g.add_edge(0,1)
g.add_edge(0,2)
g.add_edge(1,3)
g.add_edge(2,3)
g.add_edge(3,4)
g.add_edge(4,5)
print("\n\n\nThe DFS traversal of the Graph is:\n\n")
g.DFS(1)
print("\n\n")


OUTPUT:



Friday, 18 August 2017

BFS Implementation in Python

Breadth First Search (BFS) algorithm is used to traverse a graph in a breadth ward motion. BFS Algorithm use data structure queue to remember to get the next vertex to start the search and we will required an array to keep the track of vertex that it is visited or unvisited. Implementation of BFS algorithm with example is given below.





In BFS traversal we start the source vertex, display and mark it as visited and look for its adjacent vertices which are unvisited, display them and mark them visited and put them in the queue. If we  not found any adjacent vertex to the source node which is unvisited then, we pop out the first element of queue and do the same thing for the popped element. This steps will be repeated until the queue becomes empty.

PROGRAM:

from collections import defaultdict

class graph:
 def __init__(self):
  self.graph=defaultdict(list)

 def addedge(self,u,v):
  self.graph[u].append(v)
  self.graph[v].append(u)

 def BFS(self,s):
  queue=[]
  visited=[False for i in range(len(self.graph))]
  queue.append(s)
  visited[s]=True
  while queue:
   source=queue.pop(0)
   print(source,end=' ')
   for i in self.graph[source]:
    if visited[i]==False:
     queue.append(i)
     visited[i]=True
     
g=graph()
g.addedge(0, 1)
g.addedge(0, 2)
g.addedge(1, 3)
g.addedge(2, 3)
g.addedge(3, 4)
g.addedge(4, 5)
print("\n\nThe BFS traversal of the above graph is:\n\n")
g.BFS(1)
print("\n\n")



OUTPUT:



Tuesday, 25 July 2017

C++ Program to find the level of the target Node in Binary Tree

C++ Program to find the level of the target node in a binary tree is given below. Approach is simple we will do the Breadth First Search traversal of the binary tree by using and keep the track of  the level. If we found the level of the target node then we will return its level otherwise we will return -1 i.e the target node is not present in the given binary tree.

PROGRAM:

#include <stdio.h>
#include <queue>
#include <stdlib.h>
struct node{
 int data;
 struct node *left;
 struct node *right;
};
int  getLevel(struct node *root,int target)
{
   std::queue<node*> q;
   if(root==NULL)
   {
       return -1;
   }
   q.push(root);
   q.push(NULL); //NULL is pushed to identify that the current level is completed
   int level=1;
   while(!q.empty())
   {
       struct node *temp=q.front();
       q.pop();
       if(temp==NULL)
       {
              q.push(NULL); 
              level+=1;   //we completed searching in current level so incrementing level
       }
       else
       {
             if(temp->data==target)
             {
                return level;
             }
             if(temp->left!=NULL)
             {
                q.push(temp->left);
             }
             if(temp->right!=NULL)
             {
                q.push(temp->right);
             }
       }
   }
   return -1;
}
int main()
{


       /*  Generating a binary tree

                                     5
                                   /   \
                                  /     \
                                 8       34
                                / \        
                               /   \
                             10     15
       */


    struct node *root;
    root=(struct node*)malloc(sizeof(struct node));
    root->data=5;
    root->left=(struct node*)malloc(sizeof(struct node));
    root->left->data=8;
    root->left->left=(struct node*)malloc(sizeof(struct node));
    root->left->left->data=10;
    root->left->left->left=root->left->left->right=NULL;
    root->left->right=(struct node*)malloc(sizeof(struct node));
    root->left->right->data=15;
    root->left->right->left=root->left->right->right=NULL;

    
    root->right=(struct node*)malloc(sizeof(struct node));
    root->right->data=34;
    root->right->left=root->right->right=NULL;

       int target;
    printf("\n\nEnter the element to find its level: \n");
    scanf("%d",&target);
    int result=getLevel(root,target);
    if(result==-1)
    {
         printf("\n\nThe target element is not present in Binary Tree:\n");
    }
    else
    {
         printf("\n\nThe level of the target element is: %d\n\n",result);
    }
    return 0;
}


OUTPUT:




C Program to Check if a Binary Tree is a Balanced Tree or not

A binary tree will be balanced tree if its both left subtree and right subtree is balanced i.e The difference between the height of left subtree and right subtree should not be more than 1. C program to check if a given binary tree is balanced or not is given below.

Ex: 1
                      A
                    /    \
                C        D
                            \
                             E

    This tree is a balanced tree, because the  height difference between  left subtree and right subtree of 'A'  is not more than one.
       
         The height difference between left subtree and right subtree of C is not more than 1 and same with the subtrees of D as well as E.

Ex: 2

                      A
                    /     \
                 B        C
                          /
                        D
                       /
                     E

        the above tree is not a balanced tree because height difference between left subtree and right subtree of C is more than 1.

PROGRAM:


#include <stdio.h>
#include <stdlib.h>
struct node{
 int data;
 struct node *left;
 struct node *right;
};
bool isBalanced(struct node *root);
int findheight(struct node *root)
{
     int lefth=0,righth=0;
     if(root==NULL)
     {
         return 0;
     }
     lefth=findheight(root->left);
     righth=findheight(root->right);
     if(lefth>righth)
     {
           return lefth+1;
     }
     else
     {
           return righth+1;
     }
}
bool isBalanced(struct node *root)
{
    int left_height,right_height;
    if(root==NULL)
    {
         return true;
    }
    left_height=findheight(root->left);
    right_height=findheight(root->right);
    if(abs(left_height-right_height)<=1 && isBalanced(root->left) && isBalanced(root->right))
    {
            return true;
    }
    return false;
}
int main()
{


       /*  Generating a binary tree

                                     5
                                   /   \
                                  /     \
                                 8       34
                                / \        
                               /   \
                             10     15
       */


    struct node *root;
    root=(struct node*)malloc(sizeof(struct node));
    root->data=5;
    root->left=(struct node*)malloc(sizeof(struct node));
    root->left->data=8;
    root->left->left=(struct node*)malloc(sizeof(struct node));
    root->left->left->data=10;
    root->left->left->left=root->left->left->right=NULL;
    root->left->right=(struct node*)malloc(sizeof(struct node));
    root->left->right->data=15;
    root->left->right->left=root->left->right->right=NULL;

    
    root->right=(struct node*)malloc(sizeof(struct node));
    root->right->data=34;
    root->right->left=root->right->right=NULL;


    if(isBalanced(root))
    {
          printf("\n\n\nThe above given tree is a Balanced Tree\n\n\n");
    }
    else
    {
          printf("\n\n\nThe above given tree is not a Balanced Tree\n\n\n");
    }
    return 0;
}


OUTPUT:



Thursday, 29 June 2017

C++ Program to detect a cycle in Directed Graph

C++ Program to detect a cycle in directed graph is given below. Approach is simple, we will do DFS traversal of graph from each vertex (which will be source) and look if there is any back edge to the source during traversal. If there is any back edge then it means there is cycle in  the graph otherwise there is not any cycle.


ALGORITHM

#include <list>
#include <stack>
#include <iostream>
#define V 6
using namespace std;


class detectCycle_DirectedGraph{
     
     std::list<int> adj[V];
     public:
         void get_data();
         bool isCyclic();

};
void detectCycle_DirectedGraph::get_data()
{
    
    /* Let there are 6 vertices total from 1 to 6
       and given edges are
       1--->2
       1--->4
       2--->3
       3--->1
       3--->6
       6--->5
       5--->4

   */

   adj[0].push_back(1);
   adj[0].push_back(3);
   adj[1].push_back(2);
   adj[2].push_back(5);
   adj[2].push_back(0);
   adj[5].push_back(4);
   adj[4].push_back(3);
}
bool detectCycle_DirectedGraph::isCyclic()
{
   bool visited[V];
      std::stack<int> s;
      std::list<int>::iterator it;
      for(int i=1;i<=V;i++)
      {
             for(int j=0;j<V;j++)
             {
                   visited[j]=false;
             }
             visited[i]=true;
             s.push(i);
             int flag=0;
             while(!s.empty())
             {
                  int source=s.top();
                  s.pop();
                  for(it=adj[source].begin();it!=adj[source].end();it++)
                  {
                      if(*it==i)
                      {
                          /*If the traversing node is equal to current source vertex
                            which means there is a cycle */

                          return true;
                      }
                      if(visited[*it]==false)
                      {
                          s.push(*it);
                          visited[*it]=true;
                      }
                  }
                 
             }
      }
      
      /* If we don't find any cycle during traversal then return false*/
      return false;
}

int main()
{
  detectCycle_DirectedGraph graph;
  graph.get_data();
  if(graph.isCyclic())
  {
        cout<<"\n\nYes There is cycle in graph\n\n";
  }  
  else
  {
        cout<<"\n\nThere is not any cycle in graph\n\n";
  }
}


OUTPUT




Saturday, 24 June 2017

C Program to traverse a matrix in spiral order

C Program to traverse a matrix in spiral order is given below. The program is compiled and checked successfully output is also given below the program.

Example:

A[4][4]= {  1 , 2 , 3 , 4
                   5 , 6 , 7 , 8
                   9 , 10 , 11 , 12
                  13 , 14 , 15 , 16  }

Spiral traversal:    1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10

PROGRAM:

#include<iostream>
using namespace std;
#define M 10
#define N 10

void spiral(int arr[M][N],int m,int n){


    int startrow=0,startcol=0,endrow=n-1,endcol=m-1;

    while(startrow<=endrow && startcol<=endcol)
    {
 
        for(int i=startcol;i<=endcol;i++){
            cout<<arr[startrow][i]<<" ";
        }
        startrow++;

        for(int i=startrow;i<=endrow;i++){
            cout<<arr[i][endcol]<<" ";
        }
        endcol--;

        if(startrow<=endrow){
            for(int i=endcol;i>=startcol;i--){
                cout<<arr[endrow][i]<<" ";
            }
            endrow--;
        }

        if(startcol<=endcol){
            for(int i=endrow;i>=startrow;i--){
                cout<<arr[i][startcol]<<" ";
            }
            startcol++;
        }
    }
}

int main(){
    
    
  

       int m,n;

       cout<<"\nEnter the number or rows and column of the matrix: \n";
       cin>>m>>n;
       int arr[M][N];

       cout<<"\n\nEnter the elements of the matrix: \n\n";
       for(int i=0;i<m;i++)
       {

          for(int j=0;j<n;j++)
          {
            cin>>arr[i][j];
          }
       }
      
      cout<<"\n\nThe spiral traversal of matrix is: \n\n";
      spiral(arr,m,n);
      cout<<"\n";
     
   
     return 0;
}



OUTPUT:




Thursday, 8 June 2017

C++ Program to detect a loop in singly Linked List

Algorithm and the program for detecting any loop inside the singly Linked linked list is given below.
Implementation is simple we will use two pointer. We will increment one pointer by one the other one by two and then check if two pointers are equal or not. If they are equal then linked list has loop inside it otherwise linked list does not contain any loop.

ALGORITHM:
  step 1:     set  node *current1=head
  step 2:     set  node *current2=head
  step 3:     doWhile current1!=NULL && current2!=NULL && current1->next!=NULL:
  step 4:                   current1=current1->next
  step 5:                   current2=current2->next->next
  step 6:                   if(current1==current2):
  step 7:                                return true
  step 8:     endLoop
  step 9:     return false



PROGRAM:

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

struct node{
 int data;
    struct node *next;
};

node* create_newnode(int data);
bool detectLoop(struct node *head);

int main()
{

      /*    Now we are creating the linked list shown below
            with a loop i.e  node 16 is connected back to node 10

            8--> 10--> 12--> 14--> 16
                 ^                 |
                 |                 |
                 -------------------


       */


   struct node *head,*temp;
   head=create_newnode(8);
   head->next=create_newnode(10);
   temp=head->next;
   head->next->next=create_newnode(12);
   head->next->next->next=create_newnode(14);
   head->next->next->next->next=create_newnode(16);
   head->next->next->next->next->next=temp;

      if(detectLoop(head))
      {
             cout<<"\n\nLinked List has loop !\n\n";
      }
      else
      {
             cout<<"\n\nLinked List does not contain loop in\n\n";
      }



      /*  Creating new linked list:
           8--> 10--> 12--> 14--> 16-->NULL

           The linked list shown above does not conatin any loop
      */


      head=create_newnode(8);
   head->next=create_newnode(10);
   head->next->next=create_newnode(12);
   head->next->next->next=create_newnode(14);
   head->next->next->next->next=create_newnode(16);


   if(detectLoop(head))
      {
             cout<<"\n\nLinked List has loop inside it!\n\n";
      }
      else
      {
             cout<<"\n\nLinked List does not has any loop insite it !\n\n";
      }
   
}

node* create_newnode(int data)
{
   
    struct node *newnode;
    newnode=new node();
    newnode->data=data;
    newnode->next=NULL;
    return newnode;

}

bool detectLoop(struct node *head)
{
    
    struct node *current1,*current2;
    current1=head;
    current2=head;
    while(current1!=NULL && current2!=NULL && current2->next!=NULL)
    {
          current1=current1->next;
          current2=current2->next->next;
          if(current1==current2)
          {
                return true;
          }
    }
    return false;
}


OUTPUT:


Wednesday, 7 June 2017

Python Program for Insertion at any position in Singly Linked List

Python program for insertion node at any position in singly linked list is given below. In this program the class LinkedList contains a method insert which will insert the new element at the desired position the program along with output is given.

If you don't know how to create a singly linked list in python then click this link:  Python program to create a singly linked list

PROGRAM:

class Node:
 def __init__(self,data):
  self.data=data
  self.next=None

class LinkedList:
 def __init__(self):
  self.head=None
  self.size=0



 def append(self,data):
  if(self.head==None):
   newnode=Node(data)
   self.head=newnode
  else:
   current=self.head
   while(current.next!=None):
    current=current.next
   current.next=Node(data)
  self.size=self.size+1



 def insert(self,data,position):
  if(position==0):
   newnode=Node(data)
   newnode.next=self.head
   self.head=newnode
  elif(position>self.size):
   print("\n\nIndex is out of range\n\n")
  elif(position==self.size):
   self.append(data)
  else:
   current=self.head
   count=0
   while(current!=None):
    if(count==position-2):
     break
    else:
     count+=1
     current=current.next
   newnode=Node(data)
   newnode.next=current.next
   current.next=newnode


 def printlist(self):
  current=self.head
  while(current!=None):
   print current.data,
   current=current.next
mylinklist=LinkedList()
mylinklist.append(4)
mylinklist.append(5)
mylinklist.append(8)
mylinklist.append(10)
print("\n\nThe linked list before insertion:\n\n")
mylinklist.printlist()
mylinklist.insert(6,3)
print("\n\nThe linked list after insertion:\n\n")
mylinklist.printlist()
mylinklist.insert(10,4)
print("\n\nThe linked list after insertion:\n\n")
mylinklist.printlist()
mylinklist.insert(2,0)
print("\n\nThe linked list after insertion:\n\n")
mylinklist.printlist()
mylinklist.insert(12,8)




OUTPUT:


Tuesday, 6 June 2017

Implementation of Floyd Warshall Algorithm - C++

Floyd Warshall algorithm is used to find the shortest distance between the every pair of vertices in a given weight directed graph which does not contain any cycles of negative length ( The total length of any cycle in the graph should not be negative). The idea is very simple we  will pick all the vertices one by one and include the picked vertex between two every other pair of vertices as an intermediate vertex and update the distance matrix if the distance between the two vertex becomes smaller than before. Implementation of Floyd Warshall algorithm is very simple which is its main advantage. Implementation of Floyd Warshall algorithm in C++ is given below.


Algorithm


step 1:    Initialize Distance matrix i.e.   D(i,j) = adjacency(i,j)
step 2:    do For  k=1 to k=n:
step 3:              do For i=1 to i=n:
step 4:                       do For j=1 to j=n:
step 5:                               if    D[i][k]+D[k][j] < D[i][j]:
step 6:                                      set   D[i][j] = D[i][k]+D[k][j]
step 7:    Exit.




Example: 

                     

The implementation of the floyd warshall algorithm for the above example and its output is given below

Note:  1000 here representing infinity i.e there is not edge between those two vertex.

PROGRAM:

#include <iostream>
#include <stdio.h>
using namespace std;

class graph
{
   int adjacency[10][10],distance[10][10],n,i,j,k;
   public:
        void get_data();
        void floydwarshall();
        void print();
};

void graph::get_data()
{
  printf("\nEnter the total number of vertices: ");
  scanf("%d",&n);
  printf("\nEnter the adjacency matrix (If there is no \nedge betweent two vertex then enter 1000): \n\n");
  for(i=1;i<=n;i++)
  {
       for(j=1;j<=n;j++)
       {
             scanf("%d",&adjacency[i][j]);
       }
  }
}

void graph::floydwarshall()
{
 
   for(i=1;i<=n;i++)
   {
        for(j=1;j<=n;j++)
        {
             distance[i][j]=adjacency[i][j];
        }
   }

   /* Updating distance matrix by taking intermediate vertex 'k'
      between every other vertices pair */

   for(k=1;k<=n;k++)
   {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(distance[i][k]+distance[k][j]<distance[i][j])
                {
                      distance[i][j]=distance[i][k]+distance[k][j];
                }
            }
        }
   }
}
void graph::print()
{
 
  printf("\n\nThe final distance matrix is: \n\n");
  for(i=1;i<=n;i++)
  {
      for(j=1;j<=n;j++)
      {
          printf("%d\t\t",distance[i][j]);
      }
      printf("\n");
  }
}

int main()
{
  graph graph;
  graph.get_data();
  graph.floydwarshall();
  graph.print();
  return 0;
}


OUTPUT:


Saturday, 27 May 2017

C++ Program to find the first Non-repeating character in a string

C++ Program and algorithm to find the first non-repeating character of  a string is given below and this question has been already asked in the interviews of following companies:-

Amazon, Goldman Sachs, DE shaw, MAQ software, MakeMyTrip, Payu, TejasNetwork, OLA, OATS System, Teradata, InfoEdge

Source:  geeksforgeeks

ALGORITHM:

1.  Declare an array arr[256]={0} /*initialize every element to zero */
2.  do For i=1 to len(string):
3.           arr[string[i]]=arr[string[i]]+1
4.  do For i=1 to len(string):
5.           if(arr[string[i]]==1):
6.                      char c=string[i]
7.                      break
8.  print 'c'.


Note:  we are using array of size 256 because we are indexing characters of string using their ASCII value. For more click here


PROGRAM:

#include <iostream>
#include <map>
#include <string.h>
using namespace std;

int main() 
{
 
 
       char string[100];
       int arr[256]={0};
       
          cout<<"\n\nEnter the String:\n\n";
       cin>>string;
       for(int j=0;j<strlen(string);j++)
       {
            arr[string[j]]++;
       }
       char c;
       for(int j=0;j<strlen(string);j++)
       {
            if(arr[string[j]]==1)
            {
                c=string[j];
                break;
            }
       }
       cout<<"\n\n";
       cout<<c<<"\n\n";

       
       return 0;
}


OUTPUT:


C++ Program for reversing an array in O(n) Time

Algorithm and its implementation to reverse an array in O(n) time is given below:

ALGORITHM:


step 1:    set j=0
step 2:    set k=n-1 /*n is the total number of elements in array */
step 3:    do While j<k:
step 4:             set: temp=array[j]
step 5:             set: array[j]=array[k]
step 6:             set: array[k]=temp
step 7:             set: j=j+1
step 8:             set: k=k-1    


PROGRAM:

#include <iostream>
using namespace std;

int main() {
  int t;    /*t is the test cases */
  cin>>t;
  for(int i=0;i<t;i++)
  {
       int n;    /*n is the number of elements */
       cin>>n;
       int arr[n];
       for(int j=0;j<n;j++)
       {
            cin>>arr[j];
       }
       int temp;
       int j=0;
       int k=n-1;
       while(j<k)
       {
           temp=arr[j];
           arr[j]=arr[k];
           arr[k]=temp;
           j++;
           k--;
       }
       cout<<"\n\nArray after reversal is: \n\n";
       for(j=0;j<n;j++)
       {
           cout<<arr[j]<<" ";
       }
       cout<<"\n\n";
  }
  return 0;
}


OUTPUT:


C++ Program to Check if two trees are Mirror


C++ Program to check if given two trees are mirror or not is given below along with its algorithm and output.

Asked in:  DE shaw, Amazon

Example of two mirror trees:

                5                                                   5                                 
              /    \                                               /   \
            /        \                                           /       \
          4          3                                       3         4
                    /    \                                   /   \
                  /        \                               /       \
                 1         2                           2          1

             (a)                                              (b)



         
                    
ALGORITHM

function CHECK(roota, rootb):
       IF  roota=NULL and rootb=NULL:
                   return true
       IF  roota=NULL or rootb=NULL:
                   return false
      return  (roota.data=rootb.data && CHECK(roota.left,rootb.right) &&
                                                             CHECK(roota.right,rootb.left))


PROGRAM:

#include <bits/stdc++.h>
using namespace std;


struct node
{
  int data;
  struct node *left,*right;
};

node *create_new_node(int data);
bool check_for_mirror(struct node *root1,struct node *root2);

int main()
{
      /*creating first binary tree*/

      node *root1=create_new_node(5);
      root1->left=create_new_node(3);
      root1->left->left=create_new_node(2);
      root1->left->right=create_new_node(1);
      root1->right=create_new_node(4);


      /*creating second binary tree*/


      node *root2=create_new_node(5);
      root2->left=create_new_node(4);
      root2->right=create_new_node(3);
      root2->right->left=create_new_node(1);
      root2->right->right=create_new_node(2);

      if(check_for_mirror(root1,root2))
      {
            printf("\n\nTrees are mirrors\n\n");
      }
      else
      {
            printf("\n\nTrees are not mirrors\n\n");
      }

      return 0;
}
node *create_new_node(int data)
{ 
       
       node *newnode=new node();
       newnode->data=data;
       newnode->left=newnode->right=NULL;
       return newnode;
}

bool check_for_mirror(struct node *root1,struct node *root2)
{
    if(root1==NULL && root2==NULL)
    {
         return true;
    }
    if(root1==NULL || root2==NULL)
    {
         return false;
    }

    return (root1->data==root2->data &&
             (check_for_mirror(root1->left,root2->right) &&
              check_for_mirror(root1->right,root2->left)));
}


OUTPUT


Thursday, 11 May 2017

Program for Insertion and Deletion at the beginning of Singly Linked List in Python

python program for the insertion and deletion operation at the beginning of singly linked list is given below. In this program we have two method. insert_at_beg() to insert the element in the beginning and delete_at_beg() to delete the element at the beginning of the linked list.

PROGRAM:

class Node:
 def __init__(self,data):
  self.data=data
  self.next=None

class LinkedList:
 def __init__(self):
  self.head=None
  
 def insert(self,data):
  if(self.head==None):
   self.head=Node(data)
  else:
   current=self.head
   while(current.next!=None):
    current=current.next
   current.next=Node(data)

 def insert_at_beg(self,data):
  newnode=Node(data)
  newnode.next=self.head
  self.head=newnode

 def delete_at_beg(self):
  current=self.head
  self.head=current.next
  del current

 def printlist(self):
  current=self.head
  while(current!=None):
   print current.data,
   current=current.next

myLinkList=LinkedList()
myLinkList.insert(25)
myLinkList.insert(45)
myLinkList.insert(78)
print("\n\nCreated Linked List is: \n")
myLinkList.printlist()
print("\n\nEnter the element you want to insert at the beginning: ")
element=int(input())
myLinkList.insert_at_beg(element)
print("\n\nThe updated Linked List after insertion at beginning: \n")
myLinkList.printlist()
print("\n\nThe updated Linked List after deletion at beginning:\n")
myLinkList.delete_at_beg()
myLinkList.printlist()


OUTPUT:


Read also: python program to create a singly Linked List