## Mastering Most Common Interview Question: Fibonacci Sequence

Different companies can have very different emphasis on algorithms during coding interview. Nevertheless, if I had only 10 minutes to prepare for recruitment meeting, I would most definitely spend it on learning recursive version of Fibonacci sequence - it simply turns up the most often. In this post, I am providing you with “transcript” of the first time I was asked to implement Fibonacci sequence algorithm in Python few years ago. Take a look at the way I was thinking out loud and try to mimic this approach during your job interview **even when different algorithmic task appears!**

**RECRUITER: **Can you write a function, which takes a positive integer **n** as an argument and returns **n**-th element of Fibonacci sequence? So, for example for 6 this function should return 8.

**ME:** Sure! Let me start by defining a function you specified. For now it’ll return a placeholder (-1). I’ll just write first few elements of Fibonacci sequence in a comment to have them in mind. As far as I remember, every consecutive element is a sum of the previous two.

def fibonacci(n): # 0, 1, 1, 2, 3, 5, 8, 13, 21 return -1

### I started with **revisiting definition of the problem and small study of an example**, which I wrote in a comment.

I will implement a solution to a simpler problem - writing Fibonacci sequence algorithm for zeroth, first and second element. Actually, we can omit zeroth since you said, that my function should take a positive integer as an argument. So, below solution will produce bad result for **n **larger than 2. Otherwise it’s fine.

def fibonacci(n): # 0, 1, 1, 2, 3, 5, 8, 13, 21 if n == 1 or n == 2: return 1 return -1 # Good result print(fibonacci(1)) # Good result print(fibonacci(2)) # Bad result print(fibonacci(3))

**Simplifying a problem** is an important step towards its further exploration and better understanding. Recruiters love that!

I think I need a visual assistance. I’ll try to dissect an example with **n** = 6. The output should be 8 (8 is sixth element of Fibonacci sequence). But how exactly was that calculated? Let me quickly draw a simple diagram to find that out. Oh, now I see - tree perfectly fits this use case, so I will probably need to use recursion.

### Don’t forget to** visualize examples using diagrams** like charts, trees, graphs or tables.

To implement recursion we need recurrence definition and a termination step. The latter can be defined by looking at leaf nodes of the tree diagram I drew. Oh, the if statement I’ve written for the first two elements is already a termination step! Let me say out loud what I want my recurrence step to look like: In order to calculate a Fibonacci element at **n**-th position I need to take Fibonacci elements from previous two positions and sum them up. In other words, I need to sum Fibonacci elements from position **n **- 1 and **n **- 2, **which can also be calculated using my Fibonacci function**.

def fibonacci(n): # 0, 1, 1, 2, 3, 5, 8, 13, 21 if n == 1 or n == 2: return 1 return fibonacci(n - 1) + fibonacci(n - 2) # Good result print(fibonacci(1)) # Good result print(fibonacci(2)) # Good result print(fibonacci(6))

## 1 COMMENT

Jacques TremblayFibonacci is always interesting to implement in any language! The implementation can be improved greatly by using a while loop instead of a recursive call. But there is a way to compute the sequence in constant

time using matrices… If you consider the computation of [Fn+2, Fn+1] from [Fn+1, Fn] to be a matrix operation on a vector formed by Fn+1 Fn. The matrix A to use is the following:

1 1

1 0

Giving the system:

Fn+2 = 1 1 Fn+1

Fn+1 1 0 Fn

If one computes the eigen vectors of matrix A and the eigenvalues, the matrix A can be written

as the product of E . L . E(inv) where L is a diagonal matrix containing the eigenvalues of A. E and Einv

are matrix formed by the eigen vectors of A. Then, the computation of F(n) for a large value of n becomes

simply elevating the eigenvalues of A to the (n-2)th power and multiplyng the three matrices together.. Fn

is then the sum of the first row element if the resulting matrix. Doing this is like applying the matrix on the

first two elements of the sequence: [1, 1]. Interesting fact, the eigenvalues of A are the golden ration and 1 – golden ratio. i.e. 1.6018… and -0.618…