HomePremium · ₹1199
← All questions

Resolve task dependencies in a DAG with a concurrency limit

Hard
Asked at:RipplingUberAmazon
Was this asked in an interview?

Topologically order tasks in a DAG and run them in parallel with a concurrency limit.

Problem

Given a graph of async tasks where some depend on others, run each task only after its dependencies finish, executing independent tasks in parallel but never more than limit at a time.

function taskA(done){ console.log("Task A Completed"); done(); }
function taskB(done){ setTimeout(()=>{ console.log("Task B Completed"); done(); },2000); }
function taskC(done){ setTimeout(()=>{ console.log("Task C Completed"); done(); },200); }
function taskD(done){ console.log("Task D Completed"); done(); }
function taskE(done){ console.log("Task E Completed"); done(); }

const asyncGraph = {
  e: { dependency: ["c","d"], task: taskE },
  c: { task: taskC },
  d: { dependency: ["a","b"], task: taskD },
  a: { task: taskA },
  b: { task: taskB },
};
Resolve task dependencies in a DAG with a concurrency limit — JavaScript Interview Question | Mentoxis