Skip to content

Instantly share code, notes, and snippets.

@GreggSetzer
Created June 22, 2018 14:40
Show Gist options
  • Save GreggSetzer/1bc4ce930fa09cd8f06d279024c72e2e to your computer and use it in GitHub Desktop.
Save GreggSetzer/1bc4ce930fa09cd8f06d279024c72e2e to your computer and use it in GitHub Desktop.
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));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment