Determine Maximum Path Length in Directed Acyclic Graph
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
A backend service represents task dependencies as a directed graph; you need to understand how deep the longest dependency chain can get.
##### Question
Given an adjacency list of a directed acyclic graph (DAG), implement a Python function max_depth(graph_dict) that returns the maximum number of nodes in any path.
##### Hints
Use DFS with memoization or topological ordering to avoid recomputation and cycles.
Quick Answer: This question evaluates proficiency in graph algorithms and algorithmic reasoning, focusing on properties of directed acyclic graphs, longest-path concepts, and complexity analysis related to dependency chains.
Given a directed acyclic graph (DAG) represented as a dictionary mapping each node (string) to a list of its outgoing neighbors (strings), return the maximum number of nodes in any directed path. If the graph has no nodes, return 0. Nodes that appear only in neighbor lists but not as keys should be treated as nodes with no outgoing edges. Count includes both start and end nodes of the path.
Constraints
- 0 <= number of nodes n <= 100000
- 0 <= number of edges m <= 200000
- Graph is directed and acyclic (DAG); no self-loops or parallel edges needed
- Node labels are unique non-empty strings
- Nodes may appear only in neighbor lists; treat them as having empty adjacency lists
- Return 0 for an empty graph
- Aim for O(n + m) time and O(n + m) space
Hints
- Use either DFS with memoization or a topological ordering to avoid recomputation.
- In topological order, let dp[u] be the longest path (in nodes) ending at u; relax edges u->v with dp[v] = max(dp[v], dp[u] + 1).
- Be sure to include nodes that only appear in neighbor lists and treat missing keys as empty adjacency lists.