Algo#48: Find minimum window length which accommodate all given character.

Given problem is purely string manipulation problem. Here we have to find minimum window length which accommodate all given character for second string.

E.g. Given string ABBACBAA, and if we want to find minimum window length which can accommodate "AAA", it will be 5 (index 3 to 7). "CCC" should return MAX length as no window in original string can accommodate "CCC".

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#47: Word search in matrix of N*N

Word search can be solved with backtracking method.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#45: Find middle node from given singly linked list using recursion.

We can find middle node from given linked list in one look of singly linked list using recursion (Ignoring stack removal access).

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#44: Modify linked list to put nodes alternate from begin & end

To modify linked list to put nodes alternate from begin & end, we will use recursion. So we can access nodes in forward and reverse direction simultaneously. And we don't need to go back and forth to access nodes from begin and end.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#30: Iterative implementation of Post-order, Pre-order & In-order traversal of given binary tree

We mostly use recursive function whenever we are asked traversal of binary tree. But what if you have to do it iterative. All recursion function can be converted to iterative with more or less effort.

Here we will see Post-order, Pre-order & In-order traversal of given binary tree using iterative method.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#28: Help frog to cross river.

Lets say there is a river that is η meters wide. At every meter from the starting shore, there may or may not be a stone enough for frog to sit. Now a frog needs to cross the river. However the frog has the limitation that if it has just jumped x meters, then it can take next jump only of size  x-1, x or x+1 meters. First jump can be of only 1 meter when starting from shore.

Assume frog can see all stone from this shore to opposite shore. Can frog determine whether it can make it to the other end or not.

Following is implementation of above problem in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#25: Find kth smallest from given 2 sorted array.

Finding kth smallest element from given 2 sorted array is not big deal if we are allowed to do it in O(K) or O(N+M). But what if you are asked to do it less than that. Can we use binary search technique to reduce complexity as given array are sorted !!

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#20: Tail command implementation

Tail command is used for extracting last n lines from file. This is very common question that we can expect  in any IT interview. To implement tail command we will use queue data structure. 

Following is simple algorithm for tail command implementation with n as parameter (number of last lines to read).

Step 1: Read line from file, and store it into queue.
Step 2: If number of lines in queue exceeds parameter n, then we can delete one line from front. Because we only need to keep n lines in queue.
Step 3: When file reading ends, we have n lines in queue.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#15: Sudoku solver

To solve given Sudoku of any level, by back tracking method, we have to try each possible combinations until it gets solved. We have to take care about given filled numbers which we can not modified while doing back track.

First thing we need here is, way to check whether we can put chosen number at particular location or not. We can put number only if satisfy following criteria.
1. It should be unique in its row.
2. It should be unique in its column.
3. It should be unique in its region (3 * 3) box.

Lets say we made some function called isValid() which tell check above constraint for our move. Now we are ready to take up our back tracking algorithm.

Following is simple recursive algorithm for Solving given Sudoku.

Step 1: If we have filled all position without violation of any constraint, then we are done.
Step 2: If current location (filling row by row, left to right) is fixed location, we can not modified it, go ahead and fill remaining location recursively.
Step 3: Try every element from 1 to 9 one by one and check if remaining Sudoku can be solved recursively. If we are out of all nine numbers, and Sudoku doesn't yet solved then Sudoku is unsolvable.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#9: Add 2 numbers represented by linked list such that MSD of number is head of linked list.

Numbers represented by link list means each digit of number is occupying 1 node in linked list. Obviously your next question would be how number is stored, is it head to tail or tail to head in linked list. Both ways are right depending on purpose of your application. Lets say, Most Significant Digit (MSD) is representing head of linked list. E.G 321 can be represented as : 3->2->1 , 52 can be represented as : 5->2

So coming to given problem. We have been given 2 such linked list, and our task at hand is to sum up these 2 numbers and store its addition in one such link list. One thing to note here is, when list are represented like this, actually we are having tough problem to solve because 2 list can be of different size. One way to convert this problem in easy one is by reversing both list, then apply algorithm of adding list when header represent LSD. But what if we have been asked that we can't modify given 2 list at all. Here comes recursion to help us.

Following is simple recursive algorithm for adding  2 numbers represented by linked list such that MSD of number is head of linked list. Technique same as post order traversal, process remaining (child) list first before adding current node.

Assume that size(first list) >= size(second list) , this assumption can be taken without any loss of generality of our algorithm because we can always pass list to our algorithm such that assumption is perfectly valid.

