Discussion on Java Visitor Pattern Challenge

Sort by

recency

|

192 Discussions

|

5 days ago+ 0 comments

class SumInLeavesVisitor extends TreeVis {
    private int sum = 0;

    public int getResult() {
        return sum;
    }

    public void visitNode(TreeNode node) {
        // No action needed for internal nodes in this visitor
    }

    public void visitLeaf(TreeLeaf leaf) {
        sum += leaf.getValue();
    }
}

class ProductOfRedNodesVisitor extends TreeVis {
    private double product = 1;

    public int getResult() {
        return (int) product;
    }

    public void visitNode(TreeNode node) {
        increaseProduct(node);
    }

    public void visitLeaf(TreeLeaf leaf) {
        increaseProduct(leaf);
    }

    private void increaseProduct(Tree tree) {
        if (tree.getColor() == Color.RED) {
            product = (product * tree.getValue()) % (Math.pow(10, 9) + 7);
        }
    }
}

class FancyVisitor extends TreeVis {
    private int nonLeafNodeSum = 0;
    private int greenLeafSum = 0;

    public int getResult() {
        return Math.abs(nonLeafNodeSum - greenLeafSum);
    }

    public void visitNode(TreeNode node) {
        if (node.getDepth() % 2 == 0) {
            nonLeafNodeSum += node.getValue();
        }
    }

    public void visitLeaf(TreeLeaf leaf) {
        if (leaf.getColor() == Color.GREEN) {
            greenLeafSum += leaf.getValue();
        }
    }
}

public class Solution {
  
    public static Tree solve() {
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());
        String valuesLine = scan.nextLine();
        String colorsLine = scan.nextLine();

        String[] valuesStr = valuesLine.split(" ");
        int[] values = new int[n];

        for (int i = 0; i < n; i++) {
            values[i] = Integer.parseInt(valuesStr[i]);
        }

        String[] colorsStr = colorsLine.split(" ");
        byte[] colors = new byte[n];
        
        for (int i = 0; i < n; i++) {
            colors[i] = (byte) Integer.parseInt(colorsStr[i]);
        }

        Map<Integer, List<Integer>> adj = new HashMap<>();
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            adj.put(i, new ArrayList<Integer>());
        }

        while (scan.hasNextInt()) {
            int u = scan.nextInt() - 1;
            int v = scan.nextInt() - 1;
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        scan.close();
        
        return buildTree(0, 0, values, colors, adj, visited);
    }

    public static Tree buildTree(
        int index, int depth, int[] values, byte[] colors, Map<Integer, List<Integer>> adj, boolean[] visited
    ) {
        boolean isLeaf = true;
        visited[index] = true;

        Color color = colors[index] == 0 ? Color.RED : Color.GREEN;
        List<Integer> children = adj.get(index);
        TreeNode treeNode = new TreeNode(values[index], color, depth);

        for (int child : children) {
            if (!visited[child]) {
                isLeaf = false;
                Tree childNode = buildTree(child, depth + 1, values, colors, adj, visited);
                treeNode.addChild(childNode);
            }
        }

        if (isLeaf) {
            return new TreeLeaf(values[index], color, depth);
        } else {
            return treeNode;
        }
    }

6 days ago+ 0 comments

This problem leads one to believe that the input data is a tree. But in fact, it is an undirected graph. The lack of this information made me waste a lot of time solving the problem.

1 month ago+ 0 comments

Here is Java visitor pattern solution - https://programmingoneonone.com/hackerrank-java-visitor-pattern-problem-solution.html

3 months ago+ 1 comment

