Saturday, December 31, 2011

Linux Process Managment

Describe how Linux processes states,scheduling & data structures

Useful Links:
http://www.ibm.com/developerworks/linux/library/l-linux-process-management/index.html

The Linux Kernel

Spinlocks vs Semaphores

What is the difference between semaphores and spinlocks.Discuss implementation details also.


In a semaphore when we call the down(struct semaphore *) or down_interruptible(struct semaphore*) is that, when the shared resource is locked ( Note : Rem that the shared buffer cannot be locked only instructions that access can be locked) the down call will put the calling process to sleep . So can this mechanism be applied for all synchronization . A big NO!! . Suppose we r using a semaphore to sync access to a device in a interrupt handler . Can u put the interrupt handler process to sleep ?The interrupt handler will only be wakened after quite a long time . I think you should be able to guess the consequences . So what do we use here ? It’s where the Spinlock kicks in…

The spin lock cannot be put into sleep . It will continuously poll for the processor and it will can be used in process like interrupt handlers . So know with this knowledge which one do we use for Reader/Write problem ???? Take this scenario : Initially the circular buffer is empty and the reader tries to read the data from the buffer . It gets the lock and tries to read from the queue . If it is a spinlock it will not relinquish the processor . So writer process cannot even write the data into buffer . So wat happenns the kernel hangs . The only way is switch off the PC DIRECTLY . No other way . So u must understand how sensitive these issues are and how tough it is to write such high privileged code .


Useful Links:
http://unix.stackexchange.com/questions/5214/what-is-the-difference-between-spin-locks-and-semaphores
http://stackoverflow.com/questions/195853/spinlock-versus-semaphore

Spinlocks

Spinlock is a semaphore inwhich the process spins waiting for the lock thereby requiring busy waiting.
While a process is in its critical section,any other process that tries to enter its critical section must loop continuously in the entry code.

Disadvantages:
1.Wastes CPU cycles
2.The longer a lock is held by a thread, the greater the risk that it will be interrupted by the OS scheduler while holding the lock. If this happens, other threads will be left "spinning" (repeatedly trying to acquire the lock), while the thread holding the lock is not making progress towards releasing it. The result is an indefinite postponement until the thread holding the lock can finish and release it. This is especially true on a single-processor system, where each waiting thread of the same priority is likely to waste its quantum (allocated time where a thread can run) spinning until the thread that holds the lock is finally finished.

Advantages:
They avoid overhead from operating system process re-scheduling or context switching.Hence When locks are expected to be held for short times spinlocks are useful.
1.Implememented in ISRs
2.spinlocks are often used inside operating system kernels.
3.Implemented on multi processor systems where one thread can spin on one processor while another thread performs its critical section on another processor.

