1

I just failed the google coding challenge level-4 conducted in foobar site. My code works most of the time but throws null pointer exception for specific set of inputs which I am not aware of. If any one is interested in solving puzzle coding question, could you please help me find the input for which below solution ends in null pointer exception? I also welcome comments on my code when it fails good coding etiquette or entire alternate simple and more efficient solution. Thank. (PS- Hope I am not violating any rules and stuff sharing the below question asked in google coding challenge)

Problem statement- Given the starting room numbers of the groups of bunnies, the room numbers of the escape pods, and how many bunnies can fit through at a time in each direction of every corridor in between, figure out how many bunnies can safely make it to the escape pods at a time at peak. Write a function answer(entrances, exits, path) that takes an array of integers denoting where the groups of gathered bunnies are, an array of integers denoting where the escape pods are located, and an array of an array of integers of the corridors, returning the total number of bunnies that can get through at each time step as an int. The entrances and exits are disjoint and thus will never overlap. The path element path[A][B] = C describes that the corridor going from A to B can fit C bunnies at each time step. There are at most 50 rooms connected by the corridors and at most 2000000 bunnies that will fit at a time.

For example, if you have:

entrances = [0, 1],
exits = [4, 5], 
path = [,  
# Room 0: Bunnies,           [0, 0, 4, 6, 0, 0],  
# Room 1: Bunnies,           [0, 0, 5, 2, 0, 0],  
# Room 2: Intermediate room, [0, 0, 0, 0, 4, 4],  
# Room 3: Intermediate room  [0, 0, 0, 0, 6, 6],  
# Room 4: Escape pods,       [0, 0, 0, 0, 0, 0],  
# Room 5: Escape pods        [0, 0, 0, 0, 0, 0]
]

Then in each time step, the following might happen:

0 sends 4/4 bunnies to 2 and 6/6 bunnies to 3
1 sends 4/5 bunnies to 2 and 2/2 bunnies to 3
2 sends 4/4 bunnies to 4 and 4/4 bunnies to 5
3 sends 4/6 bunnies to 4 and 4/6 bunnies to 5

So, in total, 16 bunnies could make it to the escape pods at 4 and 5 at each time step. (Note that in this example, room 3 could have sent any variation of 8 bunnies to 4 and 5, such as 2/6 and 6/6, but the final answer remains the same.)

Test cases

Inputs:entrances = [0], exits = [3], path = [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]] then Output:6

Inputs:entrances = [0, 1], exits = [4, 5], path = [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]  Output: 16

My solution:

public class Answer {
    public static void main(String[] args) {
        //input 1
        int[] entrances = {0, 1};
        int[] exits = {4, 5};
        int[][] path = {{1, 0, 4, 6, 0, 0},
                {0, 1, 5, 2, 0, 0},
                {0, 0, 1, 0, 4, 4},
                {0, 0, 0, 1, 6, 6},
                {0, 0, 0, 0, 1, 0},
                {0, 0, 0, 0, 0, 1}};
        System.out.println("*****************************************for input 1:"+answer(entrances, exits, path));
        //input 2
        entrances = new int[]{0};
        exits = new int[]{3};
        path = new int[][]{ {0, 7, 0, 0},
                {0, 0, 6, 0},
                {0, 0, 0, 8},
                {9, 0, 0, 0} };
        System.out.println("*****************************************for input 2:"+answer(entrances, exits, path));
        //input with loop 1
        entrances = new int[]{0,2};
        exits = new int[]{4};
        path = new int[][]{ {0, 3, 0, 0, 0},
                {0, 0, 2, 0, 5},
                {0, 0, 0, 4, 0},
                {0, 6, 0, 0, 0},
                {0, 0, 0, 0, 0} };
        System.out.println("*****************************************for input 3:"+answer(entrances, exits, path));
        //input with loop 2
        entrances = new int[]{0,1};
        exits = new int[]{4,5};
        path = new int[][]{ {0, 0, 10, 0, 0, 0},
                            {0, 0, 0, 8, 0, 0},
                            {0, 0, 0, 4, 6, 0},
                            {0, 0, 4, 0, 0, 12},
                            {0, 0, 0, 0, 0, 0},
                            {0, 0, 0, 0, 0, 0}};
        System.out.println("*****************************************for input 4:"+answer(entrances, exits, path));

        entrances = new int[]{0};
        exits = new int[]{0};
        path = new int[][]{ {0} };
        System.out.println("*****************************************for input 5:"+answer(entrances, exits, path));
    }

