thzinc

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();








      

      
      

        
See also