oddSquareSum - Interview question of the week from rendezvous with cassidoo
In this case, writing tests to prove the solution was far more interesting than the solution itself.
TIL that Node did have tail recursion for a brief period, but then removed the feature. I was going to work on a fancy tail recursion implementation that supported memoization, but I wanted to stay in JavaScript for the solution.
Interview question of the week
This week’s question: Sum the odd-square numbers less than a given integer
n
.Example:
> oddSquareSum(1) > 0 > oddSquareSum(2) > 1 > oddSquareSum(9) > 1 > oddSquareSum(10) > 10 > oddSquareSum(44) > 35
My solution
This is a simple iterative implementation. Very large numbers could cause undue CPU load, as well as repeated calls for similar values since there’s no memoization.
I’m using the first defined value of the sequence to short circuit the case when lim
is equal to (or less than) zero. (i.e., let n = 0, v = 1;
)
#mocha
function oddSquareSum(lim) { let acc = 0; for (let n = 0, v = 1; v < lim; v = oddSquare(++n)) { acc += v; } return acc; } function oddSquare(n) { // Odd squares: a(n) = (2n+1)^2 return (2 * n + 1) ** 2; } mocha.setup("bdd"); const assert = chai.assert; const expect = chai.expect; const should = chai.should(); describe("Given the examples from the question", () => { const expectations = [ { input: 1, output: 0 }, { input: 2, output: 1 }, { input: 9, output: 1 }, { input: 10, output: 10 }, { input: 44, output: 35 }, ]; expectations.forEach(({ input, output }) => { it(`should return ${output} for the input ${input}`, () => { oddSquareSum(input).should.equal(output); }); }); }); // https://oeis.org/A016754 const A016754 = [ 1, 9, 25, 49, 81, 121, 169, 225, 289, 361, 441, 529, 625, 729, 841, 961, 1089, 1225, 1369, 1521, 1681, 1849, 2025, 2209, 2401, 2601, 2809, 3025, 3249, 3481, 3721, 3969, 4225, 4489, 4761, 5041, 5329, 5625, 5929, 6241, 6561, 6889, 7225, 7569, ]; describe("Given elements of integer sequence A016754", () => { describe("When the limit is equal to the element of the sequence", () => { const expectations = A016754.map((lim, i, a) => ({ input: lim, output: a.slice(0, i).reduce((acc, cur) => acc + cur, 0), })); expectations.forEach(({ input, output }) => { it(`should return ${output} for the input ${input}`, () => { oddSquareSum(input).should.equal(output); }); }); }); describe("When the limit is equal one greater than the element of the sequence", () => { const expectations = A016754.map((lim, i, a) => ({ input: lim + 1, output: a.slice(0, i + 1).reduce((acc, cur) => acc + cur, 0), })); expectations.forEach(({ input, output }) => { it(`should return ${output} for the input ${input}`, () => { oddSquareSum(input).should.equal(output); }); }); }); }); mocha.run();