Step 1: If both current list are empty, then resultant list is also empty.
Step 2: Otherwise, any one or both list are not empty.
        2.1: Make new resultant list node with its value as zero.
      2.2: Add remaining digits from both list recursively same way. Don't forget to get carry of remaining addition.
           2.2.1: If both list have same size, then add digit from first list, digit from second list and carry of remaining list addition.
          2.2.2: If size(first list) > size(second list), then add digit from first list and carry of remaining list addition.
       2.3: Get resultant digit of this addition by taking modulo 10 and put it inside newly created node.
       2.4: Attach list built from recursion to current resultant list.
       2.5: [CRITICAL STEP] Fill reverse carry so that previous iteration can use it.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#8: Add 2 numbers represented by linked list such that LSD of number is head of linked list.

Numbers represented by link list means each digit of number is occupying 1 node in linked list. Obviously your next question would be how number is stored, is it head to tail or tail to head in linked list. Both ways are right depending on purpose of your application. Lets say, Least Significant Digit (LSD) is representing head of linked list. E.G 321 can be represented as : 1->2->3

So coming to given problem. We have been given 2 such linked list, and our task at hand is to sum up these 2 numbers and store its addition in one such link list.

Following is simple algorithm for adding  2 numbers represented by linked list such that LSD of number is head of linked list.

Step 1: If both current list are empty, then resultant list is also empty.
Step 2: Otherwise, any one or both list are not empty.
        2.1: Make new resultant list node with its value as zero.
        2.2: Add initial digit from both current list (Add zero if any list is empty), along with carry from previous addition (if any else add zero).
        2.3: Get resultant digit of this addition by taking modulo 10 and put it inside newly created node and keep carry ready to be passed to next iteration.
       2.4: Add remaining digits from both list recursively same way. Don't forget to pass carry of last addition.
       2.5: Attach list built from recursion to current resultant list node.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#6: Preorder Successor in Binary Tree

Preorder Successor value for any node X means value of node Y that comes just after node X while doing Preorder traversal. For given tree in figure, preorder traversal (Root Left Right) would be : 1 2 4 5 3 6. We can search preorder successor for any node by just looking at this traversal output. E.G. preorder successor of node '3' is node '6' because '6' appears after '3' in given traversal.

But in real life we encounter Preorder Successor to be search for any node randomly, and if we go by this method of doing preorder traversal first then giving successor, it would be inefficient because of its time complexity of O(n) in large trees. So we need some method which can return Preorder Successor randomly for any node without doing traversal explicitly in less time complexity.

Luckily preorder traversal follows some pattern which can help us in giving Preorder Successor for any node without doing traversal at all.

Following is simple algorithm for finding Preorder Successor of binary tree.

Step 1: Current root itself is NULL, then successor is also NULL.

Step 2: Current root contains value same as key for which we are looking successor.

        2.1: Current root has right child, then left most node of right child is successor.

        2.2: Current root does have right child r, then r is successor.
        2.3: Current root is left leaf node and having sibling on right side

        2.4: Otherwise, if current root has an ancestor, v, which is a left-child and v has a right sibling, vrs, then succ(current root) is vrs
        2.5: If none of above applies, then succ(current root) doesn't exist.

Step 3: Current root is not the target node for which we are looking successor.

        3.1: Search target node and its successor in left side of tree recursively, and return if found.

        3.2: Search target node and its successor in right side of tree recursively, and return.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#5: Preorder Predecessor in Binary Tree

Preorder Predecessor value for any node X means value of node Y that comes just before node X while doing Preorder traversal. For given tree in figure, preorder traversal (Root Left Right) would be : 1 2 4 5 3 6. We can search preorder predecessor for any node by just looking at this traversal output. E.G. preorder predecessor of node '4' is node '2' because '2' appears before '4' in given traversal.

But in real life we encounter Preorder Predecessor to be search for randomly any node, and if we go by this method of doing preorder traversal first then giving predecessor, it would be inefficient because of its time complexity of O(n) in large trees. So we need some method which can return Preorder Predecessor randomly for any node without doing traversal explicitly in less time complexity.

Luckily preorder traversal follows some pattern which can help us in giving Preorder Predecessor for any node without doing traversal at all.

Following is simple algorithm for finding Preorder Predecessor of binary tree.

Step 1: Current root itself is NULL, then predecessor is also NULL.

