Implement an algorithm to print all valid combination of n – pairs of parentheses properly opened and closed.

/*
      *  Example   n= 3.
      *  Output :  ((())) , (()()) , (())() , ()(()), ()()()
      *
      *  The problem can be solved by recursion. Select left or a right paren.
      *  If count(LeftParen) > 0 one can insert left paren.
      *  If count(RightParen) > count(LeftParen) i.e. no. of Left paren in an expression is greater than no. of right paren in the expression one can insert right parent.
      *
      *  1. Check for base case i.e. when no left or right paren are left all used up.
      *  2. If base case then print the string of parenthesis.
      *  3. If count of left parentheses > 0 then
      *        Insert Left parentheses in string str and decrement count of left parentheses by 1 and make recursive call.
      *  4. If count of right parentheses > count of left parentheses
      *        Insert right parentheses in string str and decrement count of right parentheses by 1 and make recursive call.
      *
*/ 
      void PrintParenthesis(int leftAvailable, int rightAvailable, string str)
      {
             if(leftAvailable == 0 && rightAvailable == 0)
             {
                   cout<<"n"<<str;
                   return;
             }
             if(leftAvailable >0)
                   PrintParenthesis(leftAvailable-1, rightAvailable, str+"(" );
             if(rightAvailable > leftAvailable)
                   PrintParenthesis(leftAvailable, rightAvailable-1, str+")" );    
      }

Rotate a matrix 90 degrees clockwise.

/*
      *  The algorithm is based on identifying the position of element at (row, col) after rotation.
      *  Before Rotation Coordinates:  row, col
      *  After Rotation Coordinates: r = col and c = N-1 –row (N => dimension of square matrix)
      *
      *  1 cyclic move cycle involvles:
      *  (0,0) -> (0,3) -> (3,3) - > (0,0)
      *  Values of location on left are propagated to locations on right of arrow.
      *
      *  Firstly this is done for outer most layer of matrix.
      *  row =0 , col = N-1 , row = N-1 and col = 0.
      *  Then this is done for one layer inner to the outer most layer of matrix.
      *  Row = 1, col = N-2 row = N-2 and col = 1
      *  So , on till I < (N-1)/2.
      *  i.e. Half no of rows.
      *
      *  Original Matrix
      *  1   2   3    4            
      *  5   6   7     8
      *  9   10 11 12
      *  13 14 15 16
      *
      *  After one cyclic move at i = 0, j =0
      *  13 2   3   1
      *  5   6    7   8
      *  9   10 11 12
      *  16 14 15  4
      *
      *  After second cyclic move at i=0 , j=1
      *  13 9   3    1
      *  5   6    7    2
      *  15 10 11 12
      *  16 14  8    4
      *
      *
      *  Rotated Matrix    
      *  13  9   5  1
      *  14  10  6  2
      *  15  11  7  3
      *  16  12  8  4
      *
      *
      *  ALGORITHM
      *  1. Scan each row till N/2
      *        for i=0 to i=(N-1)/2
      *  2. Pick each column one by one.
      *        for j =I to j = N-1-i
      *  3. Call moveCyclic and pass starting coordinates.
      *        a. Repeat 4 times.
      *        b. Temp1 = value of current node position.
      *        c. Temp2 = value of target location of temp1.
      *        d. Set row = NewRowIndex and col = NewColIndex.
      *        e. Set matrix[row][col] = temp1 and temp1 = temp2.
      *
      *  ALTERNATE SOLUTION
      *  1. Take transpose of a matrix.
      *  2. And then take mirror image of this matrix.
      *
      *  COMPLEXITY
      *  Time  : O(n2)
      *  Space: O(1)
      *
*/

      void setNewIndex(int &row, int &col, int N)
      {
           int temp = col;
           col = N - 1 - row;
           row = temp;
      }
     
      void moveCyclic(int row , int col , int N)
      {
           int temp1 = matrix[row][col];
           int temp2;
           for(int k=1; k<=4; k++)
           {
               setNewIndex(row,col, N);
               temp2 = matrix[row][col];
               matrix[row][col] = temp1;
               temp1 = temp2;
           }
      }
     
     
      int main()
      {
          int N = 6;
     
          display(N);
          for(int i=0; i<(N-1)/2 ; i++)
          {
                  for( int j=i; j<N-1-i ; j++)
                  {
                       moveCyclic(i,j,N);
                  }
          }
          cout<<"\nAfter Rotation\n";
          display(N);
          cout<<"\n\n";
          system("pause");
      }