Adaptive Mutex:
Most operating systems (including Solaris, Mac OS X and FreeBSD) use a hybrid approach called "adaptive mutex". The idea is to use a spinlock when trying to access a resource locked by a currently-running thread, but to sleep if the thread is not currently running. (The latter is always the case on single-processor systems.


USEFUL LINKS:
http://www.codeproject.com/KB/threads/spinlocks.aspx
http://en.wikipedia.org/wiki/Spinlock







Garbage Collection

Discuss how garbage collectors work & the methods used in garbage collection

Leak or nt ?

char *p=NULL;
p = (char *) malloc(10);
p++;
free(p);
What happens, is there a leak?? are 10 bytes freed??

Advanced linux Programming in C

Discuss linux programming concepts like process creation ,termination and other library details in C

C Storage Classes & Scope

Discuss available storage classes in C and relevent scope details

1.Auto
2.Register
3.Extern
4.Static

Auto is the default storage class for local variables.
 {
     int Count;
     auto int Month;
 }
The example above defines two variables with the same storage class. auto can only be used within functions, i.e. local variables. 


Register is used to define local variables that should be stored in a register instead of RAM. This means that the variable has a maximum size equal to the register size (usually one word) and cant have the unary '&' operator applied to it (as it does not have a memory location).
 {
   register int  Miles;
 }
Register should only be used for variables that require quick access - such as counters. It should also be noted that defining 'register' goes not mean that the variable will be stored in a register. It means that it MIGHT be stored in a register - depending on hardware and implementation restrictions.

C Function Stack, Stack pointer & Frame pointer

Describe the Stack Frame constructed during a function call.Also discuss the stack pointer and frame pointer and difference between them.

Friday, December 30, 2011

Debugger & Memory Debugger

How debuggers work and what are memory debuggers ?

Useful Links:
http://www.alexonlinux.com/how-debugger-works

Syntax Checker in C

Create a syntax checker which reports about common errors like unbalanced paranthesis etc.

Strip trailing blanks & tabs from input line

Write a function to strip trailing blanks and tabs from the input line and not to print any blank lines

sprintf() & snprintf()

Describe the use of sprintf() & snprintf() functions

Fast Multiplication

Discuss the complexities of Multiplication and fast multiplication ( Karatsuba Algo) methods.

http://en.wikipedia.org/wiki/Karatsuba_algorithm


Bluetooth in LINUX

Discuss position of Bluetooth module and its communication with Linux Kernel

Introduction to Bluetooth

Discuss evrything related to Bluetooth

Bluetooth Components

Discuss the components required for a complete Bluetooth Solution.

Thursday, December 29, 2011

Cache Memory

Discuss Working of Cache (Temporal and Spatial locality.Also discuss Write through and write back mechanisms,Set-Associativity etc.)

Point inside a triangle or NOT

How do you determine if a point is
1) inside a triangle
2) outside
3) on one of edge of triangle
4) if the point is one of the points of triangle

Rotate the n*n matrix by 90 degrees

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Example
?
1
2
3
4
5
6
7
8
9
10
11
12
       Example 1                          Example 2
INPUT    >>     OUTPUT      |         INPUT    >>  OUTPUT 
                            |
4                           |             4                                        
                            |
1 2 3 4        1 1 1 1      |     11 12 13 14      41 31 21 11
                            |
1 2 3 4        2 2 2 2      |     21 22 23 24      42 32 22 12
                            |
1 2 3 4        3 3 3 3      |     31 32 33 34      43 33 23 13
                            |
1 2 3 4        4 4 4 4      |     41 42 43 44      44 34 24 14

http://k2code.blogspot.in/2014/03/rotate-n-n-matrix-by-90-degrees.html
http://www.geeksforgeeks.org/turn-an-image-by-90-degree/
http://www.programcreek.com/2013/01/leetcode-rotate-image-java/

System Calls

Discuss System calls and its requirement

In computing, a system call is how a program requests a service from an operating system's kernel. This may include hardware related services (e.g. accessing the hard disk), creating and executing new processes, and communicating with integral kernel services (like scheduling). System calls provide the interface between a process and the operating system.

Useful Links:
http://en.wikipedia.org/wiki/System_call
http://www.tldp.org/LDP/khg/HyperNews/get/syscall/syscall86.html

Page Replacement Algorithms

Describe pros and cons of each page replacement algos.

All about Stack/Heap Space in a program

http://stackoverflow.com/questions/tagged/stack
http://stackoverflow.com/questions/tagged/heap

1.C Program to find direction of stack growth
2.Calculate maximum stack size of a program
3.Check available stack size in C
4.How to detect & prevent possible stack overflow problems in programs
5.Getting maximum frame size of each function compiled by GCC


Bresenham's line algorithm

Discuss Bresenham's Line Drawing Algorithm in computer graphics and also implement tha same in C.

Timer.c

How to time a piece of code ?

Const qualifier in C

Discuss technicalities related to const qualifier in C.How is it different than volatile.

Const Concepts:

const means that something is not modifiable, so a data object that is declared with const as a part of its type specification must not be assigned to in any way during the run of a program.

