## Posts

Showing posts from September, 2016

### An interesting Interview Question: Fibonacci Sequence

Write a function to calculate the nth Fibonacci Sequence is a common interview question and often the solution is something like   int Fib(int n) {    if(n < 1) return 1;    return Fib(n-1) + Fib(n-2); }   The next question is to ask for n=100, how many items will be on the stack . The answer is not 100 but actually horrible! It is closer to 2^100. take the first call – we start a stack on Fib(99) and one on Fib(98). There is nothing to allow Fib(99) to borrow the result of Fib(98).  So one step is two stack items to recurse.  Each subsequent call changes one stack item into 2 items.   For example 2 –> call [Fib(1), Fib(0)] 3 –> calls [ Fib(2)->[Fib(1), Fib(0)], Fib(1) –> Fib(0) ] 4 –> calls [ Fib(3)->[[[ Fib(2)->[Fib(1), Fib(0)], Fib(1) –> Fib(0) ]], Fib(2)->[Fib(1), Fib(0)], Fib(1) –> Fib(0) ] Missing this issue is very often seen with by-rote developers (who are excellent for some tasks).   A better solution is t