- Need to design a package installer (example: apt-get)
- Ensure that all packages required are installed in the right order
Algorithm that would be useful here is :
A. Merge sort B. Topological sort
Correct Answer : TOPOLOGICAL SORT
- To ensure the right order of installation of all packages that this task requires – what we really need is this:
- Understand and build a dependency graph of the given package and packages that this is dependent on.
- And, an algorithm that is known to help with resolving dependencies is the “Topological sort” – an application of DFS. As the name suggests it is useful in getting the topology right – the relationship topology.
No clue about what this algorithm is? Don’t worry! Here is a list of good references to help you explore further :
- Simple example based explanation of topological sort
- Solve coding problems related to this
- Course on graphs – that covers this? (Stanford course)