Coding Interview Question: Fibonacci Number

nazmeln — Mon, 08 Jun 2020 05:57:06 +0000

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!

DEV Community: nazmeln

Coding Interview Question: Fibonacci Number

2 Ways to solve Fibonacci sequences with JavaScript

1. Simple loop

2. Recursion