Solving Front End problems with interviews. Promise Pool

In this article I would like to analyze the Promise Pool task (Leetcode 2636)

The task

Given an array of asynchronous functions functions and maximum pool size n. You need to write an asynchronous function promisePool. She must return Promisewhich is enabled when all input functions are enabled function.

The pool size determines the maximum number Promise, which can be executed simultaneously. Function PromisePool should start executing as many functions as possible from the array functions and take new functions for execution when some of the running ones Promise will be resolved. Functions must be executed in the order they appear in the array functions. When is the last Promise will go into state resolved, promisePool should also go to state resolved.

For example, if n=1, promisePool will perform one function at a time sequentially. However, if n=2, it will first start executing two functions. When either of the two functions resolves, the third function (if there is one in the array) must begin executing, and so on until there are no more functions left to execute.

According to the conditions of the problem, all functions from the array always successfully transition to the state resolved. As a result, the resulting Promise functions promisePool can return any value.

Example

Входные данные:
functions = [
  () => new Promise(res => setTimeout(res, 300)),
  () => new Promise(res => setTimeout(res, 400)),
  () => new Promise(res => setTimeout(res, 200))
]
n = 2
Результат: [[300,400,500],500]
Объяснение:
Во входном массиве 3 функции. В них вызывается setTimeout на 300мс, 400мс, и 200mмс соответственно.
Они переходят в resolved в 300мс, 400мс, и 500мс соответственно. Результирующий promise завершается в 500мс.
В t=0, первые 2 функции начинают выполнение. Размер пула 2.
В t=300, 1-я функция завершает выполнение, а 3-я функция начинает. Размер пула 2.
В t=400, 2-я функция завершает выполнение. Больше функций в массиве functions не осталось. Размер пула 1.
В t=500, 3-я функция завершает выполнение. Размер пула 0, и результирующий promise закже завершается.

Solution

Let i – the function currently being performed, availPool – the number of remaining resources to fulfill the Promise, completedCount – number of completed Promises.

• If the function array is empty, we can complete the resulting Promise.

• Otherwise, we run the recursive function executeNextwherein:

  • Take the following k functions, where k equal to the number of available resources.

  • We are reducing the number of free resources availPool on k (availPool -= k) and run k functions for execution.

  • Upon completion of each function, we release the resource (availPool += 1) and increase the number of completed functions by 1 (completedCount += 1).

  • If all functions have completed, we complete the final promise, otherwise we run the function recursively executeNext.

var promisePool = function(functions, n) {
    let i = 0;

    let availPool = n;
    let completedCount = 0;

    return new Promise((resolve, reject) => {

        if(functions.length === 0){
            resolve();
            return;
        }

        const executeNextN = () => {
            const pendingFunctions = functions.slice(i, i + availPool);
            i += pendingFunctions.length;
            availPool = 0;
            pendingFunctions.forEach(func => {
                func().then(() => {
                    availPool++;
                    completedCount++;
                    if(completedCount === functions.length){
                        resolve();
                    } else {
                        executeNextN();
                    }
                })
            });
        }

        executeNextN();
    });
};

/**
 * const sleep = 
 * promisePool([() => sleep(500), () => sleep(400)], 1)
 *   .then(console.log) // After 900ms
 */

I encountered a similar task at the Contest before the Two Day Offer from Yandex. There the problem was complicated with additional details and modified, but to solve it it was important to know this problem (Promise Pool), as well as to be familiar with Heap / Priority Queue.