My new blog for android users

Hi Friends,

I recently started writing my experiments with android. You can find the link below.

http://indiandroidism.blogspot.com/

100 coins dividing into equal heads groups.

Question:
You have 100 coins, 37 of them are heads, rest are tails. Your task is to divide this 100 coins into two groups in which there will be the same number of heads. You are blindfolded and you can flip any number of coins.

Solution:
Pick any 37 coins and flip all of them.

Explanation:
 Lets take a simple case where 5 coins with 3 heads and 2 tails.
HTHHT
Lets take 3 coins randomly. Say first,fouth and fifth lets call it S1. Let remaining coins be S2. So we have 2 groups now
S1(H,H,T) and S2(T,H)
When we flip  the selected set S1 it turns into S1F(T,T,H).  We have only one head in both the sets.

How to select k sample nodes from a unknown sized linked list.?

http://en.wikipedia.org/wiki/Reservoir_sampling can be applied here. Is there any better solution for this problem?

Map reduce implementation of reservoir sampling is discussed in this blog post.
http://had00b.blogspot.in/2013/07/random-subset-in-mapreduce.html

Finding number of on bits (1 bits) given an unsigned integer?

Sol 1:
Simple Iterative solution.(Very slow)

int countbits (unsigned int number) {

int count = 0;

while (number) {

count += number & 0x1u;

number >>= 1;

}

return count;

}

Sol 2:
Faster Solution for 32 bit machines.
compute 16bits then add then to return full number of ones in 32 bit number.

static char ones_in_16bit_num [0x1u << 16] ;
int countbits (unsigned int number)
{
return ones_in_16bit_num [number & 0xffffu] + ones_in_16bit_num [(number >> 16) & 0xffffu] ;

}

given 2 non-uniform ropes (each burns down in 1hr, but not uniformly), how to measure 45 mins

Ignite one rope on both the ends. Ignite the second rope at only one end. When the first rope burns out, it is 30 mins. Then ignite the unburned end of the second rope. When the remaining rope burns out, it is another 15 mins. So it is 45 mins.

Find next number in Sequence

you have a sequence where each number is a multiple of 2 or 5 (so: 2^i * 5^j). Given the beginning of the sequence as 1,2,4,5,8,10,16... and find a algorithm to calculate the next number in the sequence?

Answer:
This answer gives u the pattern to make the sequence. Algorithm would look like this.
1. Make set1 with all powers of 2(i.e 2,4,8,...)
2. Make set2 with all powers of 5(i.e 5,25,125 ...)
3. Make set3 with product of numbers from set1 and set2(i.e 10,20,40,50,80,100 etc..)
Make sure that third set is sorted.
Now display elements from set1 till u find a element less than starting element in set2 or set3. Otherwise display minimum element out of elements from set2 or set3.