Graph Traversal With Recursion | Dataford Interview Questions

Your question is Graph Traversal With Recursion. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Rippling may need to install a selected set of apps while automatically including every app they depend on. Given an app dependency graph and requested apps, return a deterministic order in which all required apps can be installed, with every dependency appearing before the app that requires it.

Use recursive depth-first traversal. If a circular dependency exists among the required apps, return an empty list.

Formal Specification

Implement get_install_order(app_dependencies, requested_apps).

app_dependencies is a dictionary mapping an app name to a list of direct dependency names.
requested_apps is a list of app names to install.
Return a list containing each required app exactly once, including the requested apps and all transitive dependencies.
Dependencies must appear before their dependents.
When multiple dependencies are available, process them in lexicographic order so the result is deterministic.
An app absent from app_dependencies is treated as having no dependencies.
Return [] if the required subgraph contains a cycle.

Constraints

1 <= len(requested_apps) <= 10^4
At most 10^5 distinct apps and dependency edges exist
App names are non-empty strings
An app absent from app_dependencies has no dependencies
Return [] when the required subgraph contains a cycle

Function Signature

def get_install_order(app_dependencies, requested_apps):