class SumInLeavesVisitor extends TreeVis { public int getResult() { //implement this return leavesValuesCounter; }

public void visitNode(TreeNode node) {
    //implement this
}

public void visitLeaf(TreeLeaf leaf) {
    //implement this

    if (leaf == null) {
        return;
    }

    leavesValuesCounter += leaf.getValue();
}

// private private int leavesValuesCounter = 0; }

class ProductOfRedNodesVisitor extends TreeVis { public int getResult() { //implement this return productOfRedNodesCounter; }

public void visitNode(TreeNode node) {
    //implement this
    if (node == null)
        return;

    if (node.getColor() == Color.RED) {
        int value = node.getValue();
        value = (value == 0) ? 1 : value;

        productOfRedNodesCounter = (int)(((long)productOfRedNodesCounter * value) % MODULE);
    }
}

public void visitLeaf(TreeLeaf leaf) {
    //implement this

    if (leaf == null)
        return;

    if (leaf.getColor() == Color.RED) {
        int value = leaf.getValue();
        value = (value == 0) ? 1 : value;

        productOfRedNodesCounter = (int)(((long)productOfRedNodesCounter * value) % MODULE);
    }
}

private int productOfRedNodesCounter = 1;
final int MODULE = 1000000007;

}

class FancyVisitor extends TreeVis { public int getResult() { //implement this return Math.abs(sumGreenLeafNodes - sumNonLeafNodes); }

public void visitNode(TreeNode node) {
    //implement this
    if (node == null)
        return;

    if (node.getDepth() % 2 == 0) {
        sumNonLeafNodes += node.getValue();
    }
}

public void visitLeaf(TreeLeaf leaf) {
    //implement this

    if (leaf == null)
        return;

    if (leaf.getColor() == Color.GREEN) {
        sumGreenLeafNodes += leaf.getValue();
    }
}

private int sumNonLeafNodes = 0;
private int sumGreenLeafNodes = 0;

}

public class Solution {

private static boolean isALeaf(List<List<Integer>> adjacencyTable,
                            boolean[] visited, int elementPosition) {
    if (adjacencyTable.get(elementPosition).isEmpty()) {
        return true;
    }

    for (int i = 0; i < adjacencyTable.get(elementPosition).size(); i++) {
        Integer recordedValue = adjacencyTable.get(elementPosition).get(i);
        if (!visited[recordedValue]) {
            return false;
        }
    }

    return true;
}


private static Tree createTheTree(List<List<Integer>> adjacencyTable,
                                 boolean[] visited, int[] nodeCosts, int[] colors, int parentDepth,
                                 int elementPosition) {

    int localDepth = parentDepth + 1;
    if (isALeaf(adjacencyTable, visited, elementPosition)) {
        return new TreeLeaf(nodeCosts[elementPosition],
                colors[elementPosition] == 1 ? Color.GREEN : Color.RED,
                localDepth );
    }

    TreeNode currentNode = new TreeNode(nodeCosts[elementPosition],
            colors[elementPosition] == 1 ? Color.GREEN : Color.RED,
            localDepth);

    visited[elementPosition] = true;

    for (int i = 0; i < adjacencyTable.get(elementPosition).size(); i++) {
        Integer recordedValue = adjacencyTable.get(elementPosition).get(i);
        if (!visited[recordedValue]) {
            Tree child = createTheTree(adjacencyTable, visited, nodeCosts, colors,
                    localDepth, recordedValue);
            currentNode.addChild(child);
        }
    }

    return currentNode;
}


public static Tree solve() {
    //read the tree from STDIN and return its root as a return value of this function
    Scanner myObj = new Scanner(System.in);
    int nodesCount = myObj.nextInt();

    int[] nodeCosts = new int[nodesCount];
    int[] colors = new int[nodesCount];

    for (int i = 0; i < nodesCount; i++) {
        nodeCosts[i] = myObj.nextInt();
    }

    for (int i = 0; i < nodesCount; i++) {
        colors[i] = myObj.nextInt();
    }

    List<List<Integer>> adjacencyTable = new ArrayList<>(nodesCount);
    for (int i = 0; i < nodesCount; i++) {
        adjacencyTable.add(new ArrayList<Integer>());
    }

    boolean[] visited = new boolean[nodesCount];

    int decrement = nodesCount - 1;
    while (decrement > 0) {
        int u = myObj.nextInt();
        int v = myObj.nextInt();

        adjacencyTable.get(u - 1).add(v - 1);
        adjacencyTable.get(v - 1).add(u - 1);

        decrement--;
    }

    Tree result = createTheTree(adjacencyTable, visited, nodeCosts, colors, -1, 0);
    return result;
}

3 months ago+ 0 comments

This is my take on this problem:

Nowhere in the problem it is stated that one of the two nodes of an edge is 100% the parent. Which means, you cannot assume it.
You can work yourself through construction level by level, with a queue. Dequeue the next potential parent, and enqueue all implemented children. Save all edges in an adjacent list, then implement this strategy.
Mark all visited nodes! You don't want to accidentally attatch a parent as another child.
Modulo needs clarification. You are expected to use it on every calculation for every node, and not on the final sum.

This is my solution:

class SumInLeavesVisitor extends TreeVis {
    private int sumInLeavesVisitor = 0;
    public int getResult() {
      	//implement this
        return sumInLeavesVisitor;
    }

