Coding Interview Question: Fibonacci Number

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!

Comments

[Alex 👨🏼‍💻FullStack.Cafe]

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.