How to ace the Fibonacci sequence interview question

How to optimize Fibonacci sequence elements calculation in JavaScript

Maciej Twaróg
Oct 17 · 4 min read
Fibonacci sequence in nature

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:

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:

Implementing 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:

Implementing 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:

Graph of elements to compute for N=6

We clearly see that some nodes are repeated. Lets color the same elements:

Graph of elements to compute for N=6 (colorized)

Lets summarize our discoveries in a table:

Table of repeated calculations

We only checked the situation for N=6, but all of these redundant calculations are getting even worse for bigger N!

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:

Example of filled cache

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.

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?

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.

JavaScript in Plain English

Learn the web's most important programming language.

Maciej Twaróg

Written by

Programming computers is my hobby

JavaScript in Plain English

Learn the web's most important programming language.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade