Write a function to generate nth Fibonacci number.

This can be done with both iteration and recursion.

Solution #1: Here is an implementation using recursion,

int fib_rec(int n)
{
    if(n == 0)
 return 0;

    if((n == 1) || (n == 2))
        return 1;
    
    return fib_rec(n-1) + fib_rec(n-2);
}

By adding arithmetic operators(+, -, /, *) and parenthesis, make the following expression true: 3 1 3 6 = 8.

Solution: ((3+1) / 3)*6

Write a program to swap odd and even bits of an integer using minimum instructions.

Solution #1: We can mask all the odd bits and shift them by one to right and similarly mask all even bits and shift them by one to the left and then combine the result. Here is the code,

int swapEvenOddBits(int num)
{
return ((num&0xAAAAAAAA)>>1) | ((num&0x55555555)<<1);
}

Write a function to determine the number of bits required to convert int A to B.

Solution #1: Basically, the question asks you to figure out which bits are different in A and B. Example: in case of 32 and 3, answer is 3 as they have 3 bits which are different. Taking a XOR and then counting the no. of 1s is the simplest approach. Here is the code,

void findBits(int a, int b)
{
    int c = a^b;

    int count=0;

    for(;c!=0; c=c>>1)
        count += c&1;

    printf("Number of bits required to convert int A to B is %d\n", count);
}

What does ((n&(n-1)) == 0) checks??

Solution: A number and its predecessor when &ed will result in '0' only when there is just one '1' bit in the number eg. 1000 and its predecessor 0111. So, this condition checks whether the number is a multiple of 2 or not.

Create mirror image of a tree.

Solution #1: A mirror image of a tree is a tree in which left and right children of each node get swapped. This problem has a recursive nature and therefore can be easily solved with recursion. The algorithm will look like this,

- check if  the node is NULL, if yes then return, continue otherwise
- swap left and right child
- repeat for left and right child

Here is the code,

void mirror(node *root)
{
    if(root == NULL)
        return;

    //swap left and right children
    node* temp = root->left;
    root->left = root->right;
    root->right = temp;

    //recursively call on left and right child
    mirror(root->left);
    mirror(root->right);
}

Multiply two integers without using * operator or while/for loop.

Solution #1: This can be done using recursion,

int multiply(int a, int c)
{
    static int b = 0;
    if(c == 0)
        return b;
    else if(c<0)
    {
        b-=a;
        return multiply(a,++c);
    }
    else
    {
        b+=a;
        return multiply(a,--c);
    }
}

void main()
{
    printf("Product = %d\n", multiply(5, -2));
}

3 ants are at 3 vertices of a triangle. They randomly start moving towards another vertex. What is the probability that they don't collide?

Solution #1: Let the vertices of triangle be A, B and C. Now, each ant has two path options eg. the ant at A can go either A->B or A->C. So, there are eight scenarios possible for ants movements(2*2*2). Out of these eight scenarios, there are two where there will be no collision: A->B, B->C, C->A or A->C, C->B, B->A. So the probability of no collision is 2/8 = 1/4.

Given a cake(cuboid) with a rectangular piece cut from it(any size or orientation), how would you divide the cake into two equal halves by a single cut of knife.

Solution #1: Consider a plane perpendicular to the cake and passing through the center of the cake. Now, no matter at what angle you keep this plane at, it will divide the cake in two equal halves. So, the point is, a perpendicular plane passing through the center of a cuboid will always divide it into two equal halves. Now, if we connect centers of cake and rectangular piece and run our knife through that line we will cut both of them in two equal halves giving us two equal halves of cake.