Generating the Fibonacci sequence in some form is a popular technical interview problem for employers. One variation of the popular Fibonacci number problem is generating all of the even numbers in the sequence. Here, I’m going to look at two possible ways to do this, using Python and JavaScript. To make things more simple, we are only going to generate the even numbers in the sequence below 4,000,000, and then get the sum of all of those numbers.
What is the Fibonacci Sequence?
Each new term in the Fibonacci sequence is generated by adding the previous two terms. So, for example, starting with 1 and 2, the first 10 numbers in the sequence would be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89
How would we go about generating all the numbers in the sequence?
We could start off, thinking about generating the sequence by doing something like this:
The problem with this, is that we can’t create a variable for every number, so a better solution is, once we get a + b = c, then we would want to reset the value of each of the three variables. So ‘a’ now is set to the value of ‘b’, then ‘b’ is set to the value of ‘c’, etc. That might look something like this:
So the basic idea is that inside some sort of a loop, we want to check and make sure we haven’t hit 4,000,000, then reset the value of a, b and c, and then push c into an array or a list. Then we can get the sum of that array or list.
Enough pseudo code though, lets put some actual code up, and see what that would look like:
Python:
Lets start off exactly like our pseudo code there. I’ll use ‘x’ as my empty array.
x = []a = 1b = 2c = a + b
Next, we’ll use a python while loop to check and make sure c is less than 4000000.
while c < 4000000:a = bb = cc = a + bif c % 2 == 0:x.insert(0, c)
Since we’re only interested in the even numbers, then inside the while loop, we check to make sure it’s an even number, and only then do we insert it into x. Next, we can add the sum of the list, and print the sum in python.
numSum = (sum(x))print numSum
JavaScript:
I want to solve it a little bit differently in JavaScript than we did in Python. I’m going to start off by creating an empty array, and then setting the value of the first two indices in the array:
var fib = [];
fib[0] = 1;fib[1] = 2;
Next, I’ll loop through the array. and generate the fibonacci sequence by selecting the indices I need. In the previous example, we kept re-setting the value of a, b & c each time we went through the array. But in this version, I’m not going to reset any values, but instead do something like this, where I take fib[i] and set it equal to the value of fib[i-2] + fib[i-1], and then push the value of fib[i] into a the array.
for(i=2; i<=50; i++) {fib[i] = fib[i-2] + fib[i-1];fib.push(fib[i]);}
At this point, I have the entire fibonacci sequence, not just the even ones, so I’ll use a second for loop to get the array indices that are below 4,000,000 and also even.
arrUnder4mil = [];for (var i = 0; i < fib.length; i++) {if (fib[i] <= 4000000 && fib[i] %2 == 0) {arrUnder4mil.push(fib[i]);}}
Finally, I’ll get the sum of all the numbers in the array, and log the result.
let fibSum = arrUnder4mil.reduce((a, b) => a + b, 0);
console.log(fibSum);
Conclusion:
Although our JavaScript one is a little bit more round about, both functions solve the problem in only a few milliseconds. My thought is that, for these technical interviews, solving the same problem in two different ways, in different languages helps employers see your versatility and creativity. But most importantly, it showcases your ability to think logically. Let me know if you have any feedback. Thanks!