thzinc

numBalanced - Interview question of the week from rendezvous with cassidoo

This one was fun to think about the minimal amount of processing needed to produce the result. In this case, the question is carefully worded to allow naive processing that’s really fast.

Interview question of the week

This week’s question: Given a string of parenthesis, return the number of parenthesis you need to add to the string in order for it to be balanced.

Examples:

> numBalanced(`()`)
> 0

> numBalanced(`(()`)
> 1

> numBalanced(`))()))))()`)
> 6

> numBalanced(`)))))`)
> 5

My solution

Written as a stream of consciousness

Upon first glance, I should be able to treat ( as +1, ) as -1, and any other character as 0 and then sum the result. However, if the sum is negative, that would mean there’s more ) than ( in the string, so I’ll probably need to take the absolute value of the sum.

#mocha

  

function numBalanced(input = "") {
  if (typeof input !== "string") return 0;

  let sum = 0;
  for (let i = 0; i < input.length; i++) {
    switch (input.charAt(i)) {
      case "(":
        sum++;
        break;
      case ")":
        sum--;
        break;
    }
  }

  return Math.abs(sum);
}


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: "()",
      output: 0,
    },
    {
      input: "(()",
      output: 1,
    },
    {
      input: "))()))))()",
      output: 6,
    },
    {
      input: ")))))",
      output: 5,
    },
  ];
  expectations.forEach(({ input, output }) => {
    it(`should return ${output} for the input ${input}`, () => {
      numBalanced(input).should.equal(output);
    });
  });
});

describe("Given additional valid inputs", () => {
  const expectations = [
    {
      input: "XYZ()",
      output: 0,
    },
    {
      input: "((xyz)",
      output: 1,
    },
    {
      input: "}))()))))()",
      output: 6,
    },
    {
      input: "])))))",
      output: 5,
    },
  ];
  expectations.forEach(({ input, output }) => {
    it(`should return ${output} for the input ${input}, ignoring characters that are not parentheses`, () => {
      numBalanced(input).should.equal(output);
    });
  });
});

describe("Given invalid input", () => {
  it("should return 0 when the input is an empty string", () => {
    numBalanced("").should.equal(0);
  });
  it("should return 0 when the input is not a string", () => {
    numBalanced(null).should.equal(0);
    numBalanced(undefined).should.equal(0);
    numBalanced([]).should.equal(0);
    numBalanced({}).should.equal(0);
    numBalanced(1).should.equal(0);
  });
});

mocha.run();

This feels pretty decent. I could rewrite it in a single line with .reduce() (as long as I drop the validation that input is a string), but it loses a lot of readability.

const MAP = {
  "(": 1,
  ")": -1,
};
const numBalanced = (input) =>
  Math.abs(Array.from(input).reduce((sum, c) => sum + (MAP[c] || 0), 0));

(This uses MAP initialized outside of the function body in order to avoid reinstantiating the object input.length times.)

See also