PYTHON

Given Map:

dependency_map = {"Gnome 3":"GTK Widget Toolkit", "Boost": None, "elfutils": "libelf++", "libelf++": "Cairo 2D" "GTK Widget Toolkit": "Cairo 2D" "GDB": "elfutils" "Cairo 2D" : "Boost"}

# # Given a map of software package dependencies, and a request to install a piece of software, return an ordered list of all pieces of software that must be installed before the requested software can be installed. # # Assumptions you can make: # # - Each piece of software will only ever have a single dependency # - There are no cyclical dependencies and you will always be able # to return a valid answer. # - Each software will only appear once as a key in the map of # software package dependencies # # # ===== Example ===== # # For the rest of this document, pieces of software will be referred to objects and their IDs, as this problem is abstractable to many different scenarios. # # The following is a map of object names, mapped to that object's dependency. For this problem, an object can only have a single dependency, but a single object can be depended on by multiple objects. Any object that has a dependency on None means that it has no dependencies. # # == Map of Object IDs == # Gnome 3, GTK Widget Toolkit # Boost, None # elfutils, libelf++ # libelf++, Cairo 2D # GTK Widget Toolkit, Cairo 2D # GDB, elfutils # Cairo 2D, Boost # # It can be read as: # Gnome 3 has a dependency on GTK Widget Toolkit, # Boost has no dependencies, # elfutils has a dependency on libefl++, # libelf++ has a dependency on Cairo 2D, # GTK Widget Toolkit has a dependency on Cairo 2D, # GDB has a dependency on elfutils, # Cairo 2D has a dependency on Boost # # No software appears in the left hand column more than once, each object is unique and can only have one dependency. # A software can show up in the right hand column multiple times (a object can be depended on by multiple other objects). # # If a request came in to create object X, we need to return a list in the order that the objects should be created, such that object X was only created once all of its dependencies were also created. # # For example, if a request came in to create Gnome 3, we would need to return the following list. # # [" Boost", "Cairo 2D", "GTK Widget Tookit", "Gnome 3"] # # This list says create, in order, Boost, then Cairo 2D, then GTK Widget Toolkit, and finally, Gnome 3. # # This is because Gnome 3 depends on GTK Widget, which depends on Cairo 2D, which depends on Boost.

dependency_map = {"Gnome 3":"GTK Widget Toolkit", "Boost": None, "elfutils": "libelf++", "libelf++": "Cairo 2D" "GTK Widget Toolkit": "Cairo 2D" "GDB": "elfutils" "Cairo 2D" : "Boost"} dependency_map["Gnome 3"] = "GTK Widget Toolkit" dependency_map["Boost"] = None dependency_map["elfutils"] = "libelf++" dependency_map["libelf++"] = "Cairo 2D" dependency_map["GTK Widget Toolkit"] = "Cairo 2D" dependency_map["GDB"] = "elfutils" dependency_map["Cairo 2D"] = "Boost" input

"Gnome 3"

output

["Boost", "Cairo 2D", "GTK Widget Tookit", "Gnome 3"]