Print all permutations of a String using BackTracking Algorithm

/*
Using Backtracking Algo to print all the permutations of a string
*/


#include "iostream"
using namespace std;




void permutate(int startIndex,int endIndex,char s[])
{
if (startIndex==endIndex)
{
cout<<s<<endl; 
return;
}

for(int j=startIndex;j<=endIndex;j++)
{
char c = s[startIndex];
s[startIndex] = s[j];
s[j] = c;
permutate(startIndex+1,endIndex,s);
c = s[startIndex];
s[startIndex] = s[j];
s[j] = c;
}


}


int main()
{
// As a test case I have taken max length of string as 4. 
//use std::string or vector<char> instead if dynamic length needed
char s[] = "ABCD";
permutate(0,3,s);
return 0;
}

N characters are present in an array. Window W is given. Find character which has come maximum number of times in any window possible in the array.

Process Scheduling

/*
There are N processes. Each may depend on another process to be completed to start.
Write a Program to schedule the processes.
Example Graph :
Process 3 and 5 can run only after Process 0
...
...
Process 1 can run after 2 and 4

Algo:
Initialization : Store in every node a list of all nodes which depend on it. Also store the count of nodes it depends on.
1. Complete the process which is independent, depends count = zero.
2. Now decrease the count of all nodes in its list , i.e., count of all nodes that depend on it.
3. Find next node which has depends count = zero. complete the process. go to step 2.
4. Repeat this for all processes.
*/


#include "iostream"
#include "vector"
class Process
{
public:
 int process_number;
 int depends_on;
 std::vector <Process *> complete_before;
 Process(int num) : process_number(num) , depends_on(0)  {  }
};

int main()
{
 std::vector <Process *> mylist;
 std::vector <Process *> finallist;
 for(int i=0;i<6;i++)
  mylist.push_back(new Process(i));
 // do something to add details

 mylist[0]->complete_before.push_back(mylist[3]);
 mylist[0]->complete_before.push_back(mylist[5]);
 mylist[2]->complete_before.push_back(mylist[1]);
 mylist[3]->complete_before.push_back(mylist[2]);
 mylist[4]->complete_before.push_back(mylist[1]);
 mylist[5]->complete_before.push_back(mylist[2]);
 mylist[5]->complete_before.push_back(mylist[4]);
 mylist[0]->depends_on = 0;
 mylist[1]->depends_on = 2;
 mylist[2]->depends_on = 2;
 mylist[3]->depends_on = 1;
 mylist[4]->depends_on = 1;
 mylist[5]->depends_on = 1;
 std::vector<Process *>::iterator itr = mylist.begin();
 while(itr != mylist.end())
 {
      Process * current = *itr;
      if(current->depends_on == 0)
      {
            std::vector<Process *>::iterator temp_itr = current->complete_before.begin();
            while(temp_itr != current->complete_before.end())
           {
                 (*temp_itr)->depends_on--;
                 temp_itr++;
           }
      }else
     {
            itr++;
           continue;
      }
      finallist.push_back(*itr);
      mylist.erase(itr);
      itr = mylist.begin();
 }
 itr = finallist.begin();
 while(itr != finallist.end())
 {
      std::cout << (*itr)->process_number << std::endl;
      itr++;
 }
 return 0;
}

Longest increasing subsequence in an array

/*
Find the longest increasing sub sequence in an array of random numbers.
*/

Any integer can be repeated any number of times in a sorted array. Given a key, find number of occurrences of key.

Find Maximum Possible Zig-Zag subsequence in a sequence

/*
Start with the first 2 elements. If the 2 element is greater than first , then next you have to find the reducing number and viceversa.
If you find lets say the 3rd number also to be increasing, then take 3rd number as your sequence number rather than 2nd, i.e, replace 2nd number with 3rd number. and go on like this till the end.

Example:

Initial sequence : 5 6 4 2 100 25 32 35
Final seq: 5 6 (Increasing)
Final seq: 5 6 4(Decreasing)
Final seq: 5 6 2(Decreasing, replace 4 with 2)
...
..
Final seq: 5 6 2 100 25 35

*/

#include "iostream"
#include "vector"
using namespace std;

