Detect cycles and order with DFS

Q: Detect cycles and order with DFS

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Detect cycles and order with DFS

Overview

Comments (0)