1

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?

Improve this question
7
  • 2
    Why is extending native objects a bad practice? Commented Mar 31, 2020 at 18:26
  • You're already half way to the iterator solution, all you need is to return buffer[Symbol.iterator]() instead of buffer[0]. Commented Mar 31, 2020 at 18:31
  • …however it sounds like they want you to mutate the array, i.e. decrement counts and remove the first tuple after taking the number. Commented Mar 31, 2020 at 18:32
  • Your code doesn't satisfy this condition : which takes an array as the input Commented Mar 31, 2020 at 18:32
  • @Eldar yea I know. As I said the question they asked was open-ended. it's up to you to decide the implementation details. Commented Mar 31, 2020 at 18:40

3 Answers 3

Reset to default
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!

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Hi thanks for the solution. I am new to generator/iterator. Could you provide some instructions on how to run myIterator and get the result?
sure thing. myIterator returns an object with a next method. You would simply have to run myIterator.next() to return the next value in the sequence. I'll update the answer.
Thank you for the answer! Could you elaborate a bit on “There's a little bit of syntactic sugar here as standard js generator functions return objects like { value, done }” I don't completely understand it. Also could you make the iterator throw exception when it is called when there's no available number?
Sure. When you call a Javascript Generator's next, it returns an object. It's why I added the .value at the end of next: () => generator.next().value. But to really understand js generators I encourage you to play with that generatorFunc I wrote. I'll update the answer to throw an exception when done.
more on js generators: the egghead series is pretty good: egghead.io/courses/…
1

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());
}

Improve this answer

Comments

1

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);)

Improve this answer

1 Comment

Nice solution. However it returns an array of nums at once, not returning them one at a time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.