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.
def find_missing_ele(pkg, dep): keys = [i 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 == 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))
['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.