thzinc

missingBits - Interview question of the week from rendezvous with cassidoo

Nice, bite-sized algorithm question.

Interview question of the week

This week’s question: You are given a list of positive integers which represents some range of integers which has been truncated. Find the missing bits, insert ellipses to show that that part has been truncated, and print it. If the consecutive values differ by exactly two, then insert the missing value.

Examples:

> missingBits([1,2,3,4,20,21,22,23])
> "[1,2,3,4,...,20,21,22,23]"

> missingBits([1,2,3,5,6])
> "[1,2,3,4,5,6]"

> missingBits([1,3,20,27])
> "[1,2,3,...,20,...,27]"

My solution

This should be able to be solved in O(n) time by just reading the input array and keeping track of the last element to compare against.

One notable “gotcha” in the given examples is that the result is a string, not a data structure like an array.

#mocha

  

function missingBits(input = []) {
  const result = [];

  let prev = null;
  for (const curr of input) {
    if (prev === null) {
      prev = curr;
      result.push(curr);
      continue;
    }

    switch (curr) {
      case prev + 1:
        result.push(curr);
        break;
      case prev + 2:
        result.push(prev + 1, curr);
        break;
      default:
        result.push("...", curr);
    }

    prev = curr;
  }

  return `[${result.join(",")}]`;
}


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, 2, 3, 4, 20, 21, 22, 23],
      output: "[1,2,3,4,...,20,21,22,23]",
      because:
        "there should be ellipses to denote the gap between the value 4 and 20",
    },
    {
      input: [1, 2, 3, 5, 6],
      output: "[1,2,3,4,5,6]",
      because:
        "the range should be filled in with the missing value 4 because the gap between the value 3 and 5 is a single integer",
    },
    {
      input: [1, 3, 20, 27],
      output: "[1,2,3,...,20,...,27]",
      because: "the both criteria are employed here",
    },
  ];
  expectations.forEach(({ input, output, because }) => {
    it(`should return ${output} for the input ${input} because the expected digits are ${because}`, () => {
      missingBits(input).should.equal(output);
    });
  });
});

describe("Given additional criteria derived from the examples", () => {
  it("should handle an empty array", () => {
    missingBits([]).should.equal("[]");
  });

  it("should return a string", () => {
    missingBits([]).should.be.a("string");
  });
});

mocha.run();








      

      
      

        
See also