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 a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.