Code Arena

Find single number!!

2014-04-08T21:54:00.001-07:00

Given an array containing integers, where each number occurs three times except for one number which occurs only once, find the number which occurs only once.
Couldnt think of a way to use XOR for this. XOR works fine when all numbers appear twice and only one of them appears once.
But we can still use some bit magic for this question.
Lets consider ith bit of all numbers. If we count the total number of one's in the ith bit for all numbers and later divide this number by 3, we can get the ith bit of the desired number. So lets say if we have total of 7 elements for eg: {10, 13, 10, 13, 10, 4, 13}. Now if we count total number of ones for LSB in the whole array, we will get 3(for 3 13s, for every other number LSB is 0). Now if we find remainder of the count when divided by 3, we will get the LSB of the desired number. Why? Because every other number appears three times, hence all other ones will appear three times and when taking a remainder will cancel out.
We can do the same thing for all 32 bits :). Below is the code.

int singleNumber(int A[], int n) {
    int num = 0;
    int temp = 0;
    for(int i = 0; i < 32; i++)
    {
        for(int j = 0; j < n; j ++)
        {
            if((A[j] >> i) & 1)
                temp ++;
        }
        temp = temp %3;
        num = num | (temp<<i);
        temp = 0;
    }
    return num;
}

Zip of a linked list

2014-02-01T17:44:00.000-08:00

Given a linked list <1, 2, 3, 4, 5, 6>, zip of this linked list is defined as 1, 6 , 2, 5 , 3, 4. And the task is to achieve desired linked list using O(1) space.
This can be performed by a simple algorithm:

Split the list from the middle into two lists. We are splitting the list into two and not creating a new linked list hence maintaining O(1) space
Now we have two lists : 1, 2, 3 and 4, 5, 6. Reverse the second list
This gives us two lists 1, 2, 3 and 6, 5, 4
Now merge the lists picking one node from each list as a time

Below is how we can do the same using STL lists.


list<int> l; //original list
list<int> nl; //new empty list
int size = l.size();

//Step 1 of splitting into two
for(int i = 0 ; i < size/2; i++)
{
    nl.push_back(l.back());
    l.pop_back();
}

//At this point we have 1, 2, 3 and 6, 5, 4
size = l.size();
list<int>::iterator it = l.begin();
it++;
while(i)
{
    l.insert(it, nl.front());
    nl.pop_front();
    i--;
}

Count number of occurences of a number in a sorted array

2013-09-24T22:39:00.000-07:00

We will use the fact that the array is sorted. Hence we can use binary search. The only trick is that we do not stop when we find the first occurrence of the number, but continue doing the binary search to the left and right of that number.

int count(int* arr, int num, int start, int end)
{
    if(start > end)
    return 0;
    int mid = (start + end)/2;
    if(arr[mid] == num)
        return 1 + count(arr, num, start, mid-1) + count(arr, num, mid+1, end);
    else if(arr[mid] > num)
        return count(arr, num, start, mid-1);
    else
        return count(arr, num, mid+1, end);
}

Useful tree functions!!

2012-11-06T21:56:00.000-08:00

1) Check if a given tree is a BST?
Checking that a given binary tree is a BST requires fulfillment of the property that value of root node is greater than all nodes in its left subtree and its less than all nodes in its right subtree.

bool isBST(tree* root,int min, int max)
{
    if(root==NULL)
        return true;
    if((root->data >=min && root->data<max) || (root->data >min && root->data<=max))
        return isBST(root->lchild, min, root->data) && isBST(root->rchild, root->data, max);
    else
        return false;
}

2) Find height of given binary tree.
To calculate height of the tree, we find the height of the left subtree and the right subtree recursively and report the maximum of the two.

int height(tree* root)
{
    if(root==NULL)
        return 0;
    
    return (1+ max(height(root->lchild), height(root->rchild)));
}

3) Is the given binary tree balanced?
To check that a tree is balanced, we check at every node that its right subtree and its right subtree do not differ in height by more than 1. The property should hold true at all levels and for all nodes in order for tree to be balanced.

bool isBalanced(tree* root)
{
    if(root!=NULL)
    {
        int l = height(root->lchild);
        int r = height(root->rchild);
        
        if(abs(l-r)>1)
            return false;
        else
        {
            isBalanced(root->lchild);
            isBalanced(root->rchild);
        }
        return true;
    }

4) Count leaves in a binary tree.
Recursion is pretty similar to height calculation. We find number of leaves in the left subtree and sum that with number of leaves in the right subtree.

int countLeaves(struct tree* root)
{
    if(root==NULL)
        return 0;
    if(root->lchild==NULL && root->lchild==NULL)
        return 1;
    else
        return countLeaves(root->lchild) + countLeaves(root->rchild);
}

5) Given the root node, copy the binary tree.

tree* copy(tree* t1)
{
    if(t1)
    {
        tree* temp = new tree;
        
        temp->lchild=copy(t1->lchild);
        temp->data=t1->data;
        temp->rchild=copy(t1->rchild);
        return temp;
    }
    return NULL;
}

Is there a path from root to leaf that sums up to a value in a binary tree!!

2012-10-24T21:51:00.000-07:00

The problem can be solved using two simple recursive calls. As we need to find a path that starts from root and ends at leaf, we can check at every call if we hit a node that is a leaf and if the sum requirement at that point matches the value of that node, then we declare success. And if any such path exists we return true and hence the 'OR' operator in the return statement.

