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.
graph: dict mapping node IDs to lists of neighboring node IDsstart: starting node IDtarget: destination node IDstart to target, inclusive[] if no path existsExample 1
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}, start = 'A', target = 'D'['A', 'B', 'D']A, we can reach D through B.Example 2
graph = {1: [2], 2: [3], 3: [], 4: []}, start = 1, target = 4[]4 is disconnected from the component containing 1.1 <= number of nodes <= 10^40 <= number of edges <= 2 * 10^4graph = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []}, start = 'A', target = 'D'Output['A', 'B', 'D']WhyThe path goes from `A` to `B`, then from `B` to `D`.graph = {1: [2], 2: [3], 3: [], 4: []}, start = 1, target = 4Output[]WhyNode `4` is not reachable from node `1`, so no path exists.graph = {1: [2, 3], 2: [4], 3: [4], 4: []}, start = 1, target = 4Output[1, 2, 4]WhyBoth `[1, 2, 4]` and `[1, 3, 4]` are valid. With this neighbor order, BFS finds `[1, 2, 4]` first.1 <= number of nodes <= 10^40 <= number of edges <= 2 * 10^4Node IDs are hashable valuesThe graph may contain cyclesThe graph is unweighteddef find_path(graph, start, target):