It is very likely that the definition of the object will contain an initializer (otherwise, since you can't assign to it, how would it ever get a value?), but this is not always the case. For example, if you were accessing a hardware port at a fixed memory address and promised only to read from it, then it would be declared to be const but not initialized.

Taking the address of a data object of a type which isn't const and putting it into a pointer to the const-qualified version of the same type is both safe and explicitly permitted; you will be able to use the pointer to inspect the object, but not modify it. Putting the address of a const type into a pointer to the unqualified type is much more dangerous and consequently prohibited (although you can get around this by using a cast). Here is an example:


#include <stdio.h>
#include <stdlib.h>

main(){
        int i;
        const int ci = 123;

        /* declare a pointer to a const.. */
        const int *cpi;

        /* ordinary pointer to a non-const */
        int *ncpi;

        cpi = &ci;
        ncpi = &i;

        /*
         * this is allowed
         */
        cpi = ncpi;

        /*
         * this needs a cast
         * because it is usually a big mistake,
         * see what it permits below.
         */
        ncpi = (int *)cpi;

        /*
         * now to get undefined behaviour...
         * modify a const through a pointer
         */
        *ncpi = 0;

        exit(EXIT_SUCCESS);
}
As the example shows, it is possible to take the address of a constant object, generate a pointer to a non-constant, then use the new pointer. This is an error in your program and results in undefined behaviour.
The main intention of introducing const objects was to allow them to be put into read-only store, and to permit compilers to do extra consistency checking in a program. Unless you defeat the intent by doing naughty things with pointers, a compiler is able to check that const objects are not modified explicitly by the user.


char *const vs const char *

char c;
char *const cp = &c;
It's simple really; cp is a pointer to a char, which is exactly what it would be if the const weren't there. The const means that cp is not to be modified, although whatever it points to can be—the pointer is constant, not the thing that it points to. The other way round is
const char *cp;
which means that now cp is an ordinary, modifiable pointer, but the thing that it points to must not be modified. So, depending on what you choose to do, both the pointer and the thing it points to may be modifiable or not; just choose the appropriate declaration.

Why should we use const:
Const gives you the ability to document your program more clearly and actually enforce that documentation. By enforcing your documentation, the const keyword provides guarantees to your users that allow you to make performance optimizations without the threat of damaging their data. For instance, const references allow you to specify that the data referred to won't be changed; this means that you can use const references as a simple and immediate way of improving performance for any function that currently takes objects by value without having to worry that your function might modify the data. Even if it does, the compiler will prevent the code from compiling and alert you to the problem. On the other hand, if you didn't use const references, you'd have no easy way to ensure that your data wasn't modified

Changing a const variable in C:

const int x = 10;
int *ptr = &x;
*ptr = 20;
printf ("Value of x is %d\n", x);

Even though the variable x is const the value gets changed with
following warning "initialization discards qualifiers from pointer
target type.And its one of the drawback in c;
But the above gives error in Line 2
saying invalid conversion from const int to int 

typedef operator in C

Discuss the significance of typedef operator in C

typedef is like #define,except that since it is interpreted by the compiler,it can cope with textual substituitions that are beyond the capabilities of the preprocessor.
typedef int (*PFI) (char *,char*);
creates the type PFI for pointers to functon(of two char * arguments) returning int which can be used in contexts like PFI strcmp, numcmp;


Main Advantages of typedef:
1.This is used to parametrize a program against portability problems.If typedefs are used for data types that may be machine dependent only the typedefs need change when the program is moved.One common situation is to use typedef names for various integer quantities then make an appropriate set of choices of short,int and long for each host ,machine.Types like size_t & ptrdiff_t from standard library are examples
2.It provides better documentation for a program-a type called Treeptr may be easier to understand than one declared only as a pointer to a complicated structure.

Useful Links:
http://www.oualline.com/style/c06.html
http://itee.uq.edu.au/~comp2303/Leslie_C_ref/C/SYNTAX/typedef.html
http://msdn.microsoft.com/en-us/library/4x7sfztk.aspx
http://publib.boulder.ibm.com/infocenter/macxhelp/v6v81/index.jsp?topic=/com.ibm.vacpp6m.doc/language/ref/clrc03sc03.htm

Phases of a Compiler

Discuss several phases of a compiler.

Wednesday, December 28, 2011

ENglish phrase of an integer number

Given an integer from 0 to 9.99,999, print an English phrase that describes the integer.

Square Root without using sqrt

Find the square root of a number with out using square root function.

Also calculate square root of floating point number
http://en.wikipedia.org/wiki/Fast_inverse_square_root

Longest Common Subsequence

LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.
It is a classic computer science problem, the basis of diff (a file comparison program that outputs the differences between two files), and has applications in bioinformatics.
Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

http://algorithms.tutorialhorizon.com/dynamic-programming-longest-common-subsequence/
http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

Important Variations:
1. Longest Palindromic Subsequence
http://algorithms.tutorialhorizon.com/longest-palindromic-subsequence/
http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/
2.Longest Common Substring
http://algorithms.tutorialhorizon.com/dynamic-programming-longest-common-substring/
3.

Method 1:Recursion
Consider the input strings “AGGTAB” and “GXTXAYB”. Last characters match for the strings. So length of LCS can be written as:
L(“AGGTAB”, “GXTXAYB”) = 1 + L(“AGGTA”, “GXTXAY”)
2) Consider the input strings “ABCDGH” and “AEDFHR. Last characters do not match for the strings. So length of LCS can be written as:
L(“ABCDGH”, “AEDFHR”) = MAX ( L(“ABCDG”, “AEDFHR”), L(“ABCDGH”, “AEDFH”) )
So the LCS problem has optimal substructure property as the main problem can be solved using solutions to subproblems.