Find Inorder Successor of a node in a binary tree.

/*
    * 1. Idea is to use code of inorder traversal.
    * 2. Keep track of last processed node in lastNode pointer variable.
    * 3. While processing the current node print last process Node. Current node will be inorder successor of last node.
    * 4. Update lastNode to current processed node and repat.
    *
    * The code can be modified with little changes to return inorder successor node of a specific node.
*/

     void inorderSuccessor(node *ptr)
     {
          if(ptr)
          {
                 inorderSuccessor(ptr->getLeftChild());
                 if(lastNode)
                      cout<<"\nSuccessor of "<<lastNode->getData();
                 else
                      cout<<"\nNo predecessor of ";
                 lastNode = ptr;
                 cout<<"\t"<<ptr->getData();                                    
                 inorderSuccessor(ptr->getRightChild());
          }
     }

There is a big file of words which is dynamically changing. We are continuously adding some words into it. How would you keep track of top 10 trending words at each moment?

/*
      First Chose a data structure, we have to keep track of frequency of each word.

      *  HashMap : use words as keys and frequency as value.
      *  TRIE    : Read word from file and add each word to prefix Tree, keep a counter attach to each node and increment it everytime same word is found.
      *  BST     : BST identifies duplicates hence each word can be associated with a counter which is incremented every time it is encountered.
      *            But problem with BST is it takes O(logn) time for searching and inserting.
      *            And also if BST is not balanced and number of words are large it will effect search and insert time.
      *
      *
      *
      *  1. Maintain an array topWords of 10 elements that stores top 10 trending words in sorted order of their frequency of occurrence.
      *  2. Read file word by word.
      *  3. Insert each word in a trie/prefix Tree maintaining the frequency of occurrence of this word at the same time.
      *  4. At each insert frequency of that word is incremented and checked in top 10 trending word.
      *  5. If the word’s frequency is greater than any top10 treding word it’s entry is made to the list.
      *  6. If word is already in top 10 trending words it’s position is changed if necessary to maintain the sorted order of trending words.
      *  In code below I have included only structure of class and not complete class (excluded some functions)
*/


      class TRIENode
      {
            private:
                    int prefixCount;
                    int frequency;
                    bool isWord;
                    TRIENode **child;
            public:
                   TRIENode()
                   {
                            prefixCount = 0;
                            frequency = 0;
                            isWord = false;
                            child = new TRIENode*[26];
                            for(int i=0; i<26; i++)
                                    child[i] = NULL;
                   }
      };
   
      class prefixTree
      {
            private:
                    TRIENode *root;
                    string topWords[10];
                    int count[10];
            public:
                    prefixTree()
                    {
                                root = new TRIENode();
                                for(int i=0; i<10; i++)
                                {
                                        count[i] = 0;
                                        topWords[i] = "";
                                }
                    }
                 
                    void insertWord(string word)
                    {
                         int len = word.length();
                         TRIENode *ptr = root;
                         for(int i=0 ; i< len ; i++)
                         {
                                 int index = word[i] - 'a';
                                 if(ptr->getChild(index) == NULL)
                                 {
                                                       TRIENode *newNode = new TRIENode();
                                                       ptr->createChild(newNode,index);
                                                       ptr = newNode;
                                 }
                                 else
                                 {
                                     ptr->incrementPrefixcount();
                                     ptr = ptr->getChild(index);
                                 }
                         }
                         ptr->setIsWord();
                         ptr->incrementFrequency();
                         int frequency = ptr->getFrequency();
                         if(isTopTenWord(frequency))
                         {
                                  insertInTopTen(word,frequency);                          
                         }
                    }
                 
     
       //Read File Word by Word.
                    void readFile()
                    {
                         string words;
                         ifstream fin("C:\\Users\\varun\\Desktop\\test.txt");
                         while(fin>>words)
                         {
                                          insertWord(words);
                         }
                    }          
      };
   
      int main()
      {
          prefixTree tree;
          tree.readFile();
          tree.displayTopTenWords();
          system("pause");
      }

