Quick Overview

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.

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.

Overview: 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

  1. Use either DFS with memoization or a topological ordering to avoid recomputation.
  2. 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).
  3. Be sure to include nodes that only appear in neighbor lists and treat missing keys as empty adjacency lists.

Loading coding console...

Show the approach

Approach

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)