1. Installer for a package

Requirements :

  • 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 :

  1. Simple example based explanation of topological sort
  2. Solve coding problems related to this
  3. Course on graphs – that covers this? (Stanford course)