Factorial using promises

Here is my typical multi-part interview question.

Compute factorial of N using recursion

All I am looking for is simple code like this

function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

Can you verify this code computes the correct factorial?

I am looking for something quick and dirty

console.assert(factorial(1) === 1, '1!');
console.assert(factorial(2) === 2, '2!');
console.assert(factorial(3) === 6, '3!');

If a person writes actual QUnit / Mocha / anything unit tests that is a plus.

Can you find the largest N the system can compute factorial for?

I am looking for the value of N where the max size of the stack is exhausted. The candidate should know that when using recursion the previous call remains on the stack, so computing factorial of 5 means there are five calls at once at some point

factorial(5) {
    return 5 * factorial(4) {
        return 4 * factorial (3) {
            return 3 * factorial (2) {
                return 2 * factorial (1) {
                    return 1;
                }
            }
        }
    }
}

The candidate should try different values of N, probably starting with 1000, 10k, 100k, etc. On my machine, the stack is exhausted for n = 100k.

Can you write factorial using iteration?

Change code to a loop, and I am looking for the candidate to reuse the unit tests from before.

Can you write asynchronous version of factorial function using promises?

I am looking for recursive (simpler) version of the code, something like this using Q library

var Q = require('q');
function factorial(n) {
  if (n === 1) {
    return Q(1);
  }
  return factorial(n - 1).then(function (nMinus1Factorial) {
    return n * nMinus1Factorial;
  });
}

Can you write unit tests for your asynchronous factorial?

I am looking for something like this, quick and dirty, but the candidate should know how to handle the error.

factorial(5).then(function (result) {
  console.assert(result === 120);
}).catch(function (err) { 
    console.error('invalid 5!');
});
// OR
factorial(5).then(function (result) {
  console.assert(result === 120);
}).done();

Can you test multiple numbers, for example [1, 2, 3] at once?

I am looking for the candidate to know how to execute multiple promises in parallel. Q, Bluebird and $q libraries have this feature

Q.all([
  factorial(1),
  factorial(2),
  factorial(3)
]).then(function (results) {
  console.assert(results[0] === 1, results);
  console.assert(results[1] === 2, results);
  console.assert(results[2] === 6, results);
})
.finally(function () {
  console.log('all done');
})
.done();

Does the recursive async version crash for large N?

Yes, the candidate should just try running the same large N found earlier against the promise-returning factorial.

Advanced: rewrite async factorial to avoid stack exhaustion

I am looking for understanding the different between creating a chain of promises and executing a function. A simple solution is to build the chain first without using recursion and then execute it.

var Q = require('q');
function factorial(n) {
  var start = Q(n);
  while (n -= 1) {
    start = start.then(function (n, value) {
      return value * n;
    }.bind(null, n));
  }
  return start;
}

Notice there is no call to factorial anywhere inside this code. The only detail is binding the value of n when creating the then callback function.

This function can "compute" factorial for n = 100k. I am putting the word compute in quotes because the actual value quickly reaches Infinity. But the stack is never exhausted!

Advanced: write async factorial using native ES6 promises

Native promises are already in V8 and the syntax is very simple. To avoid using Q when building promise chain one can write

function valuePromise(n) {
  return new Promise(function (resolve) {
    return resolve(n);
  });
}
function factorial(n) {
  var start = valuePromise(n);
  while (n -= 1) {
    start = start.then(function (n, value) {
      // console.log('n', n, 'value', value)
      return value * n;
    }.bind(null, n));
  }
  return start;
}

Advanced: write tail call optimized version of recursive sync function

If the candidate is familiar with the tail call optimization, he / she could write the ES6 version and show the 6to5 transpiler transforming recursive code to the imperative one.

function factorial(n, acc = 1) {
  if (n <= 1) return acc;
  return factorial(n - 1, acc * n);
}
console.assert(factorial(1) === 1, '1!');
console.assert(factorial(2) === 2, '2!');
console.assert(factorial(3) === 6, '3!');

Notice the accumulator parameter that replaced n * factorial(n - 1) expression. The recursive call is by itself at the tail of the function.

Advanced: write factorial using generators

Generators exit the function AND keep the internal state after each yield. Thus we can keep multiplying the number without growing the stack.

function* Factorial() {
  var n = 1, total = 1;
  while (true) {
    total = total * n++;
    yield total;
  };
}
function factorial(n) {
  var f = Factorial(), k, nf;
  for (k = 0; k < n; k += 1) {
    nf = f.next().value;
  }
  return nf;
};

How to prepare for these interviews?

• Read a few of my favorite JavaScript books.
• Read my other blog posts.
• Follow me on twitter @bahmutov
• Read about upcoming ES6 features