int lcs( char *X, char *Y, int m, int n )
{
   if (m == 0 || n == 0)
     return 0;
   if(X[m-1] == Y[n-1])
     return 1 + lcs(X, Y, m-1, n-1);
   else
     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
Time complexity of the above naive recursive approach is O(2^n) in worst case and worst case happens when all characters of X and Y mismatch i.e., length of LCS is 0.
Method 2:Dyanamic Programming 

int lcs( char *X, char *Y, int m, int n )
{
   int L[m+1][n+1];
   int i, j;
   /* Following steps build L[m+1][n+1] in bottom up fashion. Note
      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
   for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
       else if(X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
   return L[m][n];
}
Time Complexity of the above implementation is O(mn) which is much better than the worst case time complexity of Naive Recursive implementation.

Pending


Subarray with sum 0 or k

Find if there is a sub-array with sum k

Method 1: Positive Numbers only: O(n)
Initialize a variable curr_sum as first element. curr_sum indicates the sum of current subarray. Start from the second element and add all elements one by one to the curr_sum. If curr_sum becomes equal to sum, then print the solution. If curr_sum exceeds the sum, then remove trailing elemnents while curr_sum is greater than sum.
http://www.programcreek.com/2014/05/leetcode-minimum-size-subarray-sum-java/

Method 2: Negative Numbers also covered : Using Map: O(n)
An efficient way is to use a map. The idea is to maintain sum of elements encountered so far in a variable (say curr_sum). Let the given number is sum. Now for each element, we check if curr_sum – sum exists in the map or not. If we found it in the map that means, we have a subarray present with given sum, else we insert curr_sum into the map and proceed to next element. If all elements of the array are processed and we didn’t find any subarray with given sum, then subarray doesn’t exists.

Variation:1:Find if there is a subarray with 0 sum
Method 1:Hashing
We can also use hashing. The idea is to iterate through the array and for every element arr[i], calculate sum of elements form 0 to i (this can simply be done as sum += arr[i]). If the current sum has been seen before, then there is a zero sum array. Hashing is used to store the sum values, so that we can quickly store sum and find out whether the current sum is seen before or not.
Method 2:Recursion
#include<stdio.h>
#include<stdlib.h>
#define SIZE 9
int hasZero(int* A, int len, int prevSum)
{
    if(len == 1)
        return((A[0]+prevSum) == 0);

    int sum = prevSum + A[0];
    if(sum == 0)
        return 1;

    return hasZero(A+1, len-1, sum) | hasZero(A+1, len-1, 0);
}
int main()
{
    int A[SIZE] = {-2, 1, 4, -1, 6, -3, 3, -4, 7};
    printf("hasSum: %d\n", hasZero(A, SIZE, 0));
    getchar();
    return 0;
}
Variation:2
Find the largest subarray with 0 sum
Variation:3
Smallest subarray with sum greater than a given value
http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/

Variation:4
Subarrays of size k that sum up to ssum.
Given an array, subarray size k and a number ssum,
find the number of subarrays of size k that sum up to ssum.

Also,Solve the above problem if the number of sub sequences are to be found given a sub
sequence sum of ssum in an array

Variation:5
Subarray with sum closest to zero
Given an array contains positive and negative values, find the subarray, whose sum is most closed to zero. Require nlogn time complexity.

Fast Fibonacci-DP

Write optmisation techniques for Calculating Fibonacci numbers using

1.Iterative way & Recursive way
2.Memorisation technique
3.Dynamic Programming way
http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

Variation 1: Tiling Problem
Given a “2 x n” board and tiles of size “2 x 1″, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.
http://www.geeksforgeeks.org/tiling-problem/

Variation 2:Count ways to reach the n’th stair [ CCIB ]
There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top.
http://www.programcreek.com/2014/06/leetcode-decode-ways-java/
http://www.geeksforgeeks.org/count-ways-reach-nth-stair/
http://algorithms.tutorialhorizon.com/dynamic-programming-stairs-climbing-puzzle/

Variation 3:Count possible ways to construct buildings
Given an input number of sections and each section has 2 plots on either sides of the road. Find all possible ways to construct buildings in the plots such that there is a space between any 2 buildings
http://www.geeksforgeeks.org/count-possible-ways-to-construct-buildings/

Question 2:
Given a simple program designed to take inputs of integers from 1-1000 and to output the factorial value of that number, how would you test this program? You do not have access to the code.


Method 1:Recursive:
int fib(int n)
{
  if (n <= 2) return n;
  else return fib(n-1) + fib(n-2);
}


Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.
We can observe that this implementation does a lot of repeated work (see the following recursion tree). So this is a bad implementation for nth Fibonacci number.

                         fib(5)
                     /             \  
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)
Extra Space: O(n) if we consider the function call stack size, otherwise O(1).



Method 2:Dynamic Programming
We can avoid the repeated work done is the method 1 by storing the Fibonacci numbers calculated so far.

#include<stdio.h>
int fib(int n)
{
  /* Declare an array to store fibonacci numbers. */
  int f[n+1];
  int i;
  /* 0th and 1st number of the series are 0 and 1*/
  f[0] = 0;
  f[1] = 1;
  for (i = 2; i <= n; i++)
  {
      /* Add the previous 2 numbers in the series
         and store it */
      f[i] = f[i-1] + f[i-2];
  }
  return f[n];
}
int main ()
{
  int n = 9;
  printf("%d", fib(n));
  getchar();
  return 0;
}
Time Complexity: O(n)
Extra Space: O(n)

Method 3:Space Optimised DP:

We can optimize the space used in method 2 by storing the previous two numbers only because that is all we need to get the next Fibannaci number in series.
#include<stdio.h>
int fib(int n)
{
  int a = 0, b = 1, c, i;
  if( n == 0)
    return a;
  for (i = 2; i <= n; i++)
  {
     c = a + b;
     a = b;
     b = c;
  }
  return b;
}
int main ()
{
  int n = 9;
  printf("%d", fib(n));
  getchar();
  return 0;
}
Time Complexity: O(n)
Extra Space: O(1)
Method 4 ( Using power of the matrx {{1,0},{0,1}} )
This another O(n) which relies on the fact that if we n times multiply the matrix M = {{1,0},{0,1}} to itself (in other words calculate power(M, n )), then we get the (n+1)th Fibonacci number as the element at 0,0 in the resultant matrix.
The matrix representation gives the following closed expression for the Fibonacci numbers:
     \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.
#include <stdio.h>
/* Helper function that multiplies 2 matricies F and M of size 2*2, and
  puts the multiplication result back to F[][] */
void multiply(int F[2][2], int M[2][2]);
/* Helper function that calculates F[][] raise to the power n and puts the
  result in F[][]
  Note that this function is desinged only for fib() and won't work as general
  power function */
void power(int F[2][2], int n);
int fib(int n)
{
  int F[2][2] = {{1,1},{1,0}};
  if(n == 0)
      return 0;
  power(F, n-1);
  return F[0][0];
}
void multiply(int F[2][2], int M[2][2])
{
  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}
void power(int F[2][2], int n)
{
  int i;
  int M[2][2] = {{1,1},{1,0}};
  // n - 1 times multiply the matrix to {{1,0},{0,1}}
  for ( i = 2; i <= n; i++ )
      multiply(F, M);
}
/* Driver program to test above function */
int main()
{
  int n = 9;
  printf("%d", fib(n));
  getchar();
  return 0;
}

Time Complexity:
O(n)
Extra Space: O(1)

Method 5 ( Optimized Method 4 )
The method 4 can be optimized to work in O(Logn) time complexity. We can do recursive multiplication to get power(M, n) in the prevous method.
#include <stdio.h>
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);
/* function that returns nth Fibonacci number */
int fib(int n)
{
  int F[2][2] = {{1,1},{1,0}};
  if(n == 0)
    return 0;
  power(F, n-1);
  return F[0][0];
}
/* Optimized version of power() in method 4 */
void power(int F[2][2], int n)
{
  if( n == 0 || n == 1)
      return;
  int M[2][2] = {{1,1},{1,0}};
  power(F, n/2);
  multiply(F, F);
  if( n%2 != 0 )
     multiply(F, M);
}
void multiply(int F[2][2], int M[2][2])
{
  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}