Ancestor Matrix Problem.

There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).

    /*  

          * IDEA is to use post-order traversal of a binary tree because in post-order we have child nodes first and then parent node which makes our task easy.

          * Algorithm of post order traversal is modified to return a string to calling function. 

          * This string contains all the child nodes of a tree separated by a space.

          * Process current node and add it to str then return str.

          * Pass str to setArray function and also current node.

          * Current node will be parent node and str will contain all child nodes of parent node separated by space.

          * Set arr[parentNode][childNode] = 1.

          * Scan str from left to right and add character to string ch, if space is encountered convert ch to integer and set arr[parent][ch] = 1.

          * Now set ch = “” and repeat.Press any key to continue . . .

    */

int **arr;

void setArray(string child, int parent)

{

     string ch ="";

     for(int i=0; i<child.length()-1; i++)

     {

             if(child[i] == ' ')

             {

                         if(ch != "")

                         {

                               arr[parent][toInt(ch)] = 1;

                         }

                         ch = "";

             }

             else

                         ch += child[i];

     }

}

string fillArray(node *ptr)

{

       string str ="";

       if(ptr)

       {

              str += " " + fillArray(ptr->getLeftChild());

              str += " " + fillArray(ptr->getRightChild());

              str += " " + toString(ptr->getData());

              setArray(str,ptr->getData());

       }

       else

           str = "";

       return str;

}

//Create and initializes 2-D array to all zeros.

void initializeArray(int n)

{

     arr = new int*[n+1];

     for(int i=0; i<=n; i++)

     {

             arr[i] = new int[n+1];

             for(int j=0; j<=n ; j++)

                     arr[i][j] = 0;

     }

}

//Diplay the 2-D array.

void displayArray(int n)

{

     for(int i=0; i<=n; i++)

     {

             cout<<"\n\nrow "<<i<<"\t";

             for(int j=1; j<=n ; j++)

             {

                     if( i ==0 )

                         cout<<" c"<<j;

                     else

                         cout<<"  "<<arr[i][j];

             }

     }

}

//Convert a string to integer and return int.

int toInt(string s)

{

    int num;

    istringstream st(s);

    st >> num;

    return num;

}

//Convert integer to string and return string.

string toString(int Number)

{

        string Result;          

        // stream used for the conversion

       ostringstream convert; 

       // insert the textual representation of 'Number' in the characters in the stream       

       convert << Number;     

        // set 'Result' to the contents of the stream

       Result = convert.str();

       return Result;

}

ORIGINAL TREE

                 6

               /   \

              2     8

             / \   / \

            1   4 7   9

               / \     \

              3   5     10

CHILD NODES OF A NODE  

1       ChildNodes :    1

3       ChildNodes :    3

5       ChildNodes :    5

4       ChildNodes :     3    5 4

2       ChildNodes :     1     3    5 4 2

7       ChildNodes :    7

10      ChildNodes :    10

9       ChildNodes :      10 9

8       ChildNodes :     7      10 9 8

6       ChildNodes :      1     3    5 4 2     7      10 9 8 6

Ancestor Matrix

row 0    c1 c2 c3 c4 c5 c6 c7 c8 c9 c10

row 1     0  0  0  0  0  0  0  0  0  0

row 2     1  0  1  1  1  0  0  0  0  0

