Problem

At Dropbox, services are modeled as an unweighted graph. Given a graph, a start node, and a target node, return one valid path from start to target.

If no path exists, return an empty list. The graph is represented as an adjacency list, where each key is a node and its value is a list of neighboring nodes.

Formal Specification

• Input:
  • graph: dict mapping node IDs to lists of neighboring node IDs
  • start: starting node ID
  • target: destination node ID
• Output:
  • A list of node IDs representing a valid path from start to target, inclusive
  • Return [] if no path exists

Examples

Example 1

• Input: graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}, start = 'A', target = 'D'
• Output: ['A', 'B', 'D']
• Explanation: Starting at A, we can reach D through B.

Example 2

• Input: graph = {1: [2], 2: [3], 3: [], 4: []}, start = 1, target = 4
• Output: []
• Explanation: Node 4 is disconnected from the component containing 1.

Constraints

• 1 <= number of nodes <= 10^4
• 0 <= number of edges <= 2 * 10^4
• Node IDs are hashable values
• The graph may contain cycles
• The graph is unweighted