thzinc

trimArray - Interview question of the week from rendezvous with cassidoo

There’s a really simple one-liner for arrays, but what about using this with generators? (i.e., the iterator pattern where a length is not known until reaching the end of the iteration)

Interview question of the week

This week’s question: Given an array arr and integers n and m, remove n elements from the front of the array, and m elements from the back. Assume that n + m <= arr.length.

Example:

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

> trimArray([6, 2, 4, 3, 7, 1, 3], 5, 0)
> [1, 3]

> trimArray([1, 7], 0, 0)
> [1, 7]

My solution

Written as a stream of consciousness

First, the one-liner:

#mocha

  

function trimArray(arr, start, end) {
  return arr.slice(start, arr.length - end);
}

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, 5, 6], 2, 1],
      output: [3, 4, 5],
    },
    {
      input: [[6, 2, 4, 3, 7, 1, 3], 5, 0],
      output: [1, 3],
    },
    {
      input: [[1, 7], 0, 0],
      output: [1, 7],
    },
  ];
  expectations.forEach(({ input, output }) => {
    it(`should return ${output} for the input ${JSON.stringify(input)}`, () => {
      // Act
      const actual = trimArray(...input);

      // Assert
      Array.from(actual).should.deep.equal(output);
    });
  });
});

mocha.run();







Now, let’s deal with a generator. To deal with the start argument, we’ll iterate that many times over the generator. Then to deal with the end argument, we’ll need to keep a queue of items that is end-sized and only yield results that exceed the size of the queue. I’m pretty sure I can use Array#splice() to do this with one nice function call.




  
#mocha

  

  

function* trimArray(arrayLike, start, end) {
  let i = 0;
  const fifo = [];
  for (const item of arrayLike) {
    if (i++ < start) continue;
    fifo.push(item);
    if (fifo.length > end) {
      yield fifo.splice(0, 1)[0];
    }
  }
}

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, 5, 6], 2, 1],
      output: [3, 4, 5],
    },
    {
      input: [[6, 2, 4, 3, 7, 1, 3], 5, 0],
      output: [1, 3],
    },
    {
      input: [[1, 7], 0, 0],
      output: [1, 7],
    },
  ];
  expectations.forEach(({ input, output }) => {
    it(`should return ${output} for the input ${JSON.stringify(input)}`, () => {
      // Act
      const actual = trimArray(...input);

      // Assert
      Array.from(actual).should.deep.equal(output);
    });
  });
});

describe("Given the examples from the question emitted as via a generator", () => {
  function* asArrayLike(arr) {
    for (const e of arr) {
      yield e;
    }
  }
  const expectations = [
    {
      input: [asArrayLike([1, 2, 3, 4, 5, 6]), 2, 1],
      output: [3, 4, 5],
    },
    {
      input: [asArrayLike([6, 2, 4, 3, 7, 1, 3]), 5, 0],
      output: [1, 3],
    },
    {
      input: [asArrayLike([1, 7]), 0, 0],
      output: [1, 7],
    },
  ];
  expectations.forEach(({ input, output }) => {
    it(`should return ${output} for the input ${JSON.stringify(input)}`, () => {
      // Act
      const actual = trimArray(...input);

      // Assert
      Array.from(actual).should.deep.equal(output);
    });
  });
});

mocha.run();







Yay! Splice works like I thought it would! This solution will only ever hold end + 1 elements in memory, which means that when iterating over a very large dataset (especially one where the length is not known ahead of iteration), it will outperform the simple solution in terms of memory use.


      

      
      

        
See also