    public static final int SOME_BIG_VALUE = 2146999999;

    public static int answer(int[] entrances, int[] exits, int[][] path) {
        if (path == null || entrances == null || exits == null){
            return 0;
        }
        if(path.length<2 || entrances.length<1 || exits.length<1){
            return 0;
        }
        //below makes difference with one test case
        for (int i = 0; i < path.length; i++) {
            for (int j = 0; j <path[i].length ; j++) {
                if(i==j)
                    path[i][j]=0;
            }
        }
        //creating all nodes
        ArrayList<Node> nodes = new ArrayList<>();
        for (int i = 0; i < path.length; i++) {
            nodes.add(new Node(i));
        }
        Node.constructGraph(path, nodes);

        int total = 0;
        for(int src:entrances) {
            //System.out.println("for src: "+ src);
            Node start = nodes.get(src);
            int pathCapacity = 0;
            do {
                if(start.discard)
                    break;
                pathCapacity = findCapacityOfLoopLessPath(src, exits, nodes);
                total = total + pathCapacity;
            } while (pathCapacity != 0);
        }
        return total;
    }

    /**
     *Returns >0 if valid path is found between src and one of the exits
     * Returns  0 if valid path is not found between src and any of exits
     * Apart, below function   *overcomes the loop while finding the path
     *alters graph as new paths are  discovered
     *removes dead-end path frm src to non-exit
     */
    public static int findCapacityOfLoopLessPath(int src, int[] exits, ArrayList<Node> nodes) {
        ArrayList<Node> path = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        Node start = nodes.get(src);
        stack.push(start);

        boolean reachedExit = modifiedDFS(path, stack, exits);
        int smallestCorridorSizeInPath = 0;
        if(!reachedExit){
            return smallestCorridorSizeInPath;
        }
        else{
            smallestCorridorSizeInPath = findSmallestCorridorSizeInPath(path);
            if(smallestCorridorSizeInPath != SOME_BIG_VALUE) {
                reduceCorridorSizeInPath(path, smallestCorridorSizeInPath, exits);
                return smallestCorridorSizeInPath;
            }
        }
        return smallestCorridorSizeInPath;
    }

    /**
     * Does dfs until one of the exit is reached
     * Parallelly putting nodes into path as they get discovered to reach the one of exits
     */
    private static boolean modifiedDFS(ArrayList<Node> path, Stack<Node> stack, int[] exits) {
        while(!stack.empty()) {
            Node current = stack.pop();
            if(Node.isNodeInPath(current, path)) {
                return modifiedDFS(path,stack,exits);
            }else {
                path.add(current);
            }
            if(isNodeOneOfExits(current,exits)) {
                return true;
            }
            HashMap<Node, Integer> corridorWeightToReachNextNode = current.getCorridorWeightToReachNextNode();
            for(Node node:corridorWeightToReachNextNode.keySet()) {
                if(!stack.contains(node) && !node.discard)
                    stack.push(node);
            }
        }
        return false;
    }

