Quant Interview Questions (Interest Rate Strat.)

1) What is the limit of F(n) when n is large, where F(n) is the n-th term in the Fibonacci series?

Ans:
The ratio between consecutive terms, x, approaches the golden ratio phi. Proof: we posit that
F(n) = x^n * F(0) = x^(n-1) * F(0) + x^(n-2) * F(0)
x^n = x^(n-1) + x^(n-2)
x = 0.5 * (1 +- sqrt(5))
The two values are phi and 1/phi, respective.

2) Write functions to compute F(n) and comment on the order of the algorithm.

Ans:
Recursive approach -
int Fib(int n){
if (n = 0) {Fib = 0}
else if (n = 1) {Fib = 1}
else {
Fib = Fib(n-1) + Fib(n-2)
}
return Fib;
}
Order ~ O(phi^n)
Note: alternatively we can store the intermediate values in a cache to reduce redundancy (for example to find F(4) we have to calculate F(2) = F(3-1) and F(2) = F(4-2) twice, which is a waste of time).

Bottom-up approach -
int Fib(int n){
temp1 = 0;
temp2 = 1;
if (n = 0) {Fib = 0}
if (n = 1) {Fib = 1}
for (int i = 0; i <= n; i++){
run_sum = temp1 + temp2;
temp1 = temp2;
temp2 = run_sum;
}
return run_sum;
}
Order ~ O(n)

See here for more interview questions/brainteasers