How to ace the Fibonacci sequence interview question
How to optimize Fibonacci sequence elements calculation in JavaScript
TLDR: Implementing Fibonacci sequence is so common on programming interviews that it is worth to master this problem. Learn about simple optimization method of recursive implementation of this sequence.
Have you ever need to implement Fibonacci sequence calculating program as part of job interview? So many hands up! Let us investigate this simple problem. Shall we start with problem definition?
“Write a function which takes positive, integer number N as argument and returns N-th element of Fibonacci sequence. Use recursive definition of Fibonacci sequence.”
Mathematical definition of Fibonacci sequence looks like this:
fib(n) = fib(n-1) + fib(n-2)
fib(1) = fib (2) = 1
Describing this in English: N-th element of Fibonacci sequence can be calculated by adding previous element and the element before previous one. We also know that two first Fibonacci numbers are both equal 1.
This is quite straightforward problem. We need to translate mathematical definition to code implementation.
Firstly, let us read through problem definition and extract function signature:
Lets take a closer look at mentioned mathematical definition. It has two components: Recurrence definition explains how to compute particular element. Termination condition says when to stop calculating:
fib(n) = fib(n-1) + fib(n-2) // recurrence definition
fib(1) = fib (2) = 1 // termination condition
First working solution
Secondly, let us try to implement recurrence definition:
This is fine code, but unfortunately it won’t terminate. It will go on for ever unless we will add some termination condition:
We achieved first working solution. Success!
Testing
At this point you should consider testing your solution to be confident that it is correct. Ask yourself: does it work for any valid input? Are there any corner-cases? What input might be problematic?
We will omit this step to keep the article short.
Optimization
Usually at this point we should think if we can optimize code in some way. This straightforward definition of Fibonacci sequence have a flaw which might not be easily spotted without analyzing algorithm step by step.
Let us analyze how to calculate value for small N. Let it be 6. In order to calculate fib(6) we need to calculate fib(5) and fib(4). Ok, that seems fine. Lets go on… In order to calculate fib(5) we need to calculate fib(4) and fib(3).
Wait a second.. We need to calculate fib(4) twice! One when calculating fib(6) and one when calculating fib(5). That’s waste of time.
If we went further into calculations it would appear that we would need to calculate some elements multiple times. Lets visualize each elements dependent elements in form of graph:
We clearly see that some nodes are repeated. Lets color the same elements:
Lets summarize our discoveries in a table:
We only checked the situation for N=6, but all of these redundant calculations are getting even worse for bigger N!
Introducing cache
One might wonder then: is it possible to calculate each sequence element only once? What springs to mind is to save each element after calculating it and then always checking if desired element is already known before trying to calculate it.
How to implement this concept? Lets introduce simple Cache. We will introduce table in which we will be keeping values of sequence elements like this:
Obviously we won’t know any values at the beginning so we start with empty array:
Finally, we achieved optimized recursive solution. Great success!
Summary
There are few general things you can learn from this examples. We approached problem in a systematic way. We also used some tools for algorithm analysis.
Approach
We used very general approach to programming problem solving which can be summarized this way:
1. Think about problem definition:
a) What it asks for?
b) Do I understand all terms used?
c) Does it have any information about solution? (e.g. function signature)
2. Reason about small input. Go through solution for them step by step.
3. Derive first working solution, even if it is far from optimal solution.
4. Test your solution. (we skipped this step)
a) Is it correct?
b) Which input values might be problematic?
c) Are there any corner-cases?
5. Try to optimize your solution?
a) Is there some redundancy?
b) Can you come up with simpler formulas?
c) Are some calculation unnecessary?
Tools
We silently used few tools which are useful when analyzing any algorithm:
- Going through simple examples using pen and paper
- Visualizing algorithm workings. Any graph, drawing, plot will do. Humans are very good in finding visual patterns, not so good at arithmetic. To be honest, we are really bad at arithmetic.
- Summarizing some aspects of algorithm in table. Like with visualization tools, it is much easier to spot patterns in table than in sequence of numbers.
Even though Fibonacci sequence is quite simple problem you can use described approach and tools to solve any other programming problem.
