CareerCup

int fib_number (unsigned int n)
{
int t[2] = {0,1};
if(n == 0U) return t[0];
if(n == 1U) return t[1];
for(unsigned int i = 1; i < n; i++){
t[(i-1)%2] = t[0]+t[1];
}
return(t[(n)%2]);
}

int fibo(int nth,int num1, int num2)
{
if(n==1) return num1;
if(n==2) return num2;
return fibo(nth-1,num2,num1+num2)
}

#include <stdio.h>
#include<alloc.h>
#include<iostream.h>
int is_even(int t){

if(t<0){
t=t*(-1);
}



if(t%2==0){
return 1;
}
else{
return 0;
}
}

int is_odd(int t){

if(t<0){
t=t*(-1);
}

if(t%2==1){
return 1;
}
else{
return 0;
}
}

int swap(int *f, int *s){
int temp;
if((!f)||(!s)){
return -1;
}
temp=*f;
*f=*s;
*s=temp;
return 1;
}

int odd_even(int *k, int f, int l){

printf("enter odd even %d\n",*(k+l));

if(k==NULL){
return -1;
}
else if(*k='\0'){
return 1;
}
else{
while(1){
printf("=======%d\n",*(k+l));

while(is_even(*(k+l))==1){
l--;
printf("l is %d\n",l);
if(l<=f){
return 1;
}
}

while(is_odd(*(k+f))==1){
f++;
printf("f is %d\n",f);
if(l<=f){
return 1;
}
}

printf("swap (%d %d) %d %d\n",*(k+l),*(k+f), l, f);

if(!swap((k+l),(k+f))){
return -1;
}
}

}


}

Cons of recursive approach
1. The OS stack which keep track of function calls may overflow if n is very large

2. In recursive approach if we want to solve F(N) then we need to solve F(N-1) and F(N-2)and in order to solve F(N-1) we have to solve F(N-2) AND F(N-3). So we are solving F(N-2) two times once while solving F(N) and second while solving F(N-1). This is highly inefficient.

Let A = [ 1, 1; 1, 0 ], and we have

(F(n), F(n-1))' = A * (F(n-1), F(n-2))' = A^(n-1)

This can be calculated in O(logn).

private static int fibonacci(int n, int prevans, int ans)
{
if (n==0)
return (ans + prevans);
else
{
return fibonacci(--n, ans, ans + prevans);
}
}

//recursion is costly here.
//following are 2 ways to resolve

/// <summary>
/// FindnthFibonacciNumber
/// </summary>
/// <param name="n"></param>
/// <returns>int</returns>
public static int FindnthFibonacciNumber(int n)
{
int f1 = 0; int f2 = 1; int sum = 0;

if (n == 1)
return 0;

else if (n == 2)
return 1;

else
{
int k = 2;
while (k < n)
{
sum = f1 + f2;
f1 = f2;
f2 = sum;
k++;
}

return sum;
}
}

/// <summary>
/// FindnthFibonacciNumberRecursion
/// </summary>
/// <param name="n"></param>
/// <returns>int</returns>
public static int FindnthFibonacciNumberRecursion(int n)
{
// Recursion way
if (n == 0 || n == 1)
return n;
else
return FindnthFibonacciNumber(n - 1) + FindnthFibonacciNumber(n - 2);
}

I was asked this same question in a Bloomberg interview:

int NthFibonacci(int n)
{
if(n<0) return -1;

int first = 0, second = 1, fib = 0;

if(n == 1) return first;

if(n == 2) return second;

for(int count = 1; count <= n-2; ++count)
{
fib = first + second;
first = second;
second = fib;
}

return fib;
}

int rec(int n)
{
int i=-1,j=1,t=0;
for(k=1;k<n;k++)
{
t=i;
i=j;
j=j+t;
}
return(i+j);
}

The most efficient way is to solve the recurrence function and to compute it without any iteration or recursive call.

One more drawback with the recursive approach apart from the drawback of using the stack is that, here we do a lot of rework in calculating the values for calling the functions. For e.g: while calculating f(5), we calculate values for f(4) and f(3) and while calculating the value of f(4), we again calculate f(3). Thus we calculate the same value again which is nothing but waste of resources. This is actually a problem of dynamic programming.

most efficient is o(1).

Another iterative solution (N>2):

int F(int Nth){
int a=0, b=1;
while(Nth-2){
a=a+b;
a=a-b;
b=a+b;
a=b-a;
Nth--;
}
return b;
}

I messed up this question at bloomberg. However, here is a simple approach.
typedef unsigned long long ull;
ull fib(ull N)
{
ull fibN2,fibN1,fibN;
fibN=fibN1=fibN2=1;

for(ull i = 3; i < N; i++) {
fibN=fibN1+fibN2;
fibN2=fibN1;
fibN1=fibN;
}
// This is as simple as this.
// You can also use matrix multiplication for this purpose.
// Formulae are given in various texts.
return fibN;
}