row 3     0  0  0  0  0  0  0  0  0  0

row 4     0  0  1  0  1  0  0  0  0  0

row 5     0  0  0  0  0  0  0  0  0  0

row 6     1  1  1  1  1  0  1  1  1  1

row 7     0  0  0  0  0  0  0  0  0  0

row 8     0  0  0  0  0  0  1  0  1  1

row 9     0  0  0  0  0  0  0  0  0  1

row 10    0  0  0  0  0  0  0  0  0  0

ROBOT MEET PROBLEM.

/*
      *  Two robots land with their parachutes on an infinite one-dimensional number line.
      *  They both release their parachutes as soon as they land and start moving.
      *  They are allowed only to make use of the following functions.
      *   I.     moveLeft()         // robot moves to left by 1 unit in 1 unit time
      *   II.    moveRight()        // robot moves to right by 1 unit in 1 unit time
      *   III.   noOperation()      // robot does not move and takes 1 unit time
      *   IV.    onTopOfParachute() // returns true if the robot is standing on top of either of the parachute, else false
      *   V.     didWeMeet()        // returns true if the robot meets to the other robot, else false
      *
      *
      *
      *  Approach -1
      *  __________________________________________________
      *  Move both the robots in oppossite directions.
      *  And at each step check whether 2 robots meet?
      *
      *  WON'T WORK :
      *  Consider robot1 landed at x=0 and robot2 landed at x=100.
      *  case1: move robot1 to right and move robot2 to left then both will meet at x=50.
      *  case2: move robot1 to left and move robot2 to right then they will never meet and will enter into infinite loop.
      *  As we donot have any means of finding out the coordinate of the robots This approach is not reliable.
      *
      *  Approach -2
      *  __________________________________________________
      *  Move both the robot to left.
      *  If robot crosses other's parachute.
      *  Reverse direction of second robot and continue moving first robot in same direction.
      *
      *  WON'T WORK :
      *  Because both robots are executing a separate copy of their program.
      *  A program can only influence robot executing this program and not the other robot as it is executed a copy of same program separately.
      *  And its movements will be governed by that program, variables assigned in one won't work in other.
      *  i.e. it is not possible to change the direction of other robot from program executed by this robot.
      *  
      *  Approach -3
      *  __________________________________________________
      *  follow this pattern, MoveLeft 1 time, MoveRight 2 times, MoveLeft 3 times, MoveRight 4 times and so on.
      *  In each iteration, the robot will go over it's own parachute one time.
      *  But after certain time, one robot will go over its parachute and also the other robots parachute.
      *  At this point, I stop this robot and continue with the other robot.
      *  Finally when this robot go over it's own parachute, it meets the other robot
      *
      *  This will work.
      *
      *  Approach -4
      *  __________________________________________________
      *  Keep a flag whether the robot has reached the other's parachute or not.
      *  If it has reached, call moveLeft() two times, otherwise call moveLeft() and noOperation().
      *  This way one robot will double it's speed as soon as it reaches to the other's parachute and eventually they will meet.
      *
      *  CATCH:
      *  Don't move a robot with twice as speed as other from landing point onwards.
      *  As we donot have any info which robot is behind and which one is in front.
      *  So if front robot is moved with double speed then lagging behind robot then it will never be able to catch it hence, never meet.
*/

      void roboMeet()
      {
            bool reachedParachute = false;
            while( !didWeMeet() )
            {
                  if(reachedParachute)
                  {
                        moveLeft();
                        moveLeft();
                  }
                  else
                  {
                        moveLeft();
                        noOperation();
                  }
                  if( onTopOfParachute() )
                  {
                        reachedParachute = true;
                  }
            }
      }

Write a function that returns the length of the longest leaf-to-leaf path in a binary.

