Pointer: What this means? int * (*(*ptf)(int))(char)

How can you detect a Cycle in a Linked List?

Constraint 1 : List is read-only, and you cannot mark elements.
Constraint 2 : There is limited amount of memory
Constraint 3 : The list is arbitarily long

Best Solution: (http://ostermiller.org/find_loop_singly_linked_list.html)

Catch Loops in Two Passes
O(n) time complexity

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}

Give Me a String at Random from THIS File

Constraint:
1) You can make only one sequential pass through the file.
2) You may not store any additional information like a table of offsets.

I would like to receive the answers from you all. After receiving answers from you i will post the answer.

PS: Seems this question also asked in Microsoft Inverview.

--------------------------------------------------------------------

Solution: ( Taken from a book, if anyone know best solution, please post comment )

The basic technique is to pick survivors, and recalculate as you go along. This is so com-putationally inefficient that it's easy to overlook. You open the file and save the first string. At this point you have one candidate string with a 100% probability of picking it. While remembering the first string, you read the next string. You now have two candidates, each with a 50% probability. Pick one of them,save it, and discard the other. Read the next string, and choose between that and the saved string,weighting your choice 33% toward the new string and 67% toward the survivor (which represents the winner of the previous two-way selection). Save the new survivor.

Keep on doing this throughout the entire file, at each step reading string N, and choosing between that(with probability 1/N) and the previous survivor, with probability (N - 1)/N. When you reach the endof the file, the current survivor is the string picked at random!

Determine if a Variable is Signed or Not?

I hope you thought the below answer:

if (Var >0 )
signed
else
un-signed.

If so, your answer is wrong. Because, once more check the question carefully. It is not asking variable value is signed/ signed or negative/ postive. It is asking type's sign.

Example, type 'char' it has both 'sighed char' and 'unsigned char'. How do we know? Thanks to the 2's complement, using which we can find it.

Before saying the way, let me explain that, we cant use function for this: why? because if we use function, the type of the variable is defined, but our purpose is to find for any given type. So, we use Macro for it.

If we use macro, we can find the sign type, in two cases:

If the argument is value: (thanks to 2's complement)
#define IS_SIGNED(__VAR__) ( ( __VAR__ > 0 ) && ( ~__VAR__ > 0 ) )

If the argument is type: (thanks to typecasting)
#define IS_SIGNED(__TYPE__) ( (__TYPE__)0 - 1 > 0 )

PS: This question is asked in a interivew for recruiting to Microsoft.

How is a Library Call Different from System Call?

Answer: Simply, Library calls are part of the language/ application, system calls are part of the Operating System.

How: A system call gets into the kernel by issuing a "trap" or interrupt.

Below is the versus between these two calls:

1. Example, the C Library is same on every ANSI C implmentation. System calls are different in each OS.
2. Library call is a call to a routine in a library. System call is a call to the kernel for a service.
3. Library call are linked with user program. System call is an entry point to the OS.
4. Library calls are executed in user address space. System calls are executed in kernel address space.
5. Library calls are counted as part of "user" time. System calls are counted as part of the "system" time.
6. Library calls has the lower overhead of the procedural call. System calls have higher overhead context switch to kernel and back.