Discussion on Java Visitor Pattern Challenge

Sort by

recency

|

189 Discussions

|

2 weeks 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 weeks 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];
        
    }

1 month ago+ 1 comment

For my solution, the problem statement requires some clarification.

A leaf node has only 1 edge.
You are constructing an undirected graph.
For an edge (u,v), most of the time u is the parent and v is the child, however, the order can be (v,u). That can happen when v is a child with a known depth and u has not had a depth assigned. -- This is the magic. Yes, a very unorthodox way to construct a graph.
You may need to have multiple passes through the edges to construct the depth array.
Use the depth array to determine if you call addChild.

5 months ago+ 0 comments

I reviewed some comments, and find more efficient data structure to solve whever use recursive or non recursive way. Recursive:

static int[] values;
    static Color[] colors;
    static Map<Integer, Set<Integer>> nodeMap = new HashMap<>();
    public static Tree solve() {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        values = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();
        colors = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt)
                .mapToObj(c -> c == 0 ? Color.RED : Color.GREEN).toArray(Color[]::new);

        for (int i = 0; i < n - 1; ++i) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;

            Set<Integer> linkedNodes = nodeMap.get(u);
            if (linkedNodes == null) {
                linkedNodes = new HashSet<>();
            }
            linkedNodes.add(v);
            nodeMap.put(u, linkedNodes);

            linkedNodes = nodeMap.get(v);
            if (linkedNodes == null) {
                linkedNodes = new HashSet<>();
            }
            linkedNodes.add(u);
            nodeMap.put(v, linkedNodes);
        }

        Tree root = new TreeNode(values[0], colors[0], 0);
        buildTree(root, 0);

        sc.close();
        return root;
    }

    private static void buildTree(Tree parentNode, int u) {
        Set<Integer> uLinkedNodes = nodeMap.get(u);
        uLinkedNodes.forEach(v -> {
            Set<Integer> vLinkedNodes = nodeMap.get(v);
            vLinkedNodes.remove(u);
            Tree childNode = null;
            if (vLinkedNodes.isEmpty()) {
                childNode = new TreeLeaf(values[v], colors[v], parentNode.getDepth() + 1);
            } else {
                childNode = new TreeNode(values[v], colors[v], parentNode.getDepth() + 1);
            }
            ((TreeNode) parentNode).addChild(childNode);
            buildTree(childNode, v);
        });
    }

Non recutsive:

    static Color[] colors;
    static Map<Integer, Set<Integer>> nodeMap = new HashMap<>();
    static Tree[] tree;
    public static Tree solve() {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        values = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();
        colors = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt)
                .mapToObj(c -> c == 0 ? Color.RED : Color.GREEN).toArray(Color[]::new);
        tree = new Tree[n];
        
        for (int i = 0; i < n - 1; ++i) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            
            Set<Integer> linkedNodes = nodeMap.get(u);
            if (linkedNodes == null) {
                linkedNodes = new HashSet<>();
            }
            linkedNodes.add(v);
            nodeMap.put(u, linkedNodes);
            
            linkedNodes = nodeMap.get(v);
            if (linkedNodes == null) {
                linkedNodes = new HashSet<>();
            }
            linkedNodes.add(u);
            nodeMap.put(v, linkedNodes);
        }
        
        tree[0] = new TreeNode(values[0], colors[0], 0);
        
        Set<Integer> levelSet = new HashSet<>();
        levelSet.add(0);
        Set<Integer> nextLevelSet = new HashSet<>();
        while (!levelSet.isEmpty()) {
            for (int u : levelSet) {
                Set<Integer> uLinkedNodes = nodeMap.get(u);
                uLinkedNodes.forEach(v -> {
                    Set<Integer> vLinkedNodes = nodeMap.get(v);
                    vLinkedNodes.remove(u);
                    if (vLinkedNodes.isEmpty()) {
                        tree[v] = new TreeLeaf(values[v], colors[v], tree[u].getDepth() + 1);
                    } else {
                        tree[v] = new TreeNode(values[v], colors[v], tree[u].getDepth() + 1);
                    }
                    ((TreeNode) tree[u]).addChild(tree[v]);
                    nextLevelSet.add(v);
                });
            }
            levelSet.clear();
            levelSet.addAll(nextLevelSet);
            nextLevelSet.clear();
        }

        sc.close();
        return tree[0];
    }

5 months ago+ 0 comments

I have to say that before you submit, you probably won't know that the edge is not pointing from the parent node to the descendant node, and you won't know that the order in which nodes appear is not top-down...

It seems that several exercises have encountered similar problems in my memory, which has lowered the impression of this website in my mind。

In the end, it took a lot of time to improve and perfect, and a non recursive tree building process was implemented.Only posted the process of building the tree, by the way, it uses Java8.

public static Tree solve() {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        int[] values = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();
        Color[] colors = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt)
                .mapToObj(c -> c == 0 ? Color.RED : Color.GREEN).toArray(Color[]::new);

        int[] edgeCount = new int[n];
        Arrays.fill(edgeCount, 0);
        edgeCount[0] = 1;
        int[] edges = new int[(n - 1) * 2];
        int x, y;
        for (int i = 0; i < edges.length - 1; i += 2) {
            x = sc.nextInt() - 1;
            y = sc.nextInt() - 1;
            edges[i] = x;
            edges[i + 1] = y;

            ++edgeCount[x];
            ++edgeCount[y];
        }

        Tree[] tree = new Tree[n];
        tree[0] = new TreeNode(values[0], colors[0], 0);

        Set<Integer> levelSet = new HashSet<>();
        Set<Integer> tmpSet = new HashSet<>();
        levelSet.add(0);
        while (!levelSet.isEmpty()) {
            for (int i = 0; i < edges.length - 1; i += 2) {
                x = edges[i];
                y = edges[i + 1];
                if (x == -1 || y == -1) {
                    continue;
                }
                if (levelSet.contains(x)) {
                    if (edgeCount[y] > 1) {
                        tree[y] = new TreeNode(values[y], colors[y], tree[x].getDepth() + 1);
                    } else if (edgeCount[y] == 1) {
                        tree[y] = new TreeLeaf(values[y], colors[y], tree[x].getDepth() + 1);
                    } else {
                        throw new RuntimeException("edgeCount error");
                    }
                    ((TreeNode) tree[x]).addChild(tree[y]);
                    tmpSet.add(y);
                    edges[i] = -1;
                    edges[i + 1] = -1;
                } else if (levelSet.contains(y)) {
                    if (edgeCount[x] > 1) {
                        tree[x] = new TreeNode(values[x], colors[x], tree[y].getDepth() + 1);
                    } else if (edgeCount[x] == 1) {
                        tree[x] = new TreeLeaf(values[x], colors[x], tree[y].getDepth() + 1);
                    } else {
                        throw new RuntimeException("edgeCount error");
                    }
                    ((TreeNode) tree[y]).addChild(tree[x]);
                    tmpSet.add(x);
                    edges[i] = -1;
                    edges[i + 1] = -1;
                }
            }
            levelSet.clear();
            levelSet.addAll(tmpSet);
            tmpSet.clear();
        }

        sc.close();
        return tree[0];
    }

Sort by

|

189 Discussions

|

Cookie support is required to access HackerRank