## Chegg.com Amazon Interview Question

Consultants Software Engineer / DevelopersSeems like this returns the sum of first n numbers. Not even related to fib.

btw, what does a 2 line program mean? Idiotic question.

recursive algorithm,

int get_fib(int n)

{

if (n==1)||(n==2)

return 1;

else

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

end;

}

iterative algorithm,

int get_fib(int n)

{

if (n==1)||(n==2)

return 1;

else

{

prev = 1;

curr = 1;

cont = 2;

while (cont != n)

{

next = prev + curr;

prev = curr;

curr = next;

cont ++;

}

return next;

}

}

stupid question. its a simple Fibonacci Qs and the answer is the Standard answer...I bet even the interviewer can't do it in _2 LINES_ LOL

@Gecko : recursive is good enough, no need to go for iterative...

here is the python code:

```
def fib(n):
prev=0
curr=1
for i in range(n):
curr, prev = curr+prev, curr
return curr
```

we start from 0

fib(0) = 1

fib(1) = 1

fib(2) = 2

fib(3) = 3

fib(4) = 5

etc ....

Better option is to use Matrix method, avoids floating point and the related precision issues.

lol. I think its not asking about squeezing the same code into two line.

I think its asking about Golden ratio.

http://www.ics.uci.edu/~eppstein/161/960109.html

To find the nthFibonacci number, use the following recursive definition :

F0 = 0

F1 = 1

When n is an even number :

Fn = Fn / 2(Fn / 2 + 2 F(n－2) / 2)

When n, modulo 4, is 1 :

Fn = (2 F(n－1) / 2 + F(n－3) / 2)(2 F(n－1) / 2 － F(n－3) / 2) + 2

When n, modulo 4, is 3 :

Fn = (2 F(n－1) / 2 + F(n－3) / 2)(2 F(n－1) / 2 － F(n－3) / 2) － 2

int fib(int N)

- Anonymous August 20, 2009{ return (N < 2)? 1 : fib(N-1) + fib(N-2);}