Promise Dependency Pool (Uber Frontend Interview) | Screening Round

In modern JavaScript development, asynchronous programming is a powerful technique for managing tasks that can occur independently of one another. This blog addresses a common problem faced during asynchronous execution: managing dependent promises dynamically. In a recent screening interview for a role at Uber, a question was posed regarding the execution of a set of asynchronous tasks with dependencies. 

The challenge can be summarized as follows:

• Assume a set of tasks, A, B, C, D, and E.
• Task A depends on the completion of Tasks B and C.
• Task B depends on the completion of Tasks D and E.
• Tasks C, D, and E operate independently, with no dependencies.

The goal is to create a generic executor that handles these asynchronous tasks without relying on hard-coded solutions or the direct use of Promise.all chaining. Let's delve deeper into the underlying concepts and provide an effective solution to this problem.

Concepts

Before we tackle the solution, it's essential to break down the key concepts related to promises and asynchronous execution in JavaScript:

• Promises: A promise is an object representing the eventual completion or failure of an asynchronous operation, allowing us to write cleaner asynchronous code and handle errors gracefully.
• Chaining Promises: When one promise depends on the resolution of another, we can chain promises together. This is a fundamental concept that enables us to execute a function after a promise resolves.
• Parallel Execution: Independent promises can be executed in parallel, optimizing performance and reducing total execution time when dependencies are not involved.
• Dependency Management: Understanding and managing dependencies between asynchronous functions ensures that tasks are executed in the correct order while still maximizing parallel execution where possible.

Problem Breakdown

In the provided scenario, we have a clear hierarchy of dependencies. To summarize:

• Task A must not start until both B and C are resolved.
• Task B must not start until both D and E are resolved.
• Tasks C, D, and E can run independently and in parallel.

Our goal is to implement these tasks dynamically, without hardcoded dependencies, and structure the solution to utilize any potential parallelism effectively.

Solution

To solve the problem, we can use a map to represent the dependencies between the tasks. When executing a task, the executor will check the dependency graph to determine what tasks need to be completed first. Below is the implementation detail:

const tasks = {
  A: () => new Promise(res => setTimeout(() => res('A'), 1000)),
  B: () => new Promise(res => setTimeout(() => res('B'), 1000)),
  C: () => new Promise(res => setTimeout(() => res('C'), 1000)),
  D: () => new Promise(res => setTimeout(() => res('D'), 1000)),
  E: () => new Promise(res => setTimeout(() => res('E'), 1000)),
};

const deps = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: [],
  D: [],
  E: [],
};

function execute(tasks, deps) {
  const resolved = new Set();
  const running = new Set();

  function tryExecute() {
    let progress = false;

    for (let task in tasks) {
      // Skip if already done or running
      if (resolved.has(task) || running.has(task)) continue;

      const dependencies = deps[task];

      // Check if all dependencies are resolved
      const canRun = dependencies.every(dep => resolved.has(dep));

      if (canRun) {
        progress = true;
        running.add(task);

        tasks[task]().then(() => {
          console.log(task, "done");

          running.delete(task);
          resolved.add(task);

          // Re-run after completion
          tryExecute();
        });
      }
    }

    return progress;
  }

  // Initial kick
  tryExecute();
}

execute(tasks, deps);

In this solution:

Conclusion

By leveraging a structured dependency graph and a recursive execution strategy, we can efficiently manage asynchronous tasks in JavaScript. This approach optimally balances parallel execution and the resolution of dependencies, giving us a robust solution for complex asynchronous flows like the one posed by Uber.

Similar Problems

Consider these additional questions that mirror the complexity of managing promises effectively:

• How into manage multiple asynchronous operations that have overlapping dependencies?
• What techniques can be employed to gracefully handle promise rejections in a chain of dependent tasks?
• In a scenario where promises can be resolved with varying priorities, how might one effectively manage these priorities?