Step 2: Current root contains value same as key for which we are looking predecessor.

        2.1: If current root is the root of the tree, then pred(current root) is undefined

        2.2: If u has a left sibling, ls, then pred(current root) is the rightmost descendant of ls
        2.3: Otherwise, pred(current root) is parent(current root).

Step 3: Current root is not the target node for which we are looking predecessor.

        3.1: Search target node and its predecessor in left side of tree recursively, and return if found.

        3.2: Search target node and its predecessor in right side of tree recursively, and return.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#4: Postorder Successor in Binary Tree

Postorder Successor value for any node X means value of node Y that comes just after node X while doing Postorder traversal. For given tree in figure, postorder traversal (Left Right Root) would be : 4 5 2 6 3 1. We can search postorder successor for any node by just looking at this traversal output. E.G. postorder successor of node '4' is node '5' because '5' appears after '4' in given traversal.

But in real life we encounter Postorder Successor to be search for randomly any node, and if we go by this method of doing postorder traversal first then giving successor  it would be inefficient because of its time complexity of O(n) in large trees. So we need some method which can return Postorder successor randomly for any node without doing traversal explicitly in less time complexity.

Luckily postorder traversal follows some pattern which can help us in giving Postorder Successor for any node without doing traversal at all.

Following is simple algorithm for finding Postorder Successor of binary tree.

Step 1: If current root is NULL, then succ(current root) is NULL.

Step 2: If current root is target node for which we are looking for successor.

        2.1: If current root is the root of the tree, succ(current root) is undefined.

        2.2: Otherwise, if current root is a right child, succ(current root) is parent(current root).

        2.3: Otherwise current root is a left child and the following applies:

           2.3.1: If u has a right sibling, r, succ(current root) is the leftmost leaf in r's sub-tree

           2.3.2: Otherwise succ(current root) is parent(current root).
           2.3.3: If none of above applies, then succ(current root) doesn't exist.

Step 3: Current root is not the target node for which we are looking predecessor.

        3.1: Search target node and its predecessor in left side of tree recursively, and return if found.

        3.2: Search target node and its predecessor in right side of tree recursively, and return.

Following is implementation of above algorithm in c language.

/*
Algo#4: Postorder Successor in Binary Tree

Description: Find Postorder Successor value in given Biinary Tree.
*/
#include 
#include 

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

Node *leftmostLEAFnotNODE(Node *root)
{
    while (root->left || root->right)
    {
        if(root->left) root=root->left;
        else root=root->right;
    }

    return root;
}

Node *postorderSuccessorRec(Node *root, int key,Node *direct_parent, Node *parent,Node * treeroot)
{
    //Case 1: If current root is NULL, then succ(current root) is NULL.
    if (root==NULL)
        return 0;
    //Case 2: If current root is target node for which we are looking for successor.
    if (root->data == key)
    {
        //Case 2.1: If current root is the root of the tree, succ(current root) is undefined.
        if(root == treeroot)
            return NULL;
        //Case 2.2: Otherwise, if current root is a right child, succ(current root) is parent(current root).
        else if(direct_parent != NULL && direct_parent->right==root)
            return direct_parent;
        //Case 2.3: Otherwise current root is a left child and the following applies:

        //Case 2.3.1: If u has a right sibling, r, succ(current root) is the leftmost leaf in r's sub-tree
        else if(direct_parent != NULL && direct_parent->left==root && direct_parent->right!=NULL)
            return leftmostLEAFnotNODE(direct_parent->right);
        //Case 2.3.2: Otherwise succ(current root) is parent(current root).
        else if(direct_parent != NULL && direct_parent->left==root && direct_parent->right==NULL)
            return direct_parent;
        //Case 2.3.3: If none of above applies, then succ(current root) doesn't exist.
        else
            return NULL;
    }
    //Case 3: Current root is not the target node for which we are looking successor.
    else
    {
        //Case 3.1: Search target node and its successor in left side of tree recursively, and return if found.
        Node *left=postorderSuccessorRec(root->left,key,root,root,treeroot);
        if (left)
            return left;
        //Case 3.2: Search target node and its successor in right side of tree recursively, and return.
        return postorderSuccessorRec(root->right,key,root,parent,treeroot);
    }
}

Node *postorderSuccessor(Node *root, int key)
{
    return postorderSuccessorRec(root,key,NULL,NULL,root);
}

struct node* newNode(int data)
{
  struct node* node = (struct node*)  malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}