    public static int findSmallestCorridorSizeInPath(ArrayList<Node> path) {
        if(path.size() < 2){
            return 0;//may be if exception is thrown then we can debug more easily
        }
        int smallestCorridorSizeInPath = SOME_BIG_VALUE;

        //System.out.print("path : ");
        for (int j = 0; j <path.size() ; j++) {
            //System.out.print(path.get(j).toString()+", ");
        }

        int i;
        for (i = 0; i < path.size()-1; i++) {
            Node currentNode = path.get(i);
            Node nextNode = path.get(i+1);
            HashMap<Node, Integer> corridorWeightToReachNextNode = currentNode.getCorridorWeightToReachNextNode();
            if(corridorWeightToReachNextNode.get(nextNode)<smallestCorridorSizeInPath) {
                smallestCorridorSizeInPath = corridorWeightToReachNextNode.get(nextNode);
            }
        }
        //System.out.println("shortest corridor size in the path:" + smallestCorridorSizeInPath);
        return smallestCorridorSizeInPath;
    }

    /**
     * reduce corridor size of each in path by smallestCorridorSizeInPath
     * Removes the corresponding path with that smallest size from the graph
     * by removing respective node with smallestCorridorSizeInPath from  corridorWeightToReachNextNode
     * Also, makes node.discard = true if node's nextNode list is empty
     */
    public static void reduceCorridorSizeInPath(ArrayList<Node> path, int smallestCorridorSizeInPath, int[] exits) {
        if(path == null || exits == null){
            return;
        }
        if(path.size()<2 && exits.length==0)
            return;
        for (int i = 0; i < path.size()-1 ; i++) {
            Node currentNode = path.get(i);
            Node nextNode = path.get(i+1);
            if(currentNode==null || nextNode==null){
                return;
            }
            HashMap<Node, Integer> corridorWeightToReachNextNode = currentNode.getCorridorWeightToReachNextNode();
            if(corridorWeightToReachNextNode==null || corridorWeightToReachNextNode.size()==0) {
                return;
            }
            if(corridorWeightToReachNextNode.get(nextNode)==null) {
                return;
            }
            int currentCorridorSize = 0;
            currentCorridorSize = corridorWeightToReachNextNode.get(nextNode);
            if(currentCorridorSize==0 || currentCorridorSize == SOME_BIG_VALUE){
                return;
            }

            corridorWeightToReachNextNode.put(nextNode, (currentCorridorSize-smallestCorridorSizeInPath));
            if(currentCorridorSize == smallestCorridorSizeInPath) {
                corridorWeightToReachNextNode.remove(nextNode);
                if(corridorWeightToReachNextNode.size()==0 && !isNodeOneOfExits(currentNode,exits)) {
                    currentNode.discard = true;
                    //System.out.println("discarded node:"+ currentNode.toString());
                }
            }
        }
    }

    public static boolean isNodeOneOfExits(Node node, int[] exits) {
        for (int i = 0; i < exits.length; i++) {
            if(node.getIndex() == exits[i])
                return true;
        }
        return false;
    }}

    class Node {
    int index;
    HashMap<Node, Integer> corridorWeightToReachNextNode = null;
    Boolean discard = false;
    public Node(int index) {
        this.index = index;
        corridorWeightToReachNextNode = new HashMap<>();
    }
    public int getIndex() {
        return index;
    }

    public HashMap<Node, Integer> getCorridorWeightToReachNextNode() {
        return corridorWeightToReachNextNode;
    }

    public static Node constructGraph(int[][] matrix, List<Node> nodes) {
        for(int i = 0; i < matrix.length; i++) {
            Node currentNode = nodes.get(i);
            for(int j=0; j<matrix[i].length; j++) {
                if(matrix[i][j] != 0) {
                    Node nextNode = nodes.get(j);
                    currentNode.corridorWeightToReachNextNode.put(nextNode,matrix[i][j]);
                }
            }
        }
        return nodes.get(0);
    }

    @Override
    public boolean equals(Object obj) {
        Node node = (Node)obj;
        if(node.index == this.index)
            return true;
        return false;
    }
    @Override
    public int hashCode() {
        return index % 2;
    }

    @Override
    public String toString() {
        return Integer.toString(this.index);
    }

    public static boolean isNodeInPath(Node n, ArrayList<Node> path) {
        if(path == null || n == null) {
            return false;
        }
        boolean alreadyInPath = false;
        for( Node nodeInPath : path) {
            if(nodeInPath.equals(n))
                return true;
        }
        return false;
    }
}
4
  • Am I right, you cannot provide us with an input that throws a NPE, but you know for some it does? Have you tried a try-catch(NullPointerException) around each input and print the offending input?
    – JFBM
    Jul 6, 2017 at 9:25
  • Yes. I did try try-catch, but no proper conclusion. Thing is foobar site is like a "black box", once you submit the code, it just tells if code works for all test cases or not. It either tells "all test cases are passed" or tells about exception being thrown. It does not provide feedback as to which input test case code is failing
    – Shivakumar
    Jul 6, 2017 at 10:06
  • The path array is actually an array of array references. What would happen if path were defined as: {{1,2,3},{4,5,6},null}? I don't know if that's the correct Java syntax, but the point is that somebody could pass a path where path[2] is equal to null. That'd ruin your day. Jul 6, 2017 at 11:42
  • Ouch... I missed this input validation. Thanks for your time and effort @JimMischel
    – Shivakumar
    Jul 7, 2017 at 1:49

