Reverse a Linked List!!

Iterative version

void reverse()
{
    if(head == NULL)
        return;
    list *first = NULL;
    list *second = head;
    list *third = second->next;
    while(third!=NULL)
    {
        second->next=first;
        first = second;
        second = third;
        third = third->next;
    }
    second->next = first;
    head=second;
}

Recursive version

void rReverse(list *n)
{
    if (n == NULL)
        return;
    if(n->next ==NULL)
    {
        head = n;
        return ;
    }
    rReverse(n->next);
    n->next = n;
}

Print given string in all combinations of uppercase and lowercase characters.

Given a string we need to print the string with all possible combinations of the uppercase and lowercase characters in the string.
So given a string "abc", we need to print the following:
ABC
ABc
AbC
Abc
aBC
aBc
abC
abc
Solution is a simple recursive approach where we call the function again and again once with a character in lower case and another time with the same character in upper case. The code is similar to what we would write for all permutations of a string.

void lowerUpper(char *s, int start, int end)
{
    if(start == end)
    {
        cout<<s<<endl;
        return;
    }
    //Change next character to upper case
    s[start] = toupper(s[start]);
    lowerUpper(s,start+1,end);

    //Change the same character as changed earlier to lower case
    s[start] = tolower(s[start]);
    lowerUpper(s,start+1,end);
}

Level Order in a Binary Tree!!

Write a function to do level order in a binary tree with a slight modification. We need to print each level's data in a separate line.
The key steps in writing such a level order function is to identify where each level ends.

In order to do that we follow the following steps:

• We use a dummy node to identify a level end and put a dummy node as soon as we are done reading that level.
• First we enter root in the queue. As root is the only node at its level, we enter a dummy node after it to signal end of level.
• So when we read back nodes from queue, as soon as we see a dummy node we know that this level has ended
• When we remove a node from queue, we enter all its children in the queue.
• And as soon as we encounter a dummy node(signaling end of current level), we enter another dummy node in the queue(this signals that we have encountered all nodes in previous level and entered their children in the queue, so this level ends here).
• As we need to print each level in new line, we enter a new line when we see a dummy node

Consider Node to be a class having 3 members, a left and right Node pointer and an integer data field and all members are public.

void printLevel(Node* root)
{
    queue<Node*> q;
    Node *dummy = NULL;
    if(root == NULL)
        return;
    //Enter root in the queue
    else
    {
        q.push(root);
        q.push(dummy);
    }
    //If queue is empty then we are done.
    while(!q.empty())
    {
        Node* temp = q.front();
        q.pop();
        //If its a dummy node
        if(temp == NULL)
        {
            cout<<endl;
            q.push(dummy);
        }
        //Else enter node's children in the queue
        if(temp->left!=NULL)
            q.push(temp->left);
        if(temp->right!=NULL)
            q.push(temp->right);
        //Print out node's data.
        cout<<temp->data<<" ";
    }
}

Check if string is valid IPv4 ip address

Given a string, we need to print whether the string is a valid IPv4 ip address or not. For example, 12.2.3.4 is valid IP address and 1222.2.22.33 is not.
The key steps in writing an verifyIP function are:

• Length of the string should be less than equal to 15. As each sub part of the IP can be at max 3 digits and we can have at max 3 dots.
• The string should have 4 parts separated by 3 dots.
• Each part should be greater than 0 and less than 256.

void verifyIP(char *s )
{
    int count=0;
    char *str = new char[strlen(s)];
    strcpy(str,s);

    //Check if length of string is greater than 15.
    if(strlen(str)>15)
    {
        cout<<"Not an IP Address"<<endl;
        return;
    }
    
    char *ip=strtok(str,".");
    
    while(ip!=NULL)
    {
        count++;

        //Check that each subpart is less than 256
        if(atoi(ip)>255)
        {
            cout<<"Not an IP address"<<endl;
            return;
        }
        ip=strtok(NULL,".");
    }

    //Check that we have 4 parts in the ip
    if(count==4)
        cout<<"Correct IP Address"<<endl;
    else
        cout<<"Not an IP Address"<<endl;
}

Commafy()

Given a number, convert it to a string and put commas in it after every 3 digits. So given a number say 100054, function should return 100,054 or for a number like 3040005, function should return 3,040,005.
The key steps in writing an commafy function are:

• Check if number is 0. In this case return string "0".
• Check if number is less than zero. Save this information in a variable and make the number positive.
• Extract each digit from the number and add a comma after every 3 digits.
• Make sure to append '-' sign before returning result if the number was negative.
• Remember to reverse the string before returning as we extracted digits LSB first and hence generated string is reverse of expected

const char* commafy(int num)
{
    char *text = new char(10);

    //Check for num == 0
    if(num==0)
        return "0\0";

    int i=0, sign = 1, count = 0;
    
    //Check if number < 0, Save this info in variable sign and make the number positive
    if(num<0)
    {
        sign = -1;
        num = num*-1;
    }
    
    //Extract each digit from right and add comma after every 3 digits.
    while(num>0)
    {
        count++;
        if(count >1 && (count%3 ==1))
        text[i++] = ',';
        
        text[i++] = '0' + num%10;
        num=num/10;
        
    }
    
    //Add '-' if number was negative.
    if(sign == -1)
        text[i++] = '-';
    
    //Add null terminator
    text[i] = '\0';
   
    //Reverse string before returning 
    int len = strlen(text);
    for(int i=0;i<(len/2);i++)
    {
        char temp = text[i];
        text[i] = text[len-i-1];
        text[len-i-1] = temp;
    }
    
    return text;
}

