Javascript Problem Solving: Fibonacci Sequence

It should come as no surprise that a Fibonacci Sequence is a common test deployed on candidates during interviews for software or development related jobs. As a front-end developer, I hardly encountered these types of tests as the usual interview question often involved building out UI/UX components or working through a design problem. But it’s all in the interest of learning Javascript on a deeper level.

Typically in a whiteboard scenario, problems like this one are handed to the candidate and they’re asked to show their thought process while solving it. Fibonacci is a common computer science problem, typically introduced to students in the first semester. Since many programmers nowadays are self-taught, a lot of us tend to be blindsided by whiteboard tests. That is not to mention the vast majority of people blank on problems during an interview when they are asked to solve a programming problem while there are a bunch of other people watching.

So, while we’re here and not being faced with a panel of interviewers, let’s talk about Fibonacci and how to go about solving the problem.

What is Fibonacci, Anyway?

Fibonacci is often referring to a number sequence that starts with usually 0 or 1 and each subsequent or following number is the sum you would get from the previous two. So, here’s a Fibonacci Sequence written out:

0
0+1 = 1
1+1 = 2
1+2 = 3
2+3 = 5
3+5 = 8
5+8 = 13
8+13 = 21

And onward. Usually you would be asked to output the sequence up to a certain number. Or to write a function that spits out the sequence when a number is thrown out. So let’s think this one through.

Thinking It Out

  1. Since we know that this is a sequence and if we’re expected to spit out a sequence up to a certain number, we already know we need to use a loop to accomplish that. This loop will test to make sure we’re below or at the specified number and then stop once it reaches that point.
  2. It would be a good idea to utilize arrays in order to hold our initial number sequences and the output of the number sequences.
  3. Finally, it seems deceptively simple that we would have to add the first sequence number to the second sequence number. But if we’re working within arrays and loops, we might have to do some fancy footwork to get the proper array numbers to perform math operations on them.

Writing Our Array and Our Variable

Like with most other problems, I like starting with the easiest thing first and worrying about the rest afterward. The easiest thing for this would be writing the array. So let’s get that out of the way. I’m also going to assume that we don’t need any kind of user input and that we’ll just feed the console the sequence number we want, so we’ll need a variable that will feed how many numbers we wish to have. This trims out some peripheral stuff. Let’s get the array and variable in there, shall we?

var number = 10;

var fibArray = [0, 1];

Super easy. I created a variable called number. Number can be populated with any value. I picked 10, but we can change that to whatever we’d like depending on how long we want our Fibonnaci sequence to be. Next I created an array called fibArray which currently holds our two starting values: 0 and 1.

Writing the Loop

We know that for whatever number’s value is up there, that we need to loop through that many times. So, easy thing out of the way first:

var number = 10;

var fibArray = [0, 1];

for (var i = 2; i <= number; i++) {

}

You probably noticed that I initialized i with a value of 2 instead of the usual 0 or 1. This is because I want it start beyond 0 and 1 when it begins calculating our sequence seeing as 0 and 1 are already taken care of in the fibArray. Now we’re at the technical part. I need to create a math operation that will work to calculate our sequence. Fibonacci numbers are calculated by the first sequence number to the second sequence number.

If we look at what we’ve got so far, I declared fibArray with preloaded 0 and 1. Our loop is going to have to perform a math operation to get the next number in the sequence. It’s going to pull the numbers from the initial values we provided in fibArray. So, I’m going to have to tell fibArray to pull its value in the 0 and 1 position (which, incidentally, are 0 and 1).

My math operation is going to look something like this:

fibArray[i - 2] + fibArray[i -1]

What’s happening up there is we’re going into fibArray and referencing i. What we want is to increment the two numbers for the sequence differently which is where -2 and -1 come in. fibArray[i – 2] is actually referencing the number in the 0 position. And fibArray[i – 1] is referencing the number in the 1 position. This way, as our loop runs through, it increments i to the next value in the array, but will slowly loop forward in the array each time, and each time i will go back two spaces and one space, add them together and return the next number in the sequence. Here’s the code as it stands right now, with the above math operation in place. I’ve added a variable to hold the value from the operation:

var number = 10;

var fibArray = [0, 1];

for (var i = 2; i <= number; i++) {

var addFib = fibArray[i-2] + fibArray[i-1];

}

The Solution

Finally, let’s add this sequence number from our above math operation to our fibArray array. This is done so our loop has the next number for it to work through:

var number = 10;

var fibArray = [0, 1];

for (var i = 2; i <= number; i++) {

var addFib = fibArray[i-2] + fibArray[i-1];
 fibArray.push(addFib);

}

console.log(fibArray);

I added a push method up there to push the resulting number for addFib into the fibArray. Finally, I log fibArray to the console so we can actually see the sequence we get from it and we’re done!


Posted

in

by