Hey!
Have you heard anything about Fibonacci numbers? Solving Fibonacci sequences is one of classical interview tasks. An employer wants to check your algorithmic thinking and problem solving skills.
A little bit explanation before solving...
The Fibonacci sequences is a set of numbers that starts with a one or a zero, followed by a one, and proceeds based on the rule that each number (called a Fibonacci number) is equal to the sum of the preceding two numbers. If the Fibonacci sequence is denoted F (n), where n is the first term in the sequence, the following equation obtains for n = 0, where the first two terms are defined as 0 and 1 by convention:
F (0) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
2 Ways to solve Fibonacci sequences with JavaScript
1. Simple loop
It's the best and fast solving.
const fib = n => {
let prev = 0;
let next = 1;
for (let i = 0; i < n; i++) {
let temp = next;
next = prev + next;
prev = temp;
}
return prev;
}
It's the best variant of solving, but if you want to show that you know something more than loop, for instance...
2. Recursion
Recursion - it's when function call itself until it doesn't.
const fib = n => {
if (n <= 1) {
return n;
} else {
return fib(n - 1) + fib(n - 2);
}
}
Remember this example. You shouldn't do like that. Never!
If on the interview you're asked to solve this task recursively, remember it's a pitfall. Why? Because if you need to count, for example, 55 Fibonacci number, you will see a little bit delay. This solving has O(e^n) notation. For better understanding, if you must wait 1 hour for fib(45), then for fib(46) you will wait 2 hours. 😄
So how can better do that? Follow me. It's better solution using recursion.
const fib2 = n => {
if (n === 0) {
return [0, 1];
} else {
const [prev, next] = fib2(n - 1);
return [next, prev + next];
}
}
const fib = n => fib2(n)[0]
I'm pleasured to share with you ways of solving this task.
If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Twitter or Facebook. Have a nice day!
Top comments (1)
Thanks for the article! For more common Fibonacci Coding Interview Questions check this blog post as well: fullstack.cafe/blog/fibonacci-inte.... Hope it will be helpful.