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
Solution
from typing import Dict, List
from collections import deque
def max_depth(graph_dict: Dict[str, List[str]]) -> int:
# Collect all nodes, including those appearing only as neighbors
nodes = set(graph_dict.keys())
for nbrs in graph_dict.values():
nodes.update(nbrs)
if not nodes:
return 0
# Build adjacency mapping for all nodes
adj = {u: list(graph_dict.get(u, [])) for u in nodes}
# Compute indegrees
indegree = {u: 0 for u in nodes}
for u in nodes:
for v in adj[u]:
indegree[v] += 1
# Initialize DP and queue with sources (indegree 0)
dp = {u: 1 for u in nodes}
q = deque([u for u in nodes if indegree[u] == 0])
# Kahn's algorithm + DP for longest path in DAG (by nodes count)
while q:
u = q.popleft()
for v in adj[u]:
if dp[v] < dp[u] + 1:
dp[v] = dp[u] + 1
indegree[v] -= 1
if indegree[v] == 0:
q.append(v)
return max(dp.values())
Explanation
Compute a topological order using Kahn's algorithm while maintaining dp[u] as the maximum number of nodes in any path that ends at u. Initialize dp[u] = 1 for every node (path of just that node). For each edge u->v processed in topological order, update dp[v] = max(dp[v], dp[u] + 1). The answer is max(dp.values()) over all nodes. This approach naturally handles disconnected DAGs and nodes that appear only as neighbors by initializing them with empty adjacency lists.
Time complexity: O(n + m). Space complexity: O(n + m).
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.