/*  
     * At first problem seems to compute height of right subtree of root node and
     * height of left subtree of root node, then add them to get maximum lenght path.
     * But Its more complicated than this. Consider the following tree:
     *        100
     *       /  \
     *      70   150
     *     / \
     *    50  80
     *   / \   \
     *  40  60  90
     *     / \   \
     *    55  65  95
     *
     *  In this case, the root node is not even in the longest path (65-60-50-70-80-90-95).
     *  So, what you must do is the following: For each node n you must compute the following:
     *  • compute longest path in left subtree starting with the root of the left subtree.
     *  • compute longest path in right subtree starting with the root of the right subtree .
     *  • compute the longest path in left subtree (not necessarily starting with the root of the left subtree).
     *  • compute the longest path in right subtree (not necessarily starting with the root of the right subtree).
     *
     *
     *  Structure of node is modified.
     *  Now node contains 2 more integers lDepth and rDepth.
     *  lDepth => maximum height of  left sub-tree of a node.
     *  rDepth => maximum height of right sub-tree of a node.
     *  1. Idea is to use inorder traversal algo to initialize lDepth and rDepth of each node in a bottom up manner.
     *  2. If a node has no left child then set it’s lDepth = 0.
     *  3. Recursively call initalizeLRDepth with left child as argument.
     *  4. When backtracking occurs i.e. if  leftChild of ptr is not null then:
     *        set lDepth of current node (ptr) to 1+ max (lDepth,rDepth) of left Child of ptr.
     *  5. Recursively call initializeLRDepth with right child as argument.
     *  6. When backtracking occurs i.e. if rightChild of ptr is not null then:
     *        set rDepth of current node (ptr) to 1 + max(lDepth,rDepth) of right child of ptr.
     *  7. Select node having maximum lDepth+rDepth.
*/




      class node
      {
            private:
           int data;
           node *left;
           node *right;
           int lDepth;
           int rDetph;
      }


      void initializeLRDEPTH(node *ptr)
      {
            if(ptr)
            {
                  if(! ptr->getLeftChild())
                        ptr->setLDEPTH(0);
                 
                  initializeLRDEPTH(ptr->getLeftChild());
                  if(ptr->getLeftChild())
                        ptr->setLDEPTH(max(ptr->getLeftChild()->getLDEPTH(),ptr->getLeftChild()->getRDEPTH())+1);
                 
                  if(! ptr->getRightChild())
                        ptr->setRDEPTH(0);
                 
                  initializeLRDEPTH(ptr->getRightChild());
                  if(ptr->getRightChild())
                        ptr->setRDEPTH(max(ptr->getRightChild()->getLDEPTH(),ptr->getRightChild()->getRDEPTH())+1);
                 
            }
      }

To find if there is any root to leaf path with specified sum in a binary tree.

/*
    1.    Idea is to use inorder traversal algorithm.
    2.    Set variable present = false it is set to true as soon as we find the leaf element at which sum from root to this element is equal to val.
    3.    After present =true no more recursive calls are made it is ensure by
    if present then return.
    4.    After leaf element with sum from root to it equal to val is found no more recursive calls will be made. print these previously made calls as they will trace back to root node from search element.
    5.    If present == true then print node->data.
*/   
   
    bool present;
    void leafSum(node *ptr, int val)
    {
        if(present)
            return;
        if(ptr)
        {
            // LEAF NODE
              if(ptr->getLeftChild() == NULL && ptr->getRightChild() == NULL)
              {
                  if(val - ptr->getData() == 0)
                  {
                      cout<<"PRESENT";
                      present = true;
                  }
              }
              leafSum(ptr->getLeftChild(), val - ptr->getData());
              leafSum(ptr->getRightChild(), val - ptr->getData());
              if(present)
                  cout<<"  "<<ptr->getData();
        }
        
    }

Non-Recursive Implementation of Post order traversal in BInary Tree/ BST.

