Problem of the week - Fibonacci

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!

Approach 1

Hint: Recursion

F(n) = F(n-1) + F(n-2), base conditions: F(0) = 0, F(1) = 1

Implementation:

// 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.

Approach 2

Hint: Dynamic Programming

Store the Fibonacci numbers calculated so far and use them to calculate the next input in a single pass.

Implementation

  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.

Approach 3

Hint: Store the last two numbers.

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!

Implementation

  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.

To solve such questions and prepare for coding interviews - log on to firecode.io

Think you have more efficient or better solution? share it in the comments!