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.
Prerequisites
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.
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on <b>CSEstack.org</b> portal.