We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Java
  3. Advanced
  4. Java Visitor Pattern
  5. Discussions

Java Visitor Pattern

Sort by

recency

|

188 Discussions

|

  • resejakow2
     + 0 comments

    This is my take on this problem:

    1. 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.

    2. 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.

    3. Mark all visited nodes! You don't want to accidentally attatch a parent as another child.

    4. 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];
        
    }

  • jmerritt45
     + 1 comment

    For my solution, the problem statement requires some clarification.

    1. A leaf node has only 1 edge.
    2. You are constructing an undirected graph.
    3. 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.
    4. You may need to have multiple passes through the edges to construct the depth array.
    5. Use the depth array to determine if you call addChild.

    • jmerritt45
       + 0 comments

      Further information. The data comes from "Test Case 1". Here is the graph assuming that u->v is a parent->child edge. But, several have to be swapped for this problem (left as an exercise for the reader). The first image (input1.png) shows the graph before swapping, and it shows multiple roots. Most of the graph is not reachable starting at node 1 (each node shows the node number and the value). The second image (input_oneTree.png) shows the graph you need to build for the HR test to be successful.

      https://github.com/johnnyski/tc1/blob/main/input1.png https://github.com/johnnyski/tc1/blob/main/input1_oneTree.png

  • KCarot
     + 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];
    }

  • KCarot
     + 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];
    }

  • pw_hackerrank
     + 0 comments

    The problem description is tricky and easily misleading. Specifically it says:

    ...Each of the subsequent lines contains two space-separated integers, *ui* and *vi* , describing an edge between nodes *u* and *v*.

    An edge input like this:

    3 4

    does not mean that 3 is the parent. The parent may as well be noted on the right side. The correct interpretation:

    There is just a link between 3 and 4, it's unspecified which one is tree node/leaf node.

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in