When practicing solving algorithm problems, we often see questions that make us wonder if we would ever encounter similar situations in the real world (e.g. spiral traversal of a matrix).

This time, however, I came across an interesting algorithm challenge that makes practical sense to me.

Here's the task:

You are given a list of tasks, some of which depend on others.
Write a function tasksInOrder that takes a subset of those tasks and returns an ordered list of all the tasks to run.

To illustrate:

const tasks = [
  {
  task: "make a sandwich",
  depends: [ "buy groceries" ]
  },
  {
  task: "buy groceries",
  depends: [ "go to the store" ]
  }, 
  {
  task: "go to the store",
  depends: []
  }
]

// tasksInOrder(tasks, ["make a sandwich"])
// -> [ 'go to the store', 'buy groceries', 'make a sandwich' ]

// tasksInOrder(tasks, ["buy groceries", "make a sandwich"])
// -> [ 'go to the store', 'buy groceries', 'make a sandwich' ]

We all make to-do lists in our daily lives, so I was glad to finally see a function that we can actually put to good, practical use.

Brute Force Approach

As I read the challenge, the first thing that came to mind was a linked-list data structure, as each task has a dependency, or node, that points to another task.

With that, I was able to quickly write out a straightforward (but flawed) solution that traverses both the task list and the given subset.

function tasksInOrder(tasks, subset) {
  let result = []
  for (let task of tasks) {
    if (task.depends.length !== 0) {
      result.unshift(task.depends[0])
    }
  }
  for (let sub of subset) {
    result.push(sub)
  }

  return [...new Set(result)]
}

The solution above does output the desired results in the two sample cases:

// tasksInOrder(tasks, ["make a sandwich"])
// -> [ 'go to the store', 'buy groceries', 'make a sandwich' ]

// tasksInOrder(tasks, ["buy groceries", "make a sandwich"])
// -> [ 'go to the store', 'buy groceries', 'make a sandwich' ]

However, this solution would fail if out task list is not in order:

const tasksNotInOrder = [ 
  {
  task: "buy groceries",
  depends: [ "go to the store" ]
  }, 
  {
  task: "make a sandwich",
  depends: [ "buy groceries" ]
  },
  {
  task: "go to the store",
  depends: []
  }
]

// tasksInOrder(tasksNotInOrder, ["buy groceries"])
// expected -> [ 'go to the store', 'buy groceries' ]
// got -> [ 'buy groceries', 'go to the store' ]

So, how might we follow the dependencies of the given subset that keep recurring in the tasks list in the right order?

Recursive Approach

In order to grab all the dependencies of all the subtasks in the subset, we can:

Grab all the dependencies of one subtask
Add the dependencies to an array by prepending them, so we can put them in order
Repeat step#2 until the subtask has no dependency

Since the recursive solution occurs in the subtasks, we can separate concerns by creating a helper function that focuses on recursion:

function tasksInOrder(tasks, subset) {
  let tasksList = []
  for (let subTask of subset) {
    let foundTask = tasks.find(taskObj => taskObj.task === subTask)
    // invoke helper function
    getDependedTasks(foundTask, tasksList, tasks)
  }
}

// helper function
function getDependedTasks(currentTask, tasksList, tasks) {
  // prepend the current task
  tasksList.unshift(currentTask)
  // base case: when we hit the task with no dependency
  if (currentTask.depends.lenth === 0) {
    return
  }
  // recursive case: 
    // (1) find the task which the current task depends on
    // (2) run the function recursively with the found task
  let nextTask = tasks.find(taskObj => taskObj.task === currentTask.depends[0])
  return getDependedTasks(nextTask, tasksList, tasks)
}

And voilà! With this approach, we see an output of an orderly tasks list, no matter how disorganized the original list is.

Do you see any potential flaws in the recursive approach? Can you think of any other way to tackle this challenge? As always, please let me know in the comments!

When Recursion Comes to Rescue

Brute Force Approach

Recursive Approach