Amazon interview SDE 2

Round 1

Questions: Design a package installer system that can install a package along with all its dependencies. Each package has an "install()" method to install itself. Implement a solution that, given a package, installs the given package and its dependencies.

Here is an example of a package structure that we would need to install:

• ‘nodejs’ depends on ‘npm’, ‘v8engine’
• ‘npm’ depends on ‘nodejs-core’
• ‘v8engine’ depends on ‘libuv’
• ‘react’ depends on ‘nodejs’, ‘babel’
• ‘babel’ depends on ‘core-js’
• ‘typescript’ depends on ‘nodejs’

The candidate mentioned that the solution evolved over time, requiring adjustments based on assumptions about input and output. They were prompted to handle edge cases, such as assuming the input dependency map represents an arbitrary graph rather than a valid Directed Acyclic Graph (DAG) and to manage cycles.

# runtime O(V + E)
# space O(E)
example_dep_map = {'npm' : ['nodejs-core'], 'nodejs' : ['npm', 'v8engine']}
loop_example = {'a': ['b'], 'b': ['a']}
multi_dependents = {'a': ['b', 'c'], 'c' : ['b']}

from something import install, isValidPackage

# visited {'nodejs', 'npm', 'v8engine', 'react', 'babel', 'typescript'}
# installed {npm, v8engine, nodejs, babel, react, typescript}
# ordered [nodejs-core, npm, libuv, v8engine, nodejs, corejs, babel, react, typescript]

def install(dep_map):
    already_installed = set()
    visited = set()
    
    ordered = []
    
    def dfs(package_name):
        if package_name not in dep_map:
            if not isValidPackage(package_name):
                throw Exception('undefined package')
            
            # already_installed.add(package_name) optional
            ordered.append(package_name)
            return
        
        if package_name in already_installed:
            return
        if package_name in visited: 
            throw Exception('error')
        visited.add(package_name)
        deps = dep_map[package_name]
        for d in deps:
            dfs(d)
        install(package_name)
        ordered.append(package_name)
    
    # dfs(package_name)
    
    for package_name in dep_map.keys():
        dfs(package_name)
        
    return ordered