## CapitalIQ Interview Question

Consultants**Country:**India

**Interview Type:**Phone Interview

The most optimal way here would be to use Dynamic Programming because the subproblems overlap.

F(n) = F(n-1) + F(n-2)

and in next set of iteration:

F(n-1) = F(n-2) + F(n-3).

So, as you can see, there are unnecessary recompuation of same subproblem, which can be avoided by using Dynamic Programming and storing intermediate results in a table. THe normal fibonacci program won't be of much interest since it incurs heavy complexity (exponential factor).

Is this a Joke. No one ask this simple question in the interview.

```
public static int fib(int n) {
if (n < 2) return n;
return fib(n-1)+fib(n-2);
}
```

First of all, this is a very valid interview question because there are various solutions with different complexities.

And for the program you have written, try to invoke fib(-3).

Fibonacci sequence is as follow 0, 1, 1, 2, 3, 5, 8.....

the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two. so the code is easy.

}

- qqfz521 June 19, 2013