int main()
{

  /*
            1
          /   \
        2      3
      /  \    /
    4     5  6
  */
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);

  struct node * succ;
  succ = postorderSuccessor(root, 3);
  printf("Postorder Successor of %d is : %d\n",3,succ?succ->data:0);

  succ = postorderSuccessor(root, 4);
  printf("Postorder Successor of %d is : %d\n",4,succ?succ->data:0);

  getchar();
  return 0;
}

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#3: Postorder Predecessor in Binary Tree

Postorder Predecessor value for any node X means value of node Y that comes just before node X while doing Postorder traversal. For given tree in figure, postorder traversal (Left Right Root) would be : 4 5 2 6 3 1. We can search postorder predecessor for any node by just looking at this traversal output. E.G. postorder predecessor of node '5' is node '4' because '4' appears before '5' in given traversal.

But in real life we encounter Postorder Predecessor to be search for randomly any node, and if we go by this method of doing postorder traversal first then giving predecessor, it would be inefficient because of its time complexity of O(n) in large trees. So we need some method which can return Postorder Predecessor randomly for any node without doing traversal explicitly in less time complexity.

Luckily postorder traversal follows some pattern which can help us in giving Postorder Predecessor for any node without doing traversal at all.

Following is simple algorithm for finding Postorder Predecessor of binary tree.

Step 1: If current root is NULL, then pred(current root) is NULL.

Step 2: If current root is target node for which we are looking for predecessor.

        2.1: If current root has a right child, r, then pred(current root) is r.

        2.2: Otherwise If current root has a left child, l, then pred(current root) is l.

        2.3: Otherwise if current root has a left sibling, ls, then pred(current root) is ls

      2.4: Otherwise if current root has an ancestor, v, which is a right child and has a left sibling, vls, then pred(current root) is vls

        2.5: Otherwise, pred(current root) is undefined.

Step 3: Current root is not the target node for which we are looking predecessor.

        3.1: Search target node and its predecessor in left side of tree recursively, and return if found.

        3.2: Search target node and its predecessor in right side of tree recursively, and return.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#2: Inorder Successor in Binary Tree

Inorder Successor value for any node X means value of node Y that comes just after node X while doing Inorder traversal. For given tree in figure, inorder traversal (Left Root Right) would be : 4 2 5 1 6 3. We can search inorder successor for any node by just looking at this traversal output. E.G. inorder successor of node '1' is node '6' because '6' appears after '1' in given traversal.

But in real life we encounter Inorder Successor to be search for any node randomly, and if we go by this method of doing inorder traversal first then giving successor, it would be inefficient because of its time complexity of O(n) in large trees. So we need some method which can return Inorder Successor randomly for any node without doing traversal explicitly in less time complexity.

Luckily inorder traversal follows some pattern which can help us in giving Inorder Successor for any node without doing traversal at all.

Following is simple algorithm for finding Inorder Successor of binary tree.

Step 1: Current root itself is NULL, then successor is also NULL.

Step 2: Current root contains value same as key for which we are looking successor.

        2.1: Current root has right child, then left most node of right child is successor.

        2.2: Current root doesn't has right child, then parent of current root is successor.

Step 3: Current root is not the target node for which we are looking successor.

        3.1: Search target node and its successor in left side of tree recursively, and return if found.

        3.2: Search target node and its successor in right side of tree recursively, and return.

Following is implementation of above algorithm in c language.

/*
Algo#2: Inorder Successor in Binary Tree

Description: Find Inorder Successor value in given Binary Tree.
*/
#include 
#include 

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

Node *findLeftMostNode(Node *root)
{
    while (root->left)
        root=root->left;
    return root;
}

Node *inorderSuccessorRec(Node *root, int key, Node *parent)
{
    //Case 1: Current root itself is NULL, then successor is also NULL.
    if (root==NULL)
        return 0;
    //Case 2: Current root contains value same as key for which we are looking successor.
    if (root->data == key)
    {
        //Case 2.1: Current root has right child, then left most node of right child is successor.
        if (root->right)
            return findLeftMostNode(root->right);
        //Case 2.2: Current root doesn't has right child, then parent of current root is successor.
        else
            return parent;
    }
    //Case 3: Current root is not the target node for which we are looking successor.
    else
    {
        //Case 3.1: Search target node and its successor in left side of tree recursively, and return if found.
        Node *left=inorderSuccessorRec(root->left,key,root);
        if (left)
            return left;
        //Case 3.2: Search target node and its successor in right side of tree recursively, and return.
        return inorderSuccessorRec(root->right,key,parent);
    }
}

