Factorial using promises

Iterative, recursive, promise-returning factorial interview question.

Here is my typical multi-part interview question.

Compute factorial of N using recursion

All I am looking for is simple code like this

1
2
3
4
5
6
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

1
2
3
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

1
2
3
4
5
6
7
8
9
10
11
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

1
2
3
4
5
6
7
8
9
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.

1
2
3
4
5
6
7
8
9
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

1
2
3
4
5
6
7
8
9
10
11
12
13
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.

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

1
2
3
4
5
6
7
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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?