JavaScript Interview Question: Fibonacci

fibonacci.js

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Write a program to find a fibonacci number.
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

// * * * * * * * * * * * * * * * * * * * * * * * * * * *
// Iterative solution
// O(n) Linear Runtime Complexity
// This is an alternative approach to solving fibonacci 
// without recursion. However, this shoudn't be the 
// final answer in an interview setting.
// * * * * * * * * * * * * * * * * * * * * * * * * * * *

function fibonacci(n) {
  const arr = [0, 1];
  
  for (let i = 2; i <= n; i++) {
    let num1 = arr[i - 1];
    let num2 = arr[i - 2];
    arr.push(num1 + num2);
  }
  
  return arr[n];
}

console.log('Iterative solution', fibonacci(5));


// * * * * * * * * * * * * * * * * * * * * * * * * * * *
// Recursive solution
// O(2^n) Exponential Runtime Complexity
// Using recursion, we can solve this problem as shown
// below. However, this is highly inefficent as it becomes
// extremely slow as the value of n grows.
// * * * * * * * * * * * * * * * * * * * * * * * * * * *

function fibonacci(n) {
  //Base case - exit when n <= 1.
  if (n <= 1) {
    return n;
  }
  
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log('Recursive solution', fibonacci(5));


// * * * * * * * * * * * * * * * * * * * * * * * * * * *
// Recursive solution with memoization. 
// O(n^2) Exponential Runtime Complexity
// This solution is more efficient than the other two.
// Memoization is the answer to present in an interview
// setting.
// * * * * * * * * * * * * * * * * * * * * * * * * * * *

//Slow version of fibonacci.
function slowFib(n) {
  //Base case - exit when n <= 1.
  if (n <= 1) {
    return n;
  }
  
  return slowFib(n - 1) + slowFib(n - 2);
}

//A generic memoization function to cache function calls with the result.
function memoize(fn) {
  let cache = {};
  
  return function(...args) {
    //Return cached, if applicable.
    if (cache[args] === true) { 
      return cache[args]; 
    }
    
    //Cache it.
    cache[args] = fn.apply(this, args);
    
    //Return it.
    return cache[args];
    
  }
}

//The fast version of our fibonacci function.
let fastFib = memoize(slowFib);
console.log('Memoized version', fastFib(8));