Cracking the Coding Interview

Saptarshi Chatterjee

·

Follow

27 min read

·

Dec 15, 2018

--

Share

1. Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList();
        find(graph, result, new ArrayList(), 0);
        return result;
    }
    public void find(int[][] graph, List<List<Integer>> result, List<Integer> running, int index) {
        running.add(index);//just adding node as it's acyclic.Would check visited otherwise
        if(index == graph.length -1 )…