May 282017
 

We discussed Insertion sort in detail earlier. This post shows the recursive implementation of Insertion Sort. Continue reading »

Apr 262016
 

Given a string, print the variation of string as shown below

Input String: ‘hat’

  • Replace one character with numeric one(‘1’): ‘1at‘, ‘h1t‘, ‘ha1
  • Replace two characters with ‘1’ each: ‘11t‘, ‘h11‘, ‘1a1
  • Replace three characters with ‘1’ each: ‘111

In all the strings above, wherever the numeric characters are consecutive, add them. So ’11t’ will become ‘2t’, Similarly ‘111’ will become ‘3’. So the final output will be

hat ha1 h1t h2 1at 1a1 2t 3

Continue reading »

Jan 172013
 

We discussed problem of Tower of Hanoi earlier and written a recursive function to solve the problem, Recursive functions take lot of extra memory (New activation record for each call on the stack) (A detailed analysis of recursion is done in this post of mine).

Todays question is to write a Non-recursive function to solve problem of Tower Of Hanoi.

The function should not take more than O(n) time (n = number of Moves actually required to solve the problem) and O(1) extra space.

The signature of the function will be

/* The three char represents the characters representing three rods 
 * and n is the number of discs (initially in s) 
 */
 void towerOfHanoi(char s, char d, char e, unsigned int n)

Continue reading »

Aug 072012
 

We have already seen the problem to reverse the words in a string, in the solution to that problem we have also written function to reverse the string. That was a non-recursive (iterative) function. Write a recursive function to reverse the String.

For example: If the String is “ABCD” then the output should be “DCBA“.

Before getting to the solution, please note that a non-recursive solution is always better than a recursive solution in terms of its time and space complexities. To know more about recursion refer this post.
Continue reading »

Jun 122012
 

Given the following structure of Node of the Linked List:

    struct Node{
        int data;
        Node *link;
    };

What is the purpose of the below function

    void myFun(Node* head)
    {
        if(NULL == head){ return; }

        printf("%d  ", head->data); 

        if(head->link != NULL )
            myFun(head->link->link);

        printf("%d  ", head->data);
    }

Continue reading »