FastPrepAll Paths From Source to Target

All Paths From Source to Target

Bloomberg LP logoBloomberg LP● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

Given a directed acyclic graph as an adjacency list graph, return every path from node 0 to node n - 1.

Each returned path includes both endpoints. Visit outgoing neighbors in their listed order and return paths in the resulting depth-first order.

Function

allPathsSourceTarget(graph: int[][]) → int[][]

Examples

Example 1

graph = [[1,2],[3],[3],[]]return = [[0,1,3],[0,2,3]]

The two directed routes go through node 1 or node 2.

Example 2

graph = [[4,3,1],[3,2,4],[3],[4],[]]return = [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Depth-first traversal follows each adjacency list in its supplied order.

Constraints

  • 2 <= graph.length <= 15.
  • Every neighbor is a valid node index and the graph is acyclic.
  • The input contains no duplicate outgoing edge.

More Bloomberg LP problems

See Bloomberg LP hiring insights
public int[][] allPathsSourceTarget(int[][] graph) {
  // Write your code here.
}
graph[[1,2],[3],[3],[]]
expected[[0,1,3],[0,2,3]]
Checking account…