Rotate an array of integers.

Simple one but little tricky.
Implement a function something like RotateArray(int array[], int nLen, int rotateBy), that will rotate the array by the given ammount.
For ex array is 1,2,3,4,5,6,7,8 and RotateArray(array, 8, 3) (rotateBy is 3) so afterthe function call the arry sould look like: 6,7,8, 1,2,3,4,5
..

Ok here goes my solution( O(n) ):

void RotateArray(int arr[], int len, int rotateBy) {
int i = 0;
int j = 0;

rotateBy = rotateBy%len;
do {
for (i = 0;i < rotateBy; i++) {
EXCHANGE(arr[j+i], arr[len-rotateBy+i])
}
j += i;
} while(j < len-rotateBy);
}

Classic 2 egg problem!

Picked up from http://classic-puzzles.blogspot.com/2006/12/google-interview-puzzle-2-egg-problem.html
Problem statement you can get on the above link. Now task is to generalize it for N story building and E eggs.

Find the mid point of a link list and delete a node(given the pointer to this node) from a very long circuilar link list

The are just to warm you up..
First one is to find the middle element in the link list!
Hint: think about 2 pointers.
Second one is , delete a node P(given is the pointer to P) without traversing list to get to the previous node.
Hint: you shouldn't need one :)

Convert a tree into a liked list where nodes in the linked list represent level order traversal.

Now a simpler one:
For ex. if tree is
.............|1|..............
............./..\..............
.........|2|.... |3|..........
....... / \...... / \..........
.... |4|..|5| ..|6|...|7|....

Make a list like 1-->2-->3-->4-->5-->6-->7.

Given a number, find a number just grater than the given number and having same no of 1s.

Find the lowest common ancestor of two given nodes in a binary tree.

Counting No of ones in the binary representation of a number.

Approach 1:
Lets say the number is n. If you do n&(n-1) it will change the rightmost one in the number to zero.
int i = n?1:0;
while(n = (n & (n-1))) i++;


Approach 2:
If we are given little more memory, we can keep an array of 256 elements, value of each element being the no of ones in the index. for ex. table[0] = 0; table[1] = 1; table[2] = 1; table[3] = 2; etc.

So no of ones in a 4 byte integer n will be,
no_of_ones = table[n&0xff] + table[(n>>8)&0xff] + table[(n>>16)&0xff] + table[(n>>24)&0xff];

Approach 3:
lets say x is another no whose binary representation is 01010101.(or of this pattern)
now if we perform the operation
n = n&x + (n>>1)&x;
Now each 2 bits block in n 'll give no of ones presented in that block in the initial value of n.For ex.
00 --> there was no 1 in these two bit positions.
01 --> there was only one 1 in these two bit positions(irrespective of the place of that 1).
10 -->both of these positions were having 1.
lets take an example (...do the home work).

Now lets say y is another no whose binary representation is 00110011.
perform the same operation
n = n&y + (n>>2)&y;
similarly if we look at four bits blocks in n, each block 'll give no of ones presented in that block in the initial value of n. For example 0010 -> there were two 1s in this block.

so keep doing this until you get the size of one block equal to size of the number given.
For a 4 byte integer(n) no of ones are m
m = (n & 0x55555555) + ((n>>1)&0x55555555); [0x55555555 - >32 bit no of 01010101.. pattern]
m = (m & 0x33333333) + ((m>>2) &0x33333333); [u know where from i got 0x33333333]
m = (m &0x0f0f0f0f) + ((m>>4) & 0x0f0f0f0f); [same logic goes on]
m = (m &0x00ff00ff) + ((m>>8) & 0x00ff00ff);
m = (m & 0x0000ffff) + ((m>>16) & 0000ffff);

now m is the no of ones present in the given number.
So for a number having size 2^x bytes, x+3 steps are needed.
Note: It just counts the number of ones in the binary representation, for signed integers the binary representation is machine dependent. For ex -1 in two's compliment form written as all ones.