Function to return items from an array where items at odd index which are repeated by the number at its preceding even index

Question

I got this interview question when interviewing with some big company. They asked me to write out a function next, which takes an array as the input value and returns the next available number.

The number at even index in the array indicates the number of the next number in the array at the odd index . For example, [2,2,1,7,3,5] meaning that we have two 2s, one 7 and 3 5s. So calling next() will output 2 2 7 5 5 5 sequentially one at a time. And when there is no available number, in this case when the third 5 is returned, the function would throw exception.

So this question was quite open ended. They didn't explicitly specify how I should implement this function. The only requirement was to achieve the behavior mentioned above, i.e. output next available number one at time.

During the interview I thought it would make sense to put this function on the prototype chain of Array so we can call this function directly on an array like this

const array = [2, 2, 1, 7, 3, 5];

Array.prototype.next = function() {
  const buffer = [];
  let x;
  let index = 0;
  for (let i = 0; i < this.length; i++) {
    if (i % 2 === 0) {
      x = i;
    } else {
      buffer.push(...new Array(this[x]).fill(this[i]));
    }
  }
  return buffer[index++];
};

console.log(array.next()); // 2
console.log(array.next()); // 2
console.log(array.next()); // 2 

I noticed that people are saying it's bad idea to make the function part of the Array prototype. So here is another solution

function getNext(array) {
  const buffer = [];
  let x;
  let index = 0;
  for (let i = 0; i < array.length; i++) {
    if (i % 2 === 0) {
      x = i;
    } else {
      buffer.push(...new Array(array[x]).fill(array[i]));
    }
  }
  return buffer[index++];
}

However the problem is, it doesn't remember the last output and move on to the next one. It will always output the first item in the array.

I always thought maybe we can implement this next as an iterator but I couldn't implement it myself.

Can anyone help me with it?

Answer 1

I think a natural fit for this problem would be a generator function. You can read more about them here: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Generator

Here is my solution. Let me know if you have any questions:

const generatorFunc = function* (arr) {
  let i = 0;
  while (i < arr.length) {
    yield arr[i];
    i++;
  } 
};

const buildIterator = (arr) => {
  const generatedArr = arr.reduce((acc, item, itemIndex) => {
    const isEven = itemIndex % 2 === 0;
    if (isEven) {
      const value = arr[itemIndex + 1];
      const iterationCount = item;
      return acc.concat(Array(iterationCount).fill(value));
    };
    return acc;
  }, []);
  const generator = generatorFunc(generatedArr);
  return {
    next: () => {
      const nextIteration = generator.next();
      if (nextIteration.done) {
        throw new Error('No more items in array');
      }
      return nextIteration.value;
    }
  };
};

const myIterator = buildIterator([2,2,1,7,3,5]);

console.log(myIterator.next()); //2
console.log(myIterator.next()); //2
console.log(myIterator.next()); //7
console.log(myIterator.next()); //5
console.log(myIterator.next()); //5
console.log(myIterator.next()); //5
console.log(myIterator.next()); // ERROR!!

There's a little bit of syntactic sugar here as standard js generator functions return objects like { value, done }. Let me know if you have any questions!

Answer 2

Well you got the problem solving part. All you need to do is create a scope then preserve the array you created temporarly and the current index in that scope.

const array = [2, 2, 1, 7, 3, 5];

function sequencer(arr) {
  const actualArray = []
  let currentIndex = 0;
  for (let i = 0; i < arr.length; i++) {
    if (i % 2 === 0) {
      x = i;
    } else {
      actualArray.push(...new Array(arr[x]).fill(arr[i]));
    }
  }
  return function() {
    if (currentIndex >= actualArray.length) throw new Error("execced array length")
    return actualArray[currentIndex++];
  }
}
let arrSequencer = sequencer(array);
for (let i = 0; i < 7; i++) {
  console.log(arrSequencer());
}

Answer 3

Edit: I read the question again and it seems that this is iterator kind of question. I'll still leave my answer as is, since it gives the guideline (without recursion) on how to create the answer as well.

I'd approach it like this:

const next = (arr) => {
  const [multiplier, number, ...rest] = arr;

  if (!number) {
    throw Error('No next number specified');
  }

  const currentOne = Array.from(Array(multiplier), () => number);
  const nextOne = (rest.length) ? next(rest) : [];
  return currentOne.concat(nextOne);
}

console.log(next([2,1,3,2,4,3]));
console.log(next([2,1,3,2,4,3,5]));

So basically we pick the multiplier and the number, spreading the rest of the array as such.

If we don't have the number specified, we throw an error. Otherwise we create a new array with length of multiplier and content of the number.

Then we make a recursive call with the rest of the array, if it contains any elements.

And finally we return the result.

Edit: You could use Array(multiplier).fill(number) instead of iterating it like in my example (Array.from(Array(multiplier), () => number);)