    public void visitNode(TreeNode node) {
      	//implement this
    }

    public void visitLeaf(TreeLeaf leaf) {
      	//implement this
        sumInLeavesVisitor += leaf.getValue();
    }
}

class ProductOfRedNodesVisitor extends TreeVis {
    private int productOfRedNodesVisitor = 1;
    final private int mod = 1000000007;
    public int getResult() {
      	//implement this
        return productOfRedNodesVisitor;
    }

    public void visitNode(TreeNode node) {
      	//implement this
        if(node.getColor() == Color.RED)productOfRedNodesVisitor = (int)(((long)productOfRedNodesVisitor * node.getValue()) % mod);
    }

    public void visitLeaf(TreeLeaf leaf) {
      	//implement this
        if(leaf.getColor() == Color.RED)productOfRedNodesVisitor = (int)(((long)productOfRedNodesVisitor * leaf.getValue()) % mod);
    }
}

class FancyVisitor extends TreeVis {
    private int nonLeafValue = 0;
    private int leafValue = 0;
    public int getResult() {
      	//implement this
        int difference = leafValue - nonLeafValue;
        return Math.abs(difference);
    }

    public void visitNode(TreeNode node) {
    	//implement this
        if(node.getDepth() % 2 == 0)nonLeafValue += node.getValue();
    }

    public void visitLeaf(TreeLeaf leaf) {
    	//implement this
        if(leaf.getColor() == Color.GREEN)leafValue += leaf.getValue();
    }
}

public class Solution {
  
    public static Tree solve() {
        //read the tree from STDIN and return its root as a return value of this function
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nodeValues = new int[n];
        Color[] nodeColors = new Color[n];
        List<List<Integer>> adjList = new ArrayList<>();
        
        for(int i = 0; i < n; i++){
            nodeValues[i] = sc.nextInt();
            adjList.add(new ArrayList<Integer>());
        }
        for(int i = 0; i < n; i++){
            nodeColors[i] = sc.nextInt() == 0 ? Color.RED : Color.GREEN;
        }
        
        Tree[] treeNodes = new Tree[n];
        treeNodes[0] = new TreeNode(nodeValues[0], nodeColors[0], 0);
        Queue<Integer> parentQueue = new LinkedList<>();
        parentQueue.add(0);
        boolean[] visited = new boolean[n];
        visited[0] = true;
        
        for(int i = 0; i < n - 1; i++){
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }
        while(!parentQueue.isEmpty()){
            int parentIndex = parentQueue.poll();
            Tree parent = treeNodes[parentIndex];
            for(int childIndex : adjList.get(parentIndex)){
                if(!visited[childIndex]){
                    Tree child;
                    if(adjList.get(childIndex).size() == 1){
                        child = new TreeLeaf(nodeValues[childIndex], nodeColors[childIndex], parent.getDepth() + 1);
                    }
                    else{
                        child = new TreeNode(nodeValues[childIndex], nodeColors[childIndex], parent.getDepth() + 1);
                    }
                    treeNodes[childIndex] = child;
                    visited[childIndex] = true;
                    parentQueue.add(childIndex);
                    ((TreeNode) parent).addChild(child);   
                }
            }
        }
        return treeNodes[0];
        
    }

Sort by

|

192 Discussions

|

Cookie support is required to access HackerRank