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.
Useful tutorial for Visitor Pattern However, this problem is more about creating a tree in an obscure format than it is about Visitor patterns.
Common pitfall: The edges of the tree in the provided input are undirected edges. This makes creating a directed and rooted tree challenging.
classSumInLeavesVisitorextendsTreeVis{privateintresult=0;publicintgetResult(){returnresult;}publicvoidvisitNode(TreeNodenode){// do nothing}publicvoidvisitLeaf(TreeLeafleaf){result+=leaf.getValue();}}classProductOfRedNodesVisitorextendsTreeVis{privatelongresult=1;privatefinalintM=1000000007;publicintgetResult(){return(int)result;}publicvoidvisitNode(TreeNodenode){if(node.getColor()==Color.RED){result=(result*node.getValue())%M;}}publicvoidvisitLeaf(TreeLeafleaf){if(leaf.getColor()==Color.RED){result=(result*leaf.getValue())%M;}}}classFancyVisitorextendsTreeVis{privateintnonLeafEvenDepthSum=0;privateintgreenLeavesSum=0;publicintgetResult(){returnMath.abs(nonLeafEvenDepthSum-greenLeavesSum);}publicvoidvisitNode(TreeNodenode){if(node.getDepth()%2==0){nonLeafEvenDepthSum+=node.getValue();}}publicvoidvisitLeaf(TreeLeafleaf){if(leaf.getColor()==Color.GREEN){greenLeavesSum+=leaf.getValue();}}}publicclassSolution{privatestaticint[]values;privatestaticColor[]colors;privatestaticHashMap<Integer,HashSet<Integer>>map;publicstaticTreesolve(){Scannerscan=newScanner(System.in);intnumNodes=scan.nextInt();/* Read and save nodes and colors */values=newint[numNodes];colors=newColor[numNodes];map=newHashMap<>(numNodes);for(inti=0;i<numNodes;i++){values[i]=scan.nextInt();}for(inti=0;i<numNodes;i++){colors[i]=scan.nextInt()==0?Color.RED:Color.GREEN;}/* Save edges */for(inti=0;i<numNodes-1;i++){intu=scan.nextInt();intv=scan.nextInt();/* Edges are undirected: Add 1st direction */HashSet<Integer>uNeighbors=map.get(u);if(uNeighbors==null){uNeighbors=newHashSet<>();map.put(u,uNeighbors);}uNeighbors.add(v);/* Edges are undirected: Add 2nd direction */HashSet<Integer>vNeighbors=map.get(v);if(vNeighbors==null){vNeighbors=newHashSet<>();map.put(v,vNeighbors);}vNeighbors.add(u);}scan.close();/* Handle 1-node tree */if(numNodes==1){returnnewTreeLeaf(values[0],colors[0],0);}/* Create Tree */TreeNoderoot=newTreeNode(values[0],colors[0],0);addChildren(root,1);returnroot;}/* Recursively adds children of a TreeNode */privatestaticvoidaddChildren(TreeNodeparent,IntegerparentNum){/* Get HashSet of children and loop through them */for(IntegertreeNum:map.get(parentNum)){map.get(treeNum).remove(parentNum);// removes the opposite arrow direction/* Add child */HashSet<Integer>grandChildren=map.get(treeNum);booleanchildHasChild=(grandChildren!=null&&!grandChildren.isEmpty());Treetree;if(childHasChild){tree=newTreeNode(values[treeNum-1],colors[treeNum-1],parent.getDepth()+1);}else{tree=newTreeLeaf(values[treeNum-1],colors[treeNum-1],parent.getDepth()+1);}parent.addChild(tree);/* Recurse if necessary */if(treeinstanceofTreeNode){addChildren((TreeNode)tree,treeNum);}}}
haha Im going to have to cite you on my github. After seeing your Java solutions its impossible to think of a cleaner way to implement.
If you have time please elaborate on why using a long for result in the ProductOfRedNodesVisitor class passes all tests while using an int only passes the first test.
I have cited you and I could probably figure it out, but I must admit after learning that the problem is poorly worded and doesnt really teach anything new, I copied your code. Please let me know if you would like me to cite your work with a name different than rshaghoulian.
I usually post the most up-to-date solutions in my HackerRank solutions. You can cite that if you like, any citation method is fine, I wasn't even expecting one, so thanks.
The code uses a long instead of an int to avoid integer overflow. The maximum value of an int is about 2 billion. The exact value can be respresented in the code as Integer.MAX_VALUE. Any time you multiply a lot of numbers together, you must be careful of avoiding integer overflow. This was a actually a pitfall that my friend came across in an interview.
Since we can have 10000 nodes (according to the problem constraint) where each node can have value up to 1000, multiplying these numbers can easily exceed ~2 billion. Using a long lets us store these larger numbers. If for some reason a long is not big enough, you can use a BigInteger, which is loads of fun and can store numbers of any size.
Hi, your solution is very neat. I like it. And do you have any second thought on handing one node tree. You didn't actually put anything into values[] and colors[] yet.
/* Handle 1-node tree */if(numNodes==1){returnnewTreeLeaf(values[0],colors[0],0);}
here, I can't figure out the difference between the two conditions "grandChildren != null" and "!grandChildren.isEmpty()"
both appear similiar to me but if I OR them instead of AND,obviously it produces wrong output...can you please explain them??
1) You definitely need to add the reverse edges too because the graph is an undirected graph (even though it's a little unclear from the problem statement). Not adding the reverse edges would mean you are not creating the intended graph so you will get wrong results.
2) If you want to do grandChildren.isEmpty(), it might be the case that grandChildren is null, and that will give a null pointer exception. For this reason, we first make sure that grandChildren != null before using the dot (.) operator on it.
I made a slightly shorter version, but your answer was definitely pointing me to the right direction, so thank you! :)
This challenge was way over the top for the original task.
class SumInLeavesVisitor extends TreeVis {
private int result;
public int getResult() {
return result;
}
public void visitNode(TreeNode node) {
// Do nothing here
}
public void visitLeaf(TreeLeaf leaf) {
result += leaf.getValue();
}
}
class ProductOfRedNodesVisitor extends TreeVis {
private static int M = 1000000007;
private long result = 1;
public int getResult() {
return (int)result;
}
public void visitNode(TreeNode node) {
if (node.getColor() == Color.RED) {
result = (result * node.getValue()) % M;
}
}
public void visitLeaf(TreeLeaf leaf) {
if (leaf.getColor() == Color.RED) {
result = (result * leaf.getValue()) % M;
}
}
}
class FancyVisitor extends TreeVis {
int greenLeafSum = 0;
int evenNodeSum = 0;
public int getResult() {
return Math.abs(evenNodeSum - greenLeafSum);
}
public void visitNode(TreeNode node) {
if (node.getDepth() % 2 == 0) {
evenNodeSum += node.getValue();
}
}
public void visitLeaf(TreeLeaf leaf) {
if (leaf.getColor() == Color.GREEN) {
greenLeafSum += leaf.getValue();
}
}
}
public class Solution {
public static Tree solve() {
Scanner scanner = new Scanner(System.in);
int numNodes = scanner.nextInt();
int[] values = new int[numNodes];
for (int i=0; i<numNodes; i++) {
values[i] = scanner.nextInt();
}
Color[] colors = new Color[numNodes];
for (int i=0; i<numNodes; i++) {
colors[i] = (scanner.nextInt() == 0) ? Color.RED : Color.GREEN;
}
HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
for (int i=0; i<numNodes-1; i++) {
int u = scanner.nextInt()-1;
int v = scanner.nextInt()-1;
HashSet<Integer> uNeighbors = map.get(u);
if (uNeighbors == null) {
uNeighbors = new HashSet<>();
map.put(u, uNeighbors);
}
uNeighbors.add(v);
HashSet<Integer> vNeighbors = map.get(v);
if (vNeighbors == null) {
vNeighbors = new HashSet<>();
map.put(v, vNeighbors);
}
vNeighbors.add(u);
}
// Construct the root
Tree root = createSubTree(0, 0, map, values, colors);
return root;
}
private static Tree createSubTree(int nodeIdx, int depth, HashMap<Integer, HashSet<Integer>> map, int[] values, Color[] colors) {
HashSet<Integer> neighbors = map.get(nodeIdx);
if (neighbors.isEmpty()) {
return new TreeLeaf(values[nodeIdx], colors[nodeIdx], depth);
} else {
TreeNode node = new TreeNode(values[nodeIdx], colors[nodeIdx], depth);
for (int neighbor: neighbors) {
HashSet<Integer> neighboursOfNeighbour = map.get(neighbor);
neighboursOfNeighbour.remove(nodeIdx); // Remove the backward edge, so only childs remain
node.addChild(createSubTree(neighbor, depth+1, map, values, colors));
}
return node;
}
}
This approach is overly complicated. Use a simple undirected graph implemented as a directed graph with edges in both directions. Then use standart DFS, and terminate when the vortex has only one neighbour.
Ditto what hammeramr said. I've spent a week on this, finally looked at the discussions, only to find the problem is poorly worded. Copied your code. Will reference you on my github.
Java Visitor Pattern
You are viewing a single comment's thread. Return to all comments →
Java solution - passes 100% of test cases
From my HackerRank solutions.
Useful tutorial for Visitor Pattern However, this problem is more about creating a tree in an obscure format than it is about Visitor patterns.
Common pitfall: The edges of the tree in the provided input are undirected edges. This makes creating a directed and rooted tree challenging.
Let me know if you have any questions.
haha Im going to have to cite you on my github. After seeing your Java solutions its impossible to think of a cleaner way to implement.
If you have time please elaborate on why using a long for result in the ProductOfRedNodesVisitor class passes all tests while using an int only passes the first test.
I have cited you and I could probably figure it out, but I must admit after learning that the problem is poorly worded and doesnt really teach anything new, I copied your code. Please let me know if you would like me to cite your work with a name different than rshaghoulian.
haha thanks :)
just a heads up I eddited my comment :3
I usually post the most up-to-date solutions in my HackerRank solutions. You can cite that if you like, any citation method is fine, I wasn't even expecting one, so thanks.
The code uses a long instead of an int to avoid integer overflow. The maximum value of an int is about 2 billion. The exact value can be respresented in the code as Integer.MAX_VALUE. Any time you multiply a lot of numbers together, you must be careful of avoiding integer overflow. This was a actually a pitfall that my friend came across in an interview.
Since we can have 10000 nodes (according to the problem constraint) where each node can have value up to 1000, multiplying these numbers can easily exceed ~2 billion. Using a long lets us store these larger numbers. If for some reason a long is not big enough, you can use a BigInteger, which is loads of fun and can store numbers of any size.
Thanks man, I'm on the job hunt too. Yeah, I saw that, but I try my best not to look until im done, I need to sharpen my skills futher.
You've already done exactly what I want to do next. Data Structures, algorithims and Cracking the Coding interview.
Anyways, thanks for your help and keep up the good work!
haha! it is loads of fun. lmfao. ILU
Hi, your solution is very neat. I like it. And do you have any second thought on handing one node tree. You didn't actually put anything into values[] and colors[] yet.
Maybe you mean
Nice find. I fixed it by moving the "Handle 1-node tree" code lower so that values and colors have entries in them. Thanks.
input says number of nodes is at least 2. but better is to handle 1 node trees.
you are a genius bro!! saw your code in Java 1D Array(Part 2) and cited you in GitHub too...marvellous work!!
thank you :)
@rshaghoulian..clear solution and easy to understand... I have a doubt that there is no need to remove the reverse edges if we skipped adding them...
(i.e) if we skip this segment
we need not do this..
But if skip the above lines,it produces wrong output.Can u please explain this??
and one more thing..
boolean childHasChild = (grandChildren != null && !grandChildren.isEmpty());
here, I can't figure out the difference between the two conditions "grandChildren != null" and "!grandChildren.isEmpty()" both appear similiar to me but if I OR them instead of AND,obviously it produces wrong output...can you please explain them??
Thanks in advance!!
1) You definitely need to add the reverse edges too because the graph is an undirected graph (even though it's a little unclear from the problem statement). Not adding the reverse edges would mean you are not creating the intended graph so you will get wrong results.
2) If you want to do grandChildren.isEmpty(), it might be the case that grandChildren is null, and that will give a null pointer exception. For this reason, we first make sure that grandChildren != null before using the dot (.) operator on it.
HackerRank solutions.
yeah...think I got it now...Thanks again!!
Hey there. Can you please explain the difference between Node and Leaf? Especially in this part:
A Node is any element in a tree. A leaf is any element in a tree that has no children. The code you pasted above creates a Node or a Leaf accordingly.
HackerRank solutions.
Thank you for explanation
Thanks a lot for nice solution!
My solution always gave me timeout for n>100000 :(
Could you please tell me Why u this
That's from the Problem statement under "Output Format". It has 10^9 + 7 as this number.
HackerRank solutions.
I made a slightly shorter version, but your answer was definitely pointing me to the right direction, so thank you! :) This challenge was way over the top for the original task.
This approach is overly complicated. Use a simple undirected graph implemented as a directed graph with edges in both directions. Then use standart DFS, and terminate when the vortex has only one neighbour.
Ditto what hammeramr said. I've spent a week on this, finally looked at the discussions, only to find the problem is poorly worded. Copied your code. Will reference you on my github.
Its awesome! its so clear and easy to understand
you still reply bruh? are you even active here anymore?