Interview Coding Question - Fibonacci

Fibonacci number

Recursive solution

int fib(int n)

{

  if (n < 2)

    return n;

  else

    return fib(n-1) + fib(n-2);

}

Iterative solution 1

int fib(int n)

{

int fibArray [MAXINT], i;

fibArray [0] = 0; fibArray [1] = 1;

for (i = 2; i <= n; i++)

    fibArray [i] = fibArray [i-1] + fibArray [i-2];

return fibArray [n];

}

Iterative solution 2

int fib(int n)

{

  int first = 0, second = 1;

  int i, tempSum;

  for(i = 2; i <= n; i++)

  {

    tempSum = first + second;

    first = second;

    second = tempSum;

  }

  return second;

}

Interview Coding Question - Prime Number

What's Prime Number

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Simplest algorithm but most expensive

bool isPrime(int n)

{

      if (n<=1) return false;

for (int i=2; i < n; ++i)

if (n%i==0)

return false;

return true;

}
If you stop here, you barely can be hired as programmer.

A little bit optimized 

/// If the number can NOT be exactly divided by 2, no need to test 4, 6, 8...

bool IsPrime (int n)

{

if (n <= 1) return false;

if (n % 2 == 0)

return false;

else 

for (int i=3; i < n; i+=2)

if (n%i==0)

      return false;

return true;

}

Further optimization with a theory  

if  is composite (with a and b ≠ 1) then one of the factors a or b is necessarily at most .

bool IsPrime (int n)

{

if (n <= 1) return false;

float sqrt_num = sqrt(n)

for (int i=2; i < sqrt_num; ++i)

if (n%i==0)

return false;

return true;

}

Note
Prime generation algorithm is heavily tested during interview, because it can test the interviewee's basic math knowledge, logical thinking and the sense to chase excellence which are a great programmer requires.
Prime algorithm optimization is a very very deep topic. You are NOT expected to be able to finish it with the highest efficiency algorithm if the position you apply is a junior / medium level software developer. Otherwise the interview will last more than 2 hours, and very likely the interviewer will think you have guessed the question and are prepared.

Reference
http://en.wikipedia.org/wiki/Prime_number

http://program-think.blogspot.com/2011/12/prime-algorithm-1.html

Interview Coding Questions - Linked List

Linked List Data Structure

struct Node;

typedef struct Node *PtrToNode;

typedef PtrToNode List;

typedef PtrToNode Positon

struct Node

{

ElementType Element;

Position Next;

}

  
Algorithm 1 - Reverse a linked list (iterative implementation)   

  

    1     List   Reverse(List   l)   {   

    2     if(!l)   return   l;   

    3     list   cur   =   l.next;   

    4     list   pre   =   l;   

    5     list   tmp;   

    6     pre.next   =   null;   

    7     while   (   cur   )   {   

    8         tmp   =   cur;   

    9         cur   =   cur.next;   

  10         tmp.next   =   pre   

  11         pre   =   tmp;   

  12     }   

  13     return   tmp;   

  14   }   

Algorithm 2 - Reverse a linked list (recursive implementation)   

  1     List   Reverse(list   l)   {   

  2     if(!l   ||   !l.next)   return   l;   

  3       

  4         List   n   =   reverse(l.next);   

  5         l.next.next   =   l;   

  6         l.next=null;   

  7     }   

  8     return   n;   

  9   }