In this video, we're going to look at a classic coding challenge--an interview challenge called Find the Fibonacci Numbers!
Video Transcription
Hello. My name is Brian McClain. I'm an instructor of JavaScript and Python programming at Noble Desktop in New York City. In this video, we're going to look at a classic coding challenge--an interview challenge called Find the Fibonacci Numbers. Part of the challenge is to see if you actually know what a Fibonacci number is, so let's make sure we know about that before we get started.
Over here we can see that a Fibonacci number is a sequence of numbers where each number is the sum of the previous two numbers. So if the number is 5, the previous two numbers are 2 and 3. When the number is 21, the previous numbers are 8 and 13. And what's really interesting about this is that the current number divided by the previous number approaches a ratio of 1.618 to 1, which is called the Golden Ratio and is encoded in nature.
We start with these little squares: 1, 2, 2, 3, 5, 8, 13, 21. If you draw a curved line through this whole thing, you get a spiral--classic conch shell spiral, which is encoded in nature,: in hurricanes, in galaxies and conch shells, in the spin of subatomic particles--and in art. The ancients knew about the golden ratio and the numeric sequence.
That's the Parthenon, whose width and height are in the Golden Ratio. It is pretty interesting-- something worth learning more about, reading up on--and you definitely want to know how to implement finding Fibonacci numbers and generating a sequence of them because it is a classic coding challenge.
So, what they would typically do is give you a starter number. They would say: Given the first two Fibonacci numbers--or the first 3 or 4--find the nth, 20th, 30th in the sequence. So if they're giving you the first 2, first thing you do is you make an array of those givens and then we set up a loop. In the loop, we need to add up the current value plus the next value, and then take the sum of that and add that as a new item in the array.
We've already got 2 items in the array, meaning if we're trying to get the 20th item, that loop needs to run 18 times. So i equals 0, i is less than 18, i plus-plus. And every time through we'll say let nextFibo -- we need a new fibo -- it's going to equal the current item: fibos[i], plus the next item, which is fibos[i+1]. And then we take that item and we push it--append it--to the end of the array. To see if it works, we can say console.log fibos--the entire array.. And there it is, all the way up to 4181. That's the 20th value.
Now, you do need to be careful: always give them exactly what they want. They're very finicky in coding interviews. They like you to follow instructions. If they say: Find the 20th fibo, don't get them all 20--give them the 20th, which would be the last one. So, all we need to do now is just get the last item in the array, which you can always get as array-dot-length, minus one: (array.length-1). The length is 20, but the last item is 19, because the indexing begins at zero. So now we don't want to give them all of 20--we just give them the one that they ask for: 4181.
Another thing to do is to be a little bit dynamic. You don't really want to put an 18. What you would do is say: Okay, we want the 20th fibo. We'll set a variable, target, equal to 20 and another variable, iterations, which equals target, minus the length of the starter fibos array, which is 2. The iterations variable equals 18, and we need to iterate 18 times, so we put iterations in the loop--not the hard-coded 18. It is typically better to dynamically generate such values--and not just type an 18. The reason for using a dynamic value is what if they said: Okay, here's the first 4 values.. Then fibos length is 4, target 20 minus 4 is 16. By using a variable in the loop, the value automatically updates and only runs 16 times. So, for that reason you want to avoid hard-coded values. Come up with a variable that expresses how many times you need that loop to run, and the interviewer will like that better. It's always better to be dynamic instead of static in your code.
Well, that concludes this presentation on how to solve the Fibonacci number for a coding interview challenge. I hope you have enjoyed this. My name is Brian McClain. I am with Noble Desktop in New York City, where we teach Fullstack JavaScript. We have a bootcamp for that, and we also have a bootcamp for Python Data Science--and many other excellent courses that are available in person, on-site, and also live online. Until next time. Thanks again.