Ashish Srivastava | @ashishsrtechie | 13 Oct, 2015
This week we're back with one more simple, yet very common interview question.
Fibonacci Series. 0,1,1,2,3,5,……Wiki link.
This is an interview favorite with companies like Oracle, Apple and Microsoft even today. It's often used as a replacement for the famed "Fizz-Buzz" test, and interviewers like to use it as a quick sanity test to check if you're comfortable with the basics of programming. Let's code!
F(n) = F(n-1) + F(n-2), base conditions: F(0) = 0, F(1) = 1
// Base Condition if (n <= 1) return n; return fib(n-1) + fib(n-2);
This has got an exponential time complexity. T(n) = T(n-1) + T(n-2), which makes it inefficient for larger inputs. Also, if you see the implementation, F(n-2) will be calculated for F(n) and also for F(n-1), which is a repetitive work. That’s why the interviewer WILL ask for a better solution.
Store the Fibonacci numbers calculated so far and use them to calculate the next input in a single pass.
f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) { /* Add the previous 2 numbers in the series and store it */ f[i] = f[i-1] + f[i-2]; } f(n) => is the final answer.
This does have an additional space complexity of O(n). The time complexity, however, becomes O(n).
Neat, isn't it? Let's see if we can do something about that space complexity.In the above solution we have used an array to store the output at every step, which increases the space complexity of the problem. Let us avoid that by storing only the previous two fibonacci numbers. After all, you only need the last two numbers to calculate the next number!
int x = 0, y = 1, temp =0; for (int i = 2; i <= n; i++) { temp = x + y; // To Store previous two numbers x = y; y = temp; } return temp;
This approach brings down the space complexity to O(1). This problem is a favorite because it naturally lends itself to successive optimizations.