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
Candidate's Approach
The candidate implemented a depth-first search (DFS) algorithm to traverse the dependency graph. They maintained sets for already installed packages and visited nodes to avoid cycles and ensure proper installation order. The candidate faced challenges when asked to adapt their solution to handle arbitrary graphs instead of a DAG, requiring them to implement cycle detection.
Interviewer's Feedback
No feedback provided.