Mastering the interview: The Fibonacci Sequence in JavaScript

Written by

Walter G.

Published on

May 14 2019

Filed under

Article

One of the most common questions that a developer will get asked during a live coding interview is to give an implementation of the Fibonacci sequence. The main reason being that even if you don't know what the Fibonacci algorithm is, it is still short and simple enough that you can try to figure it out on the spot. And most folks interviewing you, don't particularly want to sit there 20 minutes watching you code. They want a quick 1-5 minute implementation as you talk your way through it.

The following is a breakdown of the Fibonacci algorithm. We'll start with a quick overview and history and end with a simple implementation in JavaScript that anyone can understand.

Overview

The Fibonacci sequence is a number pattern in which each number is the sum of the two preceding ones, starting from 0 and 1. It is naturally occurring in nature and the basis for the growth patterns of many biological living entities, such as certain plants and shellfish. It first appeared in early Indian mathematics as early as 450BC in describing Sanskrit poetic meters and verses. In case you get asked about its origins.

The pattern itself looks like the following and continues forward forever essentially.

1, 1, 3, 5, 8, 13, 21, 34, 55, ...

There are numerous ways with varying degrees of complexity to implement a function that can generate these values. While you'll get extra points if you can come up with the fancier one-line solution, it is isn't necessary really during an interview.

Basic JavaScript implementation

Here is a basic implementation of the sequence. This is probably how most people coding would wind up doing it, if they were looking for a quick solution.

// 1, 1, 3, 5, 8, 13
var result = [];
function fibonacci(max)
{
    var counter = 0;
    var current = 0;

    while(current <= max)
    {
        if (counter==0)
        {
            result.push(1);
        }

        else if (counter == 1)
        {
            result.push(1);
        }

        else
        {
            current = result[counter-1] + result[counter-2];
            result.push(current);
        }

        counter++;
    }
}

What's happening here?

We need 2 things for this work. We need to know which iteration we are currently in, because we are going to be ignoring the first 2 numbers (1 and 1), and we will need to create a variable to keep track of the addition of the 2 previous numbers. We'll also introduce a 'max' value and use this variable as a control, in order to signal when to stop the function from running. Otherwise, it will run forever, and at some point crash your browser.

Once we are past the 2nd "1", that's when we begin to add the 2 previous numeric values and to continuously add that sum to the results array. The function ends when our results has past the max value.

That's a simple implementation that you can use during your coding interviews, along with some history and a quick breakdown of the algorithm. I've asked this question in the past to potential candidates during on site interviews. Some people have frozen in place and did not get past the variable declaration portion. Some people implemented a for loop and couldn't figure out when to stop it. My advice is always to talk your way through it step by step, and to not skip any steps. If you can explain your way through half of the function, I can assume that you will eventually get it. If however, you freeze and don't even declare a single variable, I will probably assume that you are not a programmer. ? Happy Interviews.

Comments

No messages posted yet

Add comment