enum STATE
{
     UNKNOWN,
     NEED_TO_INCREASE,
     NEED_TO_DECREASE
};

int main()
{
     STATE state = UNKNOWN;
     int noOfElements,temp;
     vector<int> arraylist;
     vector<int> finalsequence;
     int lastelement;
     bool isIncreased;
     cout<<"Enter the number of elements in array : ";
     cin>>noOfElements;
     cout<<"Enter the elements"<<endl;
     for(int i=0;i<noOfElements;i++)
     {
          cin>>temp;
          arraylist.push_back(temp);
     }
     finalsequence.push_back(arraylist[0]);
     int index = 0;
   
     while((++index) < noOfElements)
    {
          switch(state)
         {
               case UNKNOWN:
                    if(arraylist[index] > arraylist[0])    
                         state = NEED_TO_DECREASE;  
                    else if(arraylist[index] < arraylist[0])    
                         state = NEED_TO_INCREASE;  
                    finalsequence.push_back(arraylist[index]);
                    lastelement = arraylist[index]; 
                    break;
               case NEED_TO_INCREASE: 
                    if(arraylist[index] > lastelement)
                   {   
                         finalsequence.push_back(arraylist[index]);
                         state = NEED_TO_DECREASE;
                    }else    
                          finalsequence[finalsequence.size()-1] = arraylist[index];
                     lastelement = arraylist[index];
                     break;
               case NEED_TO_DECREASE: 
                     if(arraylist[index] < lastelement)
                    {   
                          finalsequence.push_back(arraylist[index]);
                          state = NEED_TO_INCREASE;
                     }else    
                          finalsequence[finalsequence.size()-1] = arraylist[index];
                     lastelement = arraylist[index];
                     break; 
           }
     } 

     vector<int>::iterator itr = finalsequence.begin();
      while(itr != finalsequence.end())
     {
           cout<<*itr<<" ";
           itr++;
      }
      return 0;
}

Balls and the ways..

N balls are present in a basket. In one iteration either one ball or two balls can be withdrawn from the basket. Iterations are performed until basket gets empty. Find number of possible ways (write code).

#include "iostream"
using namespace std;
// Is this the Best way to find a factorial
int factorial(int n)
{
 if(n==0 || n==1)
  return 1;


int i = n-1;
while(i>1)
{
  n = n*i;
  i--;
}


 return n*factorial(n-1);
}
int main()
{
 int noOfBalls;
 cin>>noOfBalls;
 // Initalization.
 int num1,num2;
 int totalways;
 if(noOfballs <= 0)
 {
  cout<<"0";
  return;
 }
 // Initialization. We dont calculate one obvious way of using all 1s
 num1 = noOfBalls-2;
 num2=1;
 totalways = 1;


 while(num1 >= 0)
 {
  if(num1==0) { totalways++; break; }
  totalways += (factorial(num1+num2) / (factorial(num1) * factorial(num2)));
  num2++;
  num1 = num1-2;
 }
 cout<<totalways;
 return 0;
} 

Inorder Traversal Without Recursion (can be used for DFS without recursion)

/*
In order traversal without recursion using Morris Traversal.

Algo :

1. Initialize current as root
2. While current is not NULL
    If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
    Else
      a) Make current as right child of the rightmost node in current's left subtree
      b) Go to this left child, i.e., current = current->left
*/


#include "iostream"
using namespace std;
struct Node
{
     int data;
     Node * left;
     Node * right;
     Node() : left(NULL),right(NULL),data(0) { }
     Node(Node * l,Node * r,int d) : left(l),right(r),data(d) { }
     Node(int d) : left(NULL),right(NULL),data(d) { }
     ~Node()
    {
          if(left)
               delete left;
          if(right)
               delete right;
     }
};

void removeNodes(Node * root)
{
     if(root)
    {
          if(root->right)
          {
               removeNodes(root->right);
               root->right = NULL;
             }
          if(root->left)
          {
               removeNodes(root->left);
               root->left = NULL;
          }
          delete root;
     }
}

// Morris Traversal
void InorderTraversal(Node * root)
{
     Node * current, * pre;
     if(root == NULL)
          return;

     current = root;
     while(current)
     {
           if(current->left == NULL)
          {
                cout<< current->data <<" ";
                current = current->right;
           }else
          {
                // reArrange
                pre = current->left;
                while(pre->right != NULL && pre->right != current)
                     pre = pre->right;
                if(pre->right == NULL)
               {
                     pre->right = current;
                     current = current->left;
                }
       // print data and remove reArrangement
                else
               {
                     pre->right = NULL;
                    cout<< current->data << " ";
                    current= current->right;
                }
          }
      }
}


int main()
{
     Node * root = new Node(7);
     root->left = new Node(5);
     root->right = new Node(9);
     root->right->left = new Node(8);
     root->right->right = new Node(10);

     root->left->left = new Node(3);
     root->left->right = new Node(6);
     root->left->left->left = new Node(1);
     root->left->left->right = new Node(4);
     root->left->left->left->right = new Node(2);
   
     InorderTraversal(root);

     removeNodes(root);
     return 0;
}

Longest Common Subsequence(LCS) using Dynamic Pragramming and Finding one of the optimal solutions by Backtracking

/*
This finds the LCS by Dynamic Programming
*/

#include "iostream"
#include "string"
#include "vector"
using namespace std;
int main()
{
     string X,Y;
     int Xlen,Ylen;
     cin>>X;
     cin>>Y;
     Xlen = X.length();
     Ylen = Y.length();
     vector<vector<int>> table;
     table.resize(Xlen+1);
     for(int i=0;i<=Xlen;i++)
          table[i].resize(Ylen+1);
     for(int i=0; i<Xlen; i++)
          table[i][0] = 0;
     for(int i=0; i<Ylen; i++)
          table[0][i] = 0;
     int entry;
     for(int i=1; i<=Xlen; i++)
          for(int j=1; j<=Ylen; j++)
          {
               if(X[i-1] == Y[j-1])
              {
                    entry = table[i-1][j] > table[i][j-1] ? table[i-1][j] : table[i][j-1];
                    entry = (table[i-1][j-1] + 1) > entry ?  (table[i-1][j-1] + 1) : entry;
                    table[i][j] = entry;
              }else
                    table[i][j] = table[i-1][j] > table[i][j-1] ? table[i-1][j] : table[i][j-1];   
           }
     cout<<table[Xlen][Ylen]<<endl;

     //Back tracking to find one of the optimal solutions
     string LCS = "";
     for(int i=Xlen,j=Ylen;i>0 && j>0;)
     {
           if(X[i-1] == Y[j-1])
          {
                LCS.insert(LCS.begin(),X[i-1]);
                i--;
                j--;
          }
          else
          {
               if(table[i-1][j] > table[i][j-1])
                    i--;
               else
                    j--;
           }
      }
      cout<<"LCS string is "<<LCS;
      return 0;
}

Breadth First Search(BFS) of a Binary tree

/*
WORKING OF THE BFS FUNCTION CODE :


The root node is pushed into the queue so that the loop starts its iteration from the root. After that everytime the data is compared to check whether it is present. If not, the left and right nodes of the current node (same level) are pushed into the queue. This was all the nodes of the same level are pushed into the queue first and are popped out of the queue first.

*/

#include <iostream>
#include <queue>
using namespace std;

struct Node
{
     int m_data;
     Node * m_left;
     Node * m_right;

     Node(int data,Node * left,Node * right) : m_data(data),m_left(left),m_right(right)  {  }
     Node(int data) : m_data(data),m_left(NULL),m_right(NULL) { }
     Node() : m_data(0),m_left(NULL),m_right(NULL) {  }   //  m_data initialized to zero
};

bool BFS(Node * root,int data)
{
     queue<Node *> q;
     Node * temp;
     q.push(root);   // Push the parent in the queue, so that the loop starts from the parent.
     while(q.empty())
     {
          temp = q.front();
          q.pop();
          if(temp->m_data == data)
               return true;
          if(temp->left)
               q.push(temp->left);
          if(temp->right)
               q.push(temp->right);
          }

     return false;
}

int main()
{
     Node * root = new Node(3);
     root->left = new Node(4);
     root->right = new Node(5);
     root->left->left = new Node(2);

     if(BFS(root,2))
          cout<<"Node with data 2 found";
     else
          cout<<"Node with data 2 not found"
     return 0;
}