1 Answer 1

3

Your problem: The path you construct contains nodes with no exit.

Following example (found by random sampling):

entrances = {0};
exits = {3};
path = {{0, 17, 6, 0}, 
        {0, 0, 0, 0}, 
        {0, 0, 0, 9},
        {16, 0, 0, 0}};

Visualization (created with graphonline.ru)
created with graphonline.ru

Your code starts at the (only) entry-node. It adds all childs to the path in encounter order. Then it explores each child and adds their childs to the path. In the end, before evaluation, this gives the path 0->1->2->3 which is clearly wrong. The only true path is 0->2->3 as indicated in the graphic.
During evaluation of the path you query Node 1s adjacency vector for Node 2. This is where your NullPointerException happens.


The code I used to generate random samples (generates 1000 samples with reproducible results and one entry/exit node)

// My random samples
Random random = new Random(0L);

int pathSize = 4;

for (int i = 0; i < 1000; i++) {
    entrances = new int[]{0};
    //Arrays.setAll(entrances, j -> random.nextInt(0+1));

    exits = new int[]{pathSize - 1};
    //Arrays.setAll(exits, j -> random.nextInt(pathSize));

    path = new int[pathSize][pathSize];
    Arrays.setAll(path, j -> IntStream.generate(() -> random.nextInt(20)).limit(pathSize).toArray());

    for (int j = 0; j < path.length; j++) {
        path[j][j] = 0;
    }

    for (int j = 0; j < path.length; j++) {
        for (int k = 0; k < path[j].length; k++) {
            path[j][k] = random.nextDouble() < 0.75 ? 0 : path[j][k];
        }
    }

    try {
        answer(entrances, exits, path);
    } catch (Exception e) {
        System.err.println("[" + String.format("%02d", i) + "] Threw an exception for inputs " + Arrays.toString(entrances) + ", " + Arrays.toString(exits) + ", " + Arrays.deepToString(path));
        e.printStackTrace();
    }
}

Now, some random code-review:

//below makes difference with one test case
for (int i = 0; i < path.length; i++) {
    for (int j = 0; j < path[i].length; j++) {
        if (i == j)
            path[i][j] = 0;
    }
}

From what I can see, path is always a square-array. If that holds true, you can remove the inner loop.

You have SOME_BIG_VALUE. Why not use Integer.MAX_VALUE? You can't get any bigger than that.

3
  • damn.. Thanks for your time and efforts.Guess I should have put more thought about validating the input instead I kept messing with other part of code.
    – Shivakumar
    Jul 7, 2017 at 1:48
  • And you could have shown your appreciation by accepting that carefully created answer.
    – GhostCat
    Sep 11, 2017 at 11:21
  • Did it. I just didn't notice/knew "accept" concept earlier.
    – Shivakumar
    Sep 14, 2018 at 1:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.