/* Driver program to test above function */
int main()
{
  int n = 9;
  printf("%d", fib(9));
  getchar();
  return 0;
}
Time Complexity: O(Logn)
Extra Space: O(Logn) if we consider the function call stack size, otherwise O(1).

Nth Fibonacci in O(logn) time-DP

We all know the Fibonacci recurrence as F(n+1) = F(n) + F(n-1) but we can represent this in the form a matrix as shown below:


Look at the matrix A = [ [ 1 1 ] [ 1 0 ] ] . Multiplying A with [ F(n) F(n-1) ] gives us [ F(n+1) F(n) ] , so we say that

A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ]

start with [ F(1) F(0) ] , multiplying it with A gives us [ F(2) F(1) ]; again multiplying [ F(2) F(1) ] with A gives us [ F(3) F(2) ] and so on...

A* [ F(1) F(0) ] = [ F(2) F(1) ]
A* [ F(2) F(1) ] = [ F(3) F(2) ] = A^2 * [ F(1) F(0) ]
A* [ F(1) F(0) ] = [ F(4) F(3) ] = A^3 * [ F(1) F(0) ]
..
..
..
..
A* [ F(n) F(n-1) ] = [ F(n+1) F(n) ] = A^n * [ F(1) F(0) ]

So all that is left is finding the nth power of the matrix A. Well, this can be computed in O(log n) time, by recursive doubling. The idea is, to find A^n , we can do R = A^(n/2) * A^(n/2) and if n is odd, we need do multiply with an A at the end. The following pseudo code shows the same.

Matrix findNthPower( Matrix M , power n )
{
if( n == 1 ) return M;
Matrix R = findNthPower ( M , n/2 );
R = RxR; // matrix multiplication
if( n%2 == 1 ) R = RxM; // matrix multiplication
return R;
}
In this manner, by using the magic of DP, we can get the Nth fibonacci number in O(logN).


Detailed Explanation:http://www.codechef.com/wiki/tutorial-dynamic-programming

Question 2:
You are not required to check the factorial value returned each time. Rather first you have to write a routine that gives the correct factorial value for numbers between 1-1000. (There are no efficiency constraints)
Now you need to check for different test cases such as

1) It must return the correct value for the numbers in the range. You do not need to check for each number but can randomly pick 100 numbers (or whatever with the interviewer would be satisfied) from 1-1000 and check for them.

2) Then you must check what it gives for values out of the range and if it crashes or not.

3) You should also check for negative numbers and floating point. In all the cases the code should reject the input and not crash.