/***************POST ORDER*******************
     1. Create a stack and Push NULL as the first element in stack.
     2. Initialize a pointer ptr = root to traverse in the tree
     3. Initialize a pointer prev = NULL which will store previously processed node.
     4. Repeat steps  5 to 6.
     5. If ptr is not NULL then
         a. push ptr to stack and set ptr = leftChild(ptr).
     6. Else
         a. Set ptr = Top element of stack
         b. If  Top element is NULL (ptr = NULL) then return
         c. If ptr has right child and RightChild != previously processed node
             then set ptr to rightChild(ptr)
         d. Else
              i. Decrement top of stack.
             ii. Process ptr.
             iii. Set prev =  ptr.
             iv. Set ptr = NULL.

     COMPLEXITY
     Time   :  O(n)
     Space :  O(n)

*/

C++ CODE
void iterativePostorder()
{
     cout<<"\nPOSTORDER:\n";
     int top =0;
     node *ptr = root,*prev = NULL;
     node* stack[50];
     stack[0] = NULL;
     while(1)
     {
               if(ptr != NULL )
               {
                      stack[++top] = ptr;
                      ptr = ptr->getLeftChild();
               }
               else
               {
                      ptr = stack[top];
                      if( ptr == NULL)
                          return;
                      if(ptr->getRightChild() != NULL && ptr->getRightChild() != prev )
                      {
                          ptr = ptr->getRightChild();
                         
                      }
                      else
                      {
                          top--;
                          cout<<"  "<<ptr->getData();
                          prev = ptr;
                          ptr = NULL;
                      }
               }
     }
}

Non-Recursive implementation of Inorder Traversal of Binary Tree/ BST.

/*******************INORDER*****************
    1. Create a stack and Push NULL as the first element in stack.
    2. Initialize a pointer ptr = root to traverse in the tree.
    3. Repeat steps  4 to 5.
    4. If ptr is not NULL then
        a. push ptr to stack and set ptr = leftChild(ptr).
    5. Else
        a. Pop top element from stack and assign it to ptr.
        b. If NULL is popped then return
        c. Process Node
        d. If ptr has right child then set ptr to rightChild(ptr)
        e. Else set ptr = NULL.

    COMPLEXITY
    Time   :  O(n)
    Space :  O(n)

*/

void iterativeInorder()
{
     cout<<"\nINORDER:\n";
     int top =0;
     node *ptr = root;
     node* stack[50];
     stack[0] = NULL;
     while(1)
     {
               if(ptr != NULL )
               {
                      stack[++top] = ptr;
                      ptr = ptr->getLeftChild();
               }
               else
               {
                      ptr = stack[top--];
                      if( ptr == NULL)
                          return;
                      cout<<"  "<<ptr->getData();
                      if(ptr->getRightChild() != NULL)
                          ptr = ptr->getRightChild();
                      else
                          ptr = NULL;
               }
     }
}

Non-Recursive implementation of Preorder Traversal in a binary Tree / BST.

/********************PREORDER*****************
    1. Create a stack and Push NULL as the first element in stack.
    2. Initialize a pointer ptr = root to traverse in the tree.
    3. Repeat steps  4 to 5.
    4. If ptr is not NULL then
        a. Process Node ptr.
        b. push ptr to stack and set ptr = leftChild(ptr).
    5. Else
        a. Pop top element from stack and assign it to ptr.
        b. If NULL is popped then return
        c. If ptr has right child then set ptr to rightChild(ptr)
        d. Else set ptr = NULL.

    COMPLEXITY
    Time   :  O(n)
    Space :  O(n)
*/

void iterativePreorder()
{
     cout<<"\nPREORDER:\n";
     node* stack[50] ;
     stack[0] = NULL;
     int top = 0;
     node *ptr = root;
     while(1)
     {
             if(ptr != NULL)
             {
                    cout<<"  "<<ptr->getData();
                    stack[++top] = ptr;
                    ptr = ptr->getLeftChild();
             }
             else
             {
                 ptr = stack[top--];
                 if( ptr == NULL)
                     return;
                 if(ptr->getRightChild())
                     ptr = ptr->getRightChild();
                 else
                     ptr = NULL;
             }
     }
}