async javascript test

test.js

const MAX_INFLIGHT = 4;
const TOTAL = 100;
// the given dummy api supports a maximum of 4 of inflight requests.
// the given code is correct, but it is slow because it processes elements serially.
// your task is to process 100 elements as fast as possible.
// run this code with "node/bun test.js".
// it should print "pass".
// no external dependencies are allowed.
async function run(elements) {
  // ============
  // your code here starts here
  const results = [];
  for (const element of elements) {
    const result = await api(element);
    results.push(result);
  }
  return results;
  // your code ends here
  // ============
}
// api accepts 1 element, takes some time, returns a processed element
const api = (function () {
  let inflight = 0;
  const sleep = (ms) => new Promise((done) => setTimeout(done, ms));
  return async (element) => {
    inflight++;
    if (inflight > MAX_INFLIGHT) {
      console.log(`too many requests`);
      process.exit(1);
    }
    const delay =
      Math.random() < 0.1 ? 1000 : 100 + (Math.random() - 0.5) * 100;
    await sleep(delay);
    inflight--;
    console.log(`processed element ${element}/${TOTAL}`);
    return "P" + element;
  };
})();
// check ensures you have processed all elements correctly
function check(results) {
  for (let i = 0; i < TOTAL; i++) {
    const got = results[i];
    const expect = "P" + (i + 1);
    if (got !== expect) {
      console.log(`expected result[${i}] to be ${expect}, got ${got}`);
      process.exit(1);
    }
  }
  console.log("pass");
}
// create elements, run user code, check results
const elements = new Array(TOTAL).fill(null).map((_, i) => i + 1);
run(elements).then(check);

as fast as possible

How is that measured?

By the interviewer :P it's the algorithm that matters, and the range of possible solutions is fairly small. The key is that you achieve maximum utilisation of api()

This should keep 4 requests in flight until the end and it doesn't hide exceptions. A promise is created for every call right away but internally api is not called unless a spot opens up.

class AsyncQueue {
  #callCount = 0;
  // #queued holds functions that could not be called right away due to the limit.
  #queued = [];

  constructor(options) {
    this.callLimit = options?.callLimit ?? 1;
  }

  async #callOrAddToQueue(fn, resolve, reject) {
    if (this.#callCount < this.callLimit) {
      this.#callCount++;
      try {
        const result = await fn();
        resolve(result);
      } catch (err) {
        reject(err);
      } finally {
        this.#callCount--;
        // Done, now call the oldest queued if there is one.
        const next = this.#queued.shift();
        next?.();
      }
    } else {
      this.#queued.push(this.#callOrAddToQueue.bind(this, fn, resolve, reject));
    }
  }

  call(fn) {
    const { promise, resolve, reject } = Promise.withResolvers();
    this.#callOrAddToQueue(fn, resolve, reject);
    // This promise only settles when resolve or reject is called.
    return promise;
  }
}

async function run(elements) {
  const queue = new AsyncQueue({ callLimit: MAX_INFLIGHT });
  const results = await Promise.allSettled(
    elements.map((element) => queue.call(() => api(element)))
  );
  // result.reason is the error message.
  // The check function would print this if exceptions were possible.
  return results.map((result) => result.status === 'fulfilled' ? result.value : result.reason);
}

Another solution is to use a generator. This implementation allows the generator to control resuming after yield. It's a little strange, maybe there's another solution using generators that is more traditional.

function* apiIter(elements, next) {
  const promises = [];
  let callCount = 0;

  for (const element of elements) {
    if (callCount >= MAX_INFLIGHT) {
      yield;
    }
    callCount++;
    const promise = api(element);
    promises.push(promise);
    promise.finally(() => {
      callCount--;
      next();
    });
  }

  // Return an array of promises because it's easier to
  // let the caller handle waiting for the last few to resolve.
  return promises;
}

function run(elements) {
  const { promise, resolve } = Promise.withResolvers();
  // The second argument to apiIter is a callback the generator will call
  // after an individual api() call settles.
  const iter = apiIter(elements, async () => {
    const iterResult = iter.next();
    if (iterResult.done && iterResult.value) {
      const results = await Promise.allSettled(iterResult.value);
      resolve(
        results.map((result) =>
          result.status === "fulfilled" ? result.value : result.reason
        )
      );
    }
  });
  // Start the generator.
  iter.next();
  return promise;
}

var total = 100;
var array = [...Array(4)];
async function fn() {
  return new Promise((resolve, reject) => setTimeout((Math.random() < .5 ? resolve : reject), Math.floor(Math.random() * 1000)))
    .then(() => (--total, ({
      completed: 1,
      resolved: 1,
      rejected: 0,
      pending: 0
    }))).catch(() => (--total, ({
      completed: 1,
      rejected: 1,
      resolved: 0,
      pending: 0
    })))
}
while (total) {
  await Promise.allSettled(array.map(fn));
}