Implement isNumber()

The code is similar to atop but here we also need to check if number is a double. We need to make sure that the string has at most one decimal point.
The key steps in writing an isNumber function are:

• Check for sign(-) after we've checked for whitespace
• Check if each character lies between 0 & 9
• Make note of first decimal encountered.
• Return false if we encounter a second decimal point
• Return false as soon as we see a non numeric character
• Return true otherwise.

bool isNumber(string toTest)
{
    int index =0, decimal = 0;

    //Checking for sign
    if(toTest[index] == '-')
        index++;
    
    while(index<toTest.length())
    {
        int num = toTest[index] - '0';

        //Check for numerical digit
        if(num >=0 && num <=9)
        {
            index++;
            continue;
        }

        //Check if character is a decimal point and if its the first decimal point.
        else if(toTest[index] == '.')
        {

            //Number cannot have 2 decimal points so return false.
            if(decimal)
                return false;
            else
                decimal = 1;
            index++;
        }
        else
        return false;
    }
    return true;
}

Implement strtok()

strtok takes in a string and one or more tokens, and it returns a substring which is split using all the tokens provided. The tricky part is that once you call strtok with a string, next time you can call it and pass NULL instead of any string and it will assume the string you passed in previous call.
The key steps in writing an atoi function are:

• Make a static copy of the string passed into the function for reuse on next function call.
• If new string is passed to function, make a copy of it else reuse the last sent string.
• Check for tokens in the string to split on. Make sure to keep track of end of string.
• Update the saved copy of string as well as the string passed into the function.

char* new_strtok(char* str, const char* tokens)
{
    //Making a static string to be used again on next function call.
    static char *temp;
    
    //If string passed to function is not null, copy it to our static variable
    if(str!=NULL)
    {
        temp=(char*)malloc(strlen(str));
        strcpy(temp,str);
    }

    //If the string passed is NULL and even the copy is NULL, we are done and return NULL.
    else if(temp==NULL)
    return NULL;

    //If only the string passed is NULL and the copy still has data, work with it.
    else
    {
        str=temp;
    }

    int chars=0, len = strlen(tokens), flag=0;
    
    //Run the loop till we find a token or our copy is fully parsed.
    while(*temp)
    {
        for(int i=0;i<len;i++)
        {
            if(*temp==tokens[i])
            {
                if(chars==0)
                {
                    flag=1;
                    str++;
                }
                else
                {
                    temp++;
                    str[chars]='\0';
                    return str;
                }
            }
        }
        if(flag==0)
            chars++;
        temp++;
        flag=0;
    }
    temp=NULL;
    str[chars]='\0';
    return str;
}

\[x^y\]

Implement a function to calculate exponentiation x^y quickly. x and y are assumed to be integers.

The key steps in writing an exponentiation function are:

• Return 1 if exponent(power) is 0 because \[x^0 = 1\]
• Return x if exponent(power) is 1 because \[x^1 = x\]
• Check if exponent is <0. If it is, then call the function again with 1/x and -y because \[x^{-y} = 1/x^y\]
• Call function again using x*x and y/2 if exponent is even. Say y = 4, we can write \[x^4 = [x^2]^2\] which is essentially calling function again using x*x and y/2.
• If exponent is odd, say y = 2n+1, we can write \[x^y = x^{2n+1} = x * x^{2n}\]Now 2n is even and we can use the even case again by just multiplying x to it.

int power(int x, int y)
{
    if( x == 0)
        return x;

    //Checking if exponent == 0
    if(y==0)
        return 1;

    //Checking if exponent == 1
    else if(y==1)
        return x;

    //Checking if exponent < 0
    else if(y<0)
        return power(1/x, -1*y);

    //Checking if exponent is even and calling function again using x*x and y/2
    else if(y%2==0)
        return power(x*x, y/2);

    //Checking if exponent is odd and calling function again by making exponent even by taking out one x and multiplying it separately and then using the even case again. 
    else
        return x*power(x*x, y/2);
}

This method runs in O(log y) time.

Implement atoi()

The key steps in writing an atoi function are:

• Check for whitespace at the start of the string
• Check for sign(-) after we've checked for whitespace
• Check if each character lies between 0 & 9
• Break as soon as we see a non numeric character
• Make sure to multiply by sign before returning result

int atoi(const char *text)
{
    if(text==NULL || strlen(text)==0)
    return 0;
    
    int len = strlen(text), i = 0, sign = 1, num = 0;
    
    //Checking for whitespace
    while(text[i] == ' ' || text[i] == '\t' || text[i] == '\n')
    i++;
    
    //Checking for sign
    if(text[i] == '-')
    {
        sign=-1;
        i++;
    }
    
    //Checking for numeric characters
    while(i<len)
    {
        if((text[i] - '0') >=0 && (text[i] - '0') <=9)
        {
            num = num*10 + (text[i] -'0');
            i++;
        }
        //Stopping when we see non numeric character
        else
        break;
    }
    
    // multiply the number by sign before returning
    return num*sign;
}