// Asked in Rippling, Uber and Amazon
// How can you resolve task dependencies in a directed acyclic graph
// and execute tasks in parallel with a concurrency limit?
// function taskA(done) {
// console.log("Task A Completed");
// function taskB(done) {
// console.log("Task B Completed");
// function taskC(done) {
// console.log("Task C Completed");
// function taskD(done) {
// console.log("Task D Completed");
// function taskE(done) {
// console.log("Task E Completed");
// dependency: ["c", "d"],
// dependency: ["a", "b"],
// // e must be resolved before c & d
// // d must be resolved before a & b
// // first resolve dependency and then run task in parallel.
// // taskOrder -> pass an array with resolved dependency
// executeTasksInParallel(taskOrder, asyncGraph, 2).then(() => {
// console.log("All tasks completed.");
// // All tasks completed.
//first try to resolve dependency using topologic sorting
function resolveDependencies(graph) {
const graphNodes = Object.keys(graph);
const adjList = new Map();
const inDegree = new Map();
const topologicalOrder = [];
// Build adjacency list and in-degree map
for (const node of graphNodes) {
const { dependency } = graph[node] || {};
for (const dep of dependency || []) {
const neighbors = adjList.get(dep) || [];
adjList.set(dep, neighbors);
inDegree.set(node, (dependency ? dependency.length : 0));
// Perform topological sort
for (const node of graphNodes) {
//start adding nodes which has no dependency
if (inDegree.get(node) === 0) {
while (queue.length > 0) {
const current = queue.shift();
topologicalOrder.push(current);
const neighbors = adjList.get(current) || [];
// look around it dependent neighbour
for (const neighbor of neighbors) {
inDegree.set(neighbor, inDegree.get(neighbor) - 1);
if (inDegree.get(neighbor) === 0) {
//Then execute task in parallel
function executeTasksInParallel(order, graph, limit = 2) {
return new Promise((resolve) => {
if (index >= order.length && activeTasks === 0) {
resolve(results); // All tasks are done
while (index < order.length && activeTasks < limit) {
const currentTask = order[index];
graph[currentTask].task(() => {
console.log(`${currentTask} completed.`);
executeNext(); // Check for the next task
const taskOrder = resolveDependencies(asyncGraph)
executeTasksInParallel(taskOrder, asyncGraph, 2).then(() => {
console.log("All tasks completed.");