Detect cycles and order with DFS
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
You are given a directed graph of package dependencies represented as an adjacency list: Map<String, List<String>> deps where deps[p] lists packages that p depends on. Implement installOrder(List<String> packages, Map<String, List<String>> deps) that returns a valid installation order containing all packages, or indicates that no order exists if a cycle is present.
Requirements: Use depth-first search with explicit cycle detection (recursion stack or color marking). The graph may be disconnected. If acyclic, output any valid topological order. Discuss iterative vs. recursive DFS, stack overflow risks, and complexity analysis.
Quick Answer: This question evaluates understanding and implementation of graph traversal concepts such as depth-first search, explicit cycle detection, and topological ordering, and falls within the coding and algorithms domain, requiring practical application alongside conceptual understanding.