thzinc

removeZeroes - Interview question of the week from rendezvous with cassidoo

The simple case wasn’t hard, but the low-memory iterator pattern was a fun, self-imposed challenge.

Interview question of the week

This week’s question: Given a non-empty array containing only non-negative integers, return the list with trailing and leading zeroes removed.

Example:

> removeZeroes([0, 0, 0, 3, 1, 4, 1, 5, 9, 0, 0, 0, 0])
> [3, 1, 4, 1, 5, 9]

> removeZeroes([0, 0, 0])
> []

> removeZeroes([8])
> [8]

My solution

Written as a stream of consciousness

My first thought is that if data is given as an array and the array is already fully in memory, the easiest solution is to iterate through the head and the tail of the array to find the indices of the first and last nonzero values. Since JavaScript’s Array type includes findIndex and findLastIndex, this becomes a pretty trivial call:

#mocha

  

function removeZeroes(input = []) {
  return input.slice(
    input.findIndex((n) => n !== 0),
    input.findLastIndex((n) => n !== 0) + 1
  );
}


mocha.setup("bdd");
const assert = chai.assert;
const expect = chai.expect;
const should = chai.should();

describe("Given valid array inputs", () => {
  const expectations = [
    {
      input: [0, 0, 0, 3, 1, 4, 1, 5, 9, 0, 0, 0, 0],
      output: [3, 1, 4, 1, 5, 9],
    },
    {
      input: [0, 0, 0],
      output: [],
    },
    {
      input: [8],
      output: [8],
    },
    {
      input: [0, 0, 0, 1],
      output: [1],
    },
    {
      input: [1, 0, 0, 0],
      output: [1],
    },
    {
      input: [1, 0, 0, 0, 1],
      output: [1, 0, 0, 0, 1],
    },
    {
      input: [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
      output: [1, 0, 0, 0, 1],
    },
  ];
  expectations.forEach(({ input, output }) => {
    describe(JSON.stringify(input), () => {
      // Arrange & Act
      const actual = Array.from(removeZeroes(input));

      // Assert
      it(`should trim the result to ${JSON.stringify(output)}`, () =>
        actual.should.have.members(output));
    });
  });
});

mocha.run();

However, if the input data is very large and we’re concerned about allocating a lot of space to memory, using the affordances of the iterator pattern would be beneficial. (i.e., JavaScript generators) Because we’ll be reading the input one at a time, the best we can do is operate in O(n) time, but we’ll keep the impact of the stuff in memory low.

At the start, we’ll iterate through the input until we find a nonzero value and yield it. After that point, if we encounter any zero value, we’ll start counting consecutive zeros. If after starting the count, we encounter a nonzero value, we’ll yield a number of zeros equal to the count, reset the count, then yield the nonzero value. We’ll repeat this logic until the end of the input.

#mocha

  

function* removeZeroes(arrayLike) {
  let foundStart = false;
  let zeroCount = 0;
  for (const value of arrayLike) {
    if (!foundStart) {
      if (value === 0) continue;
      foundStart = true;
      yield value;
    } else {
      if (value === 0) {
        zeroCount++;
      } else {
        for (let zc = 0; zc < zeroCount; zc++) {
          yield 0;
        }
        zeroCount = 0;
        yield value;
      }
    }
  }
}


mocha.setup("bdd");
const assert = chai.assert;
const expect = chai.expect;
const should = chai.should();

describe("Given valid array-like inputs", () => {
  const largeNumberOfZeroes = 100_000;
  const expectations = [
    {
      title: "large prefix",
      input: function* () {
        for (let i = 0; i < largeNumberOfZeroes; i++) yield 0;
        yield 3;
        yield 1;
        yield 4;
        yield 1;
        yield 5;
        yield 9;
      },
      output: [3, 1, 4, 1, 5, 9],
    },
    {
      title: "large suffix",
      input: function* () {
        yield 3;
        yield 1;
        yield 4;
        yield 1;
        yield 5;
        yield 9;
        for (let i = 0; i < largeNumberOfZeroes; i++) yield 0;
      },
      output: [3, 1, 4, 1, 5, 9],
    },
    {
      title: "large prefix and suffix",
      input: function* () {
        for (let i = 0; i < largeNumberOfZeroes; i++) yield 0;
        yield 3;
        yield 1;
        yield 4;
        yield 1;
        yield 5;
        yield 9;
        for (let i = 0; i < largeNumberOfZeroes; i++) yield 0;
      },
      output: [3, 1, 4, 1, 5, 9],
    },
    {
      title: "large range of valid zeroes",
      input: function* () {
        yield 3;
        yield 1;
        yield 4;
        for (let i = 0; i < largeNumberOfZeroes; i++) yield 0;
        yield 1;
        yield 5;
        yield 9;
      },
      output: [
        3,
        1,
        4,
        ...(function* () {
          for (let i = 0; i < largeNumberOfZeroes; i++) yield 0;
        })(),
        1,
        5,
        9,
      ],
    },
  ];
  expectations.forEach(({ title, input, output }) => {
    describe(title, () => {
      // Arrange & Act
      const actual = Array.from(removeZeroes(input()));

      // Assert
      it(`should trim the result to the expected ${output.length} elements`, () =>
        actual.should.have.members(output));
    });
  });
});

describe("Given valid array inputs", () => {
  const expectations = [
    {
      input: [0, 0, 0, 3, 1, 4, 1, 5, 9, 0, 0, 0, 0],
      output: [3, 1, 4, 1, 5, 9],
    },
    {
      input: [0, 0, 0],
      output: [],
    },
    {
      input: [8],
      output: [8],
    },
    {
      input: [0, 0, 0, 1],
      output: [1],
    },
    {
      input: [1, 0, 0, 0],
      output: [1],
    },
    {
      input: [1, 0, 0, 0, 1],
      output: [1, 0, 0, 0, 1],
    },
    {
      input: [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
      output: [1, 0, 0, 0, 1],
    },
  ];
  expectations.forEach(({ input, output }) => {
    describe(JSON.stringify(input), () => {
      // Arrange & Act
      const actual = Array.from(removeZeroes(input));

      // Assert
      it(`should trim the result to ${JSON.stringify(output)}`, () =>
        actual.should.have.members(output));
    });
  });
});

mocha.run();

See also