Skip to content

Instantly share code, notes, and snippets.

# GreggSetzer/fibonacci.js Created Jun 22, 2018

JavaScript Interview Question: Fibonacci
 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 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));
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.