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.

Design a stack which have O(1) time complexity for finding the minimum element?

This problem can be solved using simple encoding technique. We should use the minimum element to get the next minimum element.Here is a solution which uses O(1) space.PUSH(elem) Operation: In this process we are keeping minimum element on the top of the stack at any given time. And encoding(i.e elem-min) the actual data with minimum and storing. Whenever there is a change in cur minimum data stored in the stack will be negative. This property will be used while poping the elements to find the next minimum. We can define it as shown below. if stack is empty. Store the element twice Else CurMin = POP(); Take difference between elem and Curmin and push it on to stack. Push the least of elem and CurMin on to stack.
POP() Operation: POP process is bit tricky. If minimum is not changing (i.e elements are positive on stack) then return the element + curMin(sitting on stack). If you see a negative stack element then it means there was a shift of curMin (or minimum element is the one which is being popped). In this case we take the current minimum and return it as popped element. We find the new minimum (as current minimum is popped out) by computing curMin-element and push it on top of stack as minimum element. We can summarize it as shown below.curMin = pop();element = pop(); If element is negative then return curMin and push curMin-element on to stack. Else push curMin on to stack and return element + curMin.
FindMin():
This is trivial operation as we are storing minimum element on the top of the stack at any given time. So we pop it and return to the caller. FindMin() steps will be...min=pop();push(min);return min;

How many points are there on the globe where, by walking one mile south, one mile east, and one mile north, you reach the place where you started?

In normal scenario if you think immediate answer will be zero as moving above directions will form 3 sides of a square. But here is the trick. Answer is not zero.
But precisely at north pole every direction is south only. At this point walking south one mile will place u at 1 mile to the south. For there if u walk east then you will form a circlular path centered at north pole. from there if you walk 1 mile north then again you will reach the point where you started. This journey looks like a wedge of pie. Samething holds good at south pole. But here you need to start little more than 1 mile away from south pole as you cannot go to south from the south pole. Then from this point u go 1 mile south. There walk east to form a full circle of 1 mile circumference and then walk 1 mile north. You will reach where u started. on circumference you can do this on infinite number of points. Similarly you can start little bit away from pole from where if you walk closer to pole one mile you will form a circle of circumference 1/2 mile(2 revolutions while walking east), 1/3 mile etc.....
So there are infinite number of points where you can do this.

Does the sun always rise in the east

This is a bit odd question for testing a s/w engineer. But still people ask these Qs. Here is the most appropriate answer i could get.

At the North Pole, there is no such thing as east. Every direction is south. During the six-month polar "day," the sun rises in the south and sets in the south. Similarly at south pole every direction is north.

Does the sun always rise in the east?

This is a bit odd question for testing a s/w engineer. But still people ask these Qs. Here is the most appropriate answer i could get.

At the North Pole, there is no such thing as east. Every direction is south. During the six-month polar "day," the sun rises in the south and sets in the south. The opposite holds for the South Pole, where every direction is north