Ordering Task/Packages from Given Dependencies | Python Coding Challenge

A project is currently having issues with some of their libraries where packages are not being built in the correct order. You have been tasked to build a program that will ensure their packages are built correctly. You are given a list of packages to build and an array of dependencies where [Pi, Pj] indicates that you must build package Pi first if you want to take build Pj. Return the correct build order for the given list of packages.

This question was asked in Ethos Life coding interview.

This problem is similar to popular job scheduling or ordering of tasks from given dependencies.

You can use any programming language of your choice like C/C++, Java and Python. I used Python.

Python Program

Prerequisites

• Python for loop
• List methods in Python

Python Code

def find_missing_ele(pkg, dep):
    keys = [i[0] for i in dep]
    for i in pkg:
        if i not in keys:
            return i  

def remove_dep(dep, val):
    return [i for i in dep if not i[1] == val]

def get_pkg_order(pkg, dep):
    size = len(pkg)
    out = [""]*size

    for i in range(size):
        value = find_missing_ele(pkg, dep)
        pkg.remove(value)
        out[size-i-1] = value
        dep = remove_dep(dep, value)

    return out

packages=["P0","P1","P2","P3"]
dependencies = [["P2", "P0"],["P1","P2"],["P3","P1"],["P3","P2"]]
print(get_pkg_order(packages, dependencies))

Output

['P3', 'P1', 'P2', 'P0']

To solve this problem you can also use the graph traversing algorithm like DFS or BFS.

Any doubt? Let’s discuss in the comment section below. You can also suggest if you have any other approach to solve a problem of ordering of tasks from given dependencies.