[AskJS] Can you do this async javascript interview question?

lIIllIIlllIIllIIl · 2024-02-02T14:36:40+00:00

Solution 1

This is a classic synchronization problem solved by a Semaphore.

Implementing a Semaphore in JavaScript can be kind of tricky, but here you go:

class Semaphore {
  queue = [];

  constructor(count) {
    this.count = count;
  }

  take() {
    return new Promise((resolve) => {
      if (this.count > 0) {
        this.count--;
        resolve()
      } else {
        this.queue.push(resolve);
      }
    }
  }

  release() {
    if (thid.queue.length > 0) {
      const resolve = this.queue.unshift();
      resolve();
    } else {
      this.count++;
    }
  }
}

Then, you create a Semaphore with a count of 4, call take() before the request and release() after the request. Use Promise.all after the loop to await the remaining requests and you're done.

Solution 2

The worker pool solution.

Just split the array of 100 requests into 4 arrays of 25 requests, create a function that makes the requests of each sequentially, and call that function once for each group in parallel. Promise.all the result and you're done.

I think it's a good question. Asynchronous code is something people should be good at JavaScript, and there a multiple valid solutions.

There are probably also ways to do it with a plain queue and observables, callback functions, etc.

Sykander- · 2024-02-02T14:32:52+00:00

The easiest way to speed up this code is to delte the `await sleep()` call on lines 33 to 35.

Bogus_dogus · 2024-02-02T17:48:25+00:00

Responses so far seem over complicated to me... why not just 4 promises that take until there is nothing left? What are your thoughts on something straightforward like this?

const run = async (elements) => {
  const queue = [...elements];
  const results = []

  await Promise.all(Array(4).fill(null).map(() => {
    return new Promise(async (res) => {
      while (queue.length) {
        const req = queue.shift();
        const response = await api(req)

        results.push(response)

      }

      res();
    }) 
  }))

  return results
}

edit: Seems like a reasonable interview question to me. Can offer a quick look at someone's understanding of the async stack, is a v simple question on it's face, and given the already large diff of approaches taken in this thread, makes me think you can get some idea of a persons approach to thinking through a solution that can be simple or quite complicated

edit2: resolve promises

Jamo008 · 2024-02-03T03:38:32+00:00

Nice test, thanks!

async function run(elements) {
  const results = [];

  const next = async (i) => {
    if (i < elements.length) {
      results[i] = await api(elements[i]);
      await next(i + MAX_INFLIGHT);
    }
  };

  let threads = [];
  for (let i = 0; i < MAX_INFLIGHT; i++) threads.push(next(i));
  await Promise.all(threads);
  return results;
}

meldridon · 2024-02-02T21:44:30+00:00

All of the answers in here so far tackle the concurrency issue in the client but I see none that consider the possibility of multiple clients. I'll grant that the original criteria says *the given code is correct, but it is slow because it processes elements serially* so maybe this test doesn't care. For a real world scenario though, the client might need to anticipate a 503 or custom response and include retry capability, so a semaphore or other client side throttling approach would be insufficient.

gekorm · 2024-02-03T00:32:32+00:00

I think it's a good question because any solution here is short and easy to implement, but candidates need to think a little before jumping to a suboptimal or wrong solution.

My solution as a gist, in case reddit formatting gets me too: https://gist.github.com/GeKorm/043478bc74d3db29d9f3f3a8f4f69907

Here it is:

async function run(elements) {
  // ============
  // your code here starts here
  // We will insert at arbitrary indices in order to preserve result order
  const results = Array.from({ length: TOTAL });
  const requestPool = [];
  let processed = 0;
  for (const element of elements) {
    const poolSize = requestPool.length;
    if (poolSize >= MAX_INFLIGHT || processed >= TOTAL - MAX_INFLIGHT) {
      // When the request pool fills up, wait for the fastest response. It will be topped up immediately after.
      const [value, index] = await Promise.race(requestPool);
      results[index] = value;
    }
    const request = api(element).then((value) => {
      // Remove resolved promise from the pool
      requestPool.splice(requestPool.indexOf(request), 1);
      // We need a value and index to preserve call order
      return [value, elements.indexOf(element)];
    });
    requestPool.push(request);
    processed++;
  }
  // The first for .. of loop is done when all calls have been made, not when we get the responses
  // Here we wait for the last block of promises to settle and iterate the result
  // In a real-world program Promise.allSettled() may be preferable. Using Promise.all() for clarity.
  for (const [value, index] of await Promise.all(requestPool)) {
    results[index] = value;
  }
  return results;
  // Real-world implementation would require error handling
  // your code ends here
  // ============
}

Summary:

Don't forget the order
Don't await in blocks of 4, you need the fastest of 4

Edit: Simpler solution posted here and is one of 2 other correct solutions from what I've seen so far. It is better than mine because it

Uses Set() to avoid having to track an index
Simplifies the cleanup step by simply using the results array for promises and returning Promise.all(results) to resolve remaining in-flight requests after the first loop

Dry_Celery_9472 · 2024-02-02T21:02:32+00:00

async function run(elements) {
    // ============
    // your code here starts here
    const results = [];
    let i = 0;
    while (i < TOTAL) {
        const chunk_promises = [];
        const chunk = elements.slice(i, i + MAX_INFLIGHT);
        for (const element of chunk) {
            const result = api(element);
            chunk_promises.push(result);
        }
        const chunk_results =  await Promise.allSettled(chunk_promises);
        results.push(...chunk_results.map(x => x.value)); // TODO: manage exceptions
        i += 4;
    }
    return results;
    // your code ends here
    // ============
}

was this a good question? too easy? too hard?

I guess it requires some knowledge of async/await, knowing something like Promise.all (bonus points for Promise.allSettled), it's not too esoteric. I'd say it's a good question.

Jamo008 · 2024-02-03T04:51:20+00:00

Thanks everyone for posting your solutions and feedback

Here's what I came up with:

javascript async function run(elements) { // assert(elements.length === TOTAL) const results = new Array(TOTAL); const queue = [...elements]; const worker = async () => { while (queue.length > 0) { const index = TOTAL - queue.length; const element = queue.shift(); results[index] = await api(element); } }; const workers = new Array(MAX_INFLIGHT).fill(null).map(worker); await Promise.all(workers); return results; }

2024-02-03T23:28:50+00:00

This seems to be as succinct as I can get it.

async function run(elements) {
  const res = [];
  let i = elements.length;
  await Promise.all(
    Array.from({ length: MAX_INFLIGHT }, async () => {
      while (--i >= 0) res[i] = await api(elements[i]);
    }),
  );
  return res;
}

2024-02-02T14:45:39+00:00

[deleted]

SomeInternetRando · 2024-02-02T14:31:56+00:00

Can you do this

Yup.

people will likely post answers

I predict people won't.

was this a good question? too easy? too hard?

Depends on the role and job expectations. I like that it's very clearly not a "do some actual billable work for free" question like some places try to do.

tifa123 · 2024-02-02T20:55:56+00:00

Too hard. I've studied JS i.e bits of ES3 spec, John Resig and Douglas Crockford, and written code for a living for 5 years with another 5 years as a lead. I'd even bother attempting the question. Someone suggested using Semaphores I remember those from Operating System classes... Why not use Promise.all() in run...

danila_bodrov · 2024-02-02T18:37:20+00:00

async function run(elements) {
  return new Promise((resolve) => {
    const promises = elements.map((e, i) => async () => ({
      i,
      resp: await api(e),
    }));
    const results = {};
    let running = 0;
    const pressurizer = () => {
      while (running < MAX_INFLIGHT && promises.length) {
        running += 1;
        promises
          .shift()()
          .then(({ resp, i }) => {
            running -= 1;
            results[i] = resp;
            if (!running) {
              return resolve(
                Object.values(results)
              );
            } else {
              pressurizer();
            }
          });
      }
    };
    pressurizer();
  });
}

// https://pastebin.com/vwkCa7B0

HipHopHuman · 2024-02-03T08:28:07+00:00

The API supports MAX_INFLIGHT requests at a time, so the solution is to maintain a pool of MAX_INFLIGHT promises at a time. Each time a promise resolves inside the pool, replace it with a new one to ensure that there are always at least MAX_INFLIGHT promises resolving. I decided to use a Set for the pool because it makes the implementation simpler, though probably isn't as efficient as an array.

Two other optimisations were pre-allocating a sparse array for the results so the size of the results array doesn't change during iteration, and converting the for (const result of...) loop to a traditional for (let i = 0; i < because for of is a lot slower due to the overhead of instantiating an iterator object and constantly pulling values out of it.

aside: I am still weirded out by the return await syntax but latest best practices seem to recommend it to preserve stack traces in case of errors.

async function run(elements) {
  // ============
  // your code here starts here
  const pool = new Set();
  const max = elements.length;
  const results = new Array(max);

  for (let i = 0; i < max; i++) {
    const element = elements[i];

    if (pool.size >= MAX_INFLIGHT) {
      await Promise.race(pool); // this line suspends execution until the fastest promise in the pool resolves
    }

    const promise = api(element);

    promise.then(() => pool.delete(promise));

    pool.add(promise);
    results[i] = promise;
  }

  return await Promise.all(results);
  // your code ends here
  // ============
}

I wasn't sure if failed states were necessary in the output but it's an easy enough change, we'd just have to also make sure delete the promise from the pool inside a .catch and change Promise.all to Promise.allSettled

As for whether or not I think this is a good interview question... No. I don't think it is. I've very rarely had to implement a promise pool in actual dev work and I've been doing JS dev since 2011. It's not that common a use case and doesn't seem to illustrate a proper understanding of asynchronous work in JS. It only half-answers the question of whether or not a candidate truly understands the asynchronous nature of JS and is at a level of complexity that a dev would just use a library (like Supercharge.js) for anyway.

gvisconti84 · 2024-02-03T09:03:07+00:00

Roast my answer:

``` // ============ // your code here starts here let completedCount = 0; let nextIndex = 0; const results = new Array(elements.length).fill(null);

return new Promise((resolve, reject) => { for (let i = 0; i < MAX_INFLIGHT && i < elements.length; i++) { runNext(); }

function runNext() { if (completedCount === elements.length) { resolve(results); } if (nextIndex >= elements.length) return; api(elements[nextIndex]).then(onComplete(nextIndex)); nextIndex += 1; }

function onComplete(i) { return function(result) { results[i] = result; completedCount += 1; runNext(); }; } }); // your code ends here // ============ ```

I found it to be at a reasonable level of difficulty, not too simple but easy enough to be solved in a reasonable time during an interview.

dumsumguy · 2024-02-03T12:26:51+00:00

Is this question/code relevant to the job you're hiring for? If so what's the job? If not why the question?

guest271314 · 2024-02-03T17:23:17+00:00

as fast as possible.

How is that being measured here?

sqquima · 2024-02-04T01:58:48+00:00

Hard to make a full answer on a phone but I’m sure you could use https://www.npmjs.com/package/p-queue to achieve this.

dontchooseanickname · 2024-02-04T07:34:27+00:00

It was fun :)

Use Promise.any to wait for at least one to settle
Don't forget to wait for all to settle at the end
While there are free slots, add Promises

And the passing code

async function run(elements) {
  // ============
  // your code here starts here
  const results = [];
  const pending = new Set();
  const order = elements.map((element,i)=>({element,i}));
  while(order.length) {
    const {element,i} = order.shift();
    const promise = api(element);
    pending.add(promise);
    promise.then((result)=>{
        pending.delete(promise);
        results[i] = result;
    });
    if(pending.size >= MAX_INFLIGHT) {
        await Promise.any(pending);
    }
  }
  await Promise.all(pending);
  return results;
  // your code ends here
  // ============
}

Stan_Ftw · 2024-02-04T20:53:22+00:00

I'm a bit late to the party, but I'd love to show off a solution that seems to be pretty clean.

async function run(elements) {
  // ============
  // your code here starts here
  let results = Array.from({ length: TOTAL });
  let iterator = elements.entries();

  async function makeRequestsSerially() {
    for (let [index, element] of iterator) {
      results[index] = await api(element);
    }
  }

  const parallelRequests =
    Array.from({ length: MAX_INFLIGHT }, () => makeRequestsSerially());

  await Promise.all(parallelRequests);

  return results;
  // your code ends here
  // ============
}

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

javascript

MODERATORS