bool sumPath(node* root, int sum)
{
    if(root == NULL)
        return false;
    if(root->lchild == NULL && root->rchild==NULL && root->data == sum)
        return true;
    return (sumPath(root->lchild, sum - root->data) || sumPath(root->rchild, sum - root->data));
}

Evaluate a parenthesized expression!!

2012-09-07T21:14:00.001-07:00

The problem can be solved by using two stacks. One for the numbers and another one for the operators. When we get a left parenthesis we ignore it. When we get an operand we push it to the number stack and when we get a operator, we push it to the operator stack. When we encounter a right parenthesis, we pop two elements from number stack, pop a operator from operator stack, perform operation on the numbers and push back the result to the number stack.

#include<iostream>
#include<stack>
using namespace std;
int main()
{
    stack<int> val;
    stack<char> op;
    string expression;
    cin>>expression;
    for(int i=0;i<expression.length();i++)
    {
        if((expression[i] - '0' >=0) && (expression[i] - '0' <=9))
            val.push(expression[i] - '0');
        else if (expression[i] == '(')
            continue;
        else if (expression[i] == '-' || expression[i] == '+' || expression[i] == '*' || expression[i] == '/')
            op.push(expression[i]);
        else if(expression[i] == ')')
        {
            if (op.empty() || val.empty())
            {
                cout<<"InCorrect number of paranthesis "<<endl;
                return -1;
            }
            else
            {
                int num1 = val.top();
                val.pop();
                if(val.empty())
                {
                    cout<<"InCorrect number of paranthesis "<<endl;
                    return -1;
                }
                int num2 = val.top();
                val.pop();
                char oper = op.top();
                op.pop();
                switch(oper)
                {
                    case '+' : val.push(num1 + num2);
                    break;
                    case '-' : val.push(num1 - num2);
                    break;
                    case '*' : val.push(num1*num2);
                    break;
                    case '/' : val.push(num1/num2);
                    break;
                }
            }
        }
        else
            continue;
    }
    cout<<val.top()<<endl;
    return 0;
}

Print all possible combinations of strings that can be made using a keypad given a number

2012-06-10T11:21:00.001-07:00

Consider a phone keypad where every number has few english alphabet characters associated with it. When a user types some numbers on screen , print all possible permutations of string possible using the characters associated with those numbers. Example: if 1 corresponds to A B C and 2 corresponds to DEF. Then number "12" might represent any of the following : AD, AE, AF, BD, BE, BF, CD, CE, CF.
The problem is very similar to this problem.
The key steps in writing an this function are:

Initialize a keypad array of strings with alphabets corresponding to each number.
Now one by one choose each of the characters corresponding to the number and recurse.
Make sure to keep a check for the digit 9 as it will have only 2 characters.

string keypad[9] = {"ABC", "DEF", "GHI", "JKL", "MNO", "PQR", "STU", "VWX", "YZ"};

void keys(char* num, char *s, int start, int end)
{
    if(start == end)
    {
        cout<<s<<endl;
        return;
    }
    
    s[start] = keypad[(num[start] - '0' - 1)][0];
    keys(num, s,start+1,end);
    s[start] = keypad[(num[start] - '0' - 1)][1];
    keys(num, s,start+1,end);
    if((num[start] - '0' - 1) < 8)
    {
        s[start] = keypad[(num[start] - '0' - 1)][2];
        keys(num, s,start+1,end);
    }
}

Function to print all permutations of a string!!

2012-06-03T23:59:00.001-07:00

Write a function to print all permutations of a string. Characters in the string do not repeat themselves.
The problem is pretty similar to this problem.
Solution is a simple recursive approach where we call the function again and again once with each arrangement of characters. These arrangements are achieved by swapping start with every other character and calling the function again and again with different values of start.

void perm(string s, int start, int end)
{
    //If we have already reached the end of string, print it
    if(start == end)
    {
        cout<<s<<endl;
        return;
    }
    char temp;
    for(int i=start;i<end;i++)
    {
        SWAP(s[start],s[i],temp);
        perm(s,start+1,end);
        SWAP(s[i],s[start],temp);
    }
}

Unsolved!!

2012-06-02T17:49:00.000-07:00

Here are some questions which I will try in coming days and have not solved them. Will take them of this list as I solve each one of them :).

Given a linked list structure where every node represents a linked list and contains two pointers of its type: (i) pointer to next node in the main list. (ii) pointer to a linked list where this node is the head. Write a function to flatten the list into a single linked list.

You are given an array of integers A[1..n] and a maximum sliding window of size w. Output an array B where B[i] is the maximum in A[i, i+w-1].

You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.

Given a binary matrix of NxN of integers ,return only unique rows of binary arrays eg: 01001 10110 01001 11100 ans: 01001 10110 11100

Given an array of integers like ar[]= {1,3,2,4,5,4,2}. Create another array ar_low[] such that ar_low[i] = # of elements lower than or equal to ar[i] in ar[i+1:n-1]. So the output for above array should be {0,2,1,2,2,1,0}

Reverse a Linked List!!

2012-05-30T20:33:00.000-07:00

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.

2012-05-27T22:40:00.001-07:00

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!!

2012-05-22T15:00:00.000-07:00

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

2012-05-17T18:12:00.000-07:00

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()

2012-05-16T22:44:00.000-07:00

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()

2012-05-07T23:22:00.002-07:00

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()

2012-05-07T21:26:00.001-07:00

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\]

2012-05-07T21:24:00.001-07:00

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()

2012-05-07T21:21:00.000-07:00

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;
}