Node *inorderSuccessor(Node *root, int key)
{
    return inorderSuccessorRec(root,key,NULL);
}

struct node* newNode(int data)
{
  struct node* node = (struct node*)  malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}

int main()
{

  /*
            1
          /   \
        2      3
      /  \    /
    4     5  6
  */
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);

  struct node * succ;

  succ = inorderSuccessor(root, 1);
  printf("Inorder Successor of %d is : %d\n",1,succ->data);

  succ = inorderSuccessor(root, 2);
  printf("Inorder Successor of %d is : %d\n",2,succ->data);

  getchar();
  return 0;
}

Please write comments if you find anything wrong or you want to add something more related to this topic.

Algo#1: Inorder Predecessor in Binary Tree

Inorder Predecessor value for any node X means value of node Y that comes just before node X while doing Inorder traversal. For given tree in figure, inorder traversal (Left Root Right) would be : 4 2 5 1 6 3. We can search inorder predecessor for any node by just looking at this traversal output. E.G. inorder predecessor of node '1' is node '5' because '5' appears before '1' in given traversal.

But in real life we encounter Inorder Predecessor to be search for randomly any node, and if we go by this method of doing inorder traversal first then giving predecessor, it would be inefficient because of its time complexity of O(n) in large trees. So we need some method which can return Inorder Predecessor randomly for any node without doing traversal explicitly in less time complexity.

Luckily inorder traversal follows some pattern which can help us in giving Inorder Predecessor for any node without doing traversal at all.

Following is simple algorithm for finding Inorder Predecessor of binary tree.

Step 1: Current root itself is NULL, then predecessor is also NULL.

Step 2: Current root contains value same as key for which we are looking predecessor.

        2.1: Current root has left child, then right most node of left child is predecessor.

        2.2: Current root doesn't has left child, then parent of current root is predecessor.

Step 3: Current root is not the target node for which we are looking predecessor.

        3.1: Search target node and its predecessor in left side of tree recursively, and return if found.

        3.2: Search target node and its predecessor in right side of tree recursively, and return.

Following is implementation of above algorithm in c language.

/*
Algo#1: Inorder Predecessor in Binary Tree

Description: Find Inorder Predecessor value in given Binary Tree.
*/

#include 
#include 

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

Node *findRightMostNode(Node *root)
{
    while (root->right)
        root=root->right;
    return root;
}

Node *inorderPredecessorRec(Node *root, int key, Node *parent)
{
    //Case 1: Current root  itself is NULL, then predecessor is also NULL.
    if (root==NULL)
        return 0;
    //Case 2: Current root  contains value same as key for which we are looking predecessor.
    if (root->data == key)
    {
        //Case 2.1: Current root has left child, then right most node of left child is predecessor.
        if (root->left)
            return findRightMostNode(root->left);
        //Case 2.2: Current root  doesn't has left child, then parent of current root is predecessor.
        else
            return parent;
    }
    //Case 3: Current root  is not the target node for which we are looking predecessor.
    else
    {
     //Case 3.1: Search target node and its predecessor in left side of tree recursively, and return if found.
        Node *left=inorderPredecessorRec(root->left,key,parent);
        if (left)
            return left;
        //Case 3.2: Search target node and its predecessor in right side of tree recursively, and return.
        return inorderPredecessorRec(root->right,key,root);
    }
}

Node *inorderPredecessor(Node *root, int key)
{
    return inorderPredecessorRec(root,key,NULL);
}

struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}

void deleteTree(struct node* node) 
{
    if (node == NULL) return;
 
    deleteTree(node->left);
    deleteTree(node->right);
   
    printf("\n Delete node: %d", node->data);
    free(node);
} 

int main()
{
  /*
            1
          /   \
        2      3
      /  \    /
    4     5  8
  */
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(8);

  struct node * prede;
  prede = inorderPredecessor(root, 1);
  printf("Inorder Predecessor of %d is : %d\n",1,prede?prede->data:0);

  prede = inorderPredecessor(root, 2);
  printf("Inorder Predecessor of %d is : %d\n",2,prede?prede->data:0);

  deleteTree(root);
  getchar();
  return 0;
}

Please write comments if you find anything wrong or you want to add something more related to this topic.