Sweeping bushes in Java | Discover ways to Grasp Software program Engineering, DevOps and Cloud


The problem

You’ll be given an inventory of strings representing nodes in a rooted tree. A visible illustration of a quite simple rooted tree may very well be:

        +----+
        |root|
        ++--++
         |  |
    +----+  +----+
    v            v
+------+      +------+
|node A|      |node B|
+------+      +------+

On this case, the foundation node has two kids, nodes A and B. A extra complicated instance could be:

        +----+
        |root|
        ++--++
         |  |
    +----+  +----+
    v            v
+------+      +------+
|node A|      |node B|
+--+---+      +------+
   |
   +-------------+
   v             v
+------+      +------+
|Node C|      |node D|
+------+      +------+

Right here, The foundation has two kids (nodes A and B), and node A in flip additionally has two kids (nodes C and D). Every of those node strings comprises three comma-separated values within the given order:

  • a singular, non-zero size, alphanumeric node id
  • the id of its father or mother node
  • its standing, which can both be “legitimate” or “invalid”

The foundation node of a tree all the time has an empty string as its father or mother id. The easy instance from above could be represented by the next listing (assuming all nodes have the standing “legitimate”):

["root,,valid", "node A,root,valid", "node B,root,valid"]

The extra complicated instance would outcome within the listing

["root,,valid", "node A,root,invalid", "node B,root,valid", "node C,node A,valid", "node D,node A,valid"]

This instance assumes that each one nodes aside from A have the standing “legitimate”.

Process

The purpose of this problem is to take away the subtrees of all invalid nodes from the tree and return the set of ids of the remaining tree nodes.

  • An invalid node is one whose standing equals “invalid”.
  • “Eradicating the subtree” signifies that it is best to each take away the invalid nodes in addition to all of their descendants (i.e. their kids, the youngsters of their kids and so forth).

The anticipated outcome set for the extra complicated instance would therefore comprise the next strings in arbitrary order:

["root", "node B"]

Notes

The listing all the time represents a sound tree. Which means that

  • there is just one root node within the listing
  • the father or mother id of every node will correspond to the id of one other node within the listing (aside from the foundation node, after all, whose father or mother id is an empty string)
  • there are not any cycles within the tree

The nodes within the listing could also be in any order, irrespectively of their father or mother/little one relations.

The lists might comprise a lot of nodes. If any check fails due to a timeout, this possible implies that whereas your answer is formally right, it’s too inefficient.

The answer in Java code

Possibility 1:

import java.util.*;

public class SweepingTrees {

    public Set<String> determineValidIds(Listing<String> dirtyTree) {
        Map<String,Listing<String>> nodes = new HashMap<>();
        dirtyTree.stream()
                 .filter( s -> !s.endsWith(",invalid"))
                 .map(s -> s.break up(","))
                 .forEach(sArr -> nodes.computeIfAbsent(sArr[1], ok -> new ArrayList<String>())
                                       .add(sArr[0]) );
        
        Set<String> out = new HashSet<>();
        Stack<String> stk = new Stack<>();
        stk.add("");
        whereas (!stk.isEmpty()) {
            Listing<String> subNodes = nodes.get(stk.pop());
            if (subNodes==null) proceed;
            out.addAll(subNodes);
            stk.addAll(subNodes);
        }
        return out;
    }
}

Possibility 2:

import java.util.*;
import static java.util.stream.Collectors.toMap;

public class SweepingTrees {

  public Set<String> determineValidIds(Listing<String> dirtyTree) {
        Set<String> outcome = new LinkedHashSet<>();
 
        if (!dirtyTree.comprises("root,,legitimate")) return outcome;
    
        Map<String, String> treeMap = new HashMap<>();
        for (String s : dirtyTree) {
            String[] itemSplit = s.break up(",");
            if (itemSplit[2].equals("legitimate")) {
                treeMap.put(itemSplit[0], itemSplit[1]);
            }
        }

        for (Map.Entry<String, String> entry : treeMap.entrySet()) {
            String key = entry.getKey();
            String worth = entry.getValue();
            if (worth.equals("")) {
                outcome.add(key);
            }else if (treeMap.containsKey(worth)) {
                if (checkKey(worth, treeMap)) outcome.add(key);
            }
        }
        return outcome;
    }

    public static boolean checkKey(String string, Map<String, String> map) {
        if (string.equals("root")) return true;
        if (map.containsKey(string)) {
            if (checkKey(map.get(string), map)) return true;
        }
        return false;
    }
  
}

Possibility 3:

import java.util.Listing;
import java.util.Set;
import java.util.HashSet;

public class SweepingTrees {

  public Set<String> determineValidIds(Listing<String> dirtyTree) {
    Set<String> legitimate = new HashSet<>(); 
    Set<String> invalid = new HashSet<>(); 
    
    for(String node : dirtyTree) {
      if(node.substring(node.lastIndexOf(",") + 1).equals("invalid") && 
        node.substring(0, node.indexOf(",")).equals("root"))
          return new HashSet<>();
      if(invalid.comprises(node.substring(node.indexOf(",") + 1, node.lastIndexOf(","))) || 
        node.substring(node.lastIndexOf(",") + 1).equals("invalid")) {
        invalid.add(node.substring(0, node.indexOf(",")));
      } else {
        legitimate.add(node.substring(0, node.indexOf(",")));
      }
    }
    
    return legitimate;
  }
}

Take a look at instances to validate our answer

import static org.junit.Assert.assertEquals;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Listing;
import java.util.Set;

import org.junit.Take a look at;

public class SweepingTreesExampleTest {
	
	@Take a look at
	public void test1() {
		Listing<String> tree = Arrays.asList("root,,legitimate", "invalid little one,root,invalid", "legitimate little one,root,legitimate");
		Set<String> expectedIds = new HashSet<>(Arrays.asList("root", "legitimate little one"));
		
		Set<String> cleanedIds = new SweepingTrees().determineValidIds(tree);
		
		assertEquals(expectedIds, cleanedIds);
	}
	
	@Take a look at
	public void test2() {
		Listing<String> tree = Arrays.asList("root,,legitimate", "invalid father or mother,root,invalid", "legitimate little one,invalid father or mother,legitimate", "legitimate child2,invalid father or mother,legitimate");
		Set<String> anticipated = new HashSet<>(Arrays.asList("root"));
		
		Set<String> cleanedTree = new SweepingTrees().determineValidIds(tree);
		
		assertEquals(anticipated, cleanedTree);
	}
	
	@Take a look at
	public void test3() {
		Listing<String> tree = Arrays.asList("root,,legitimate", "invalid father or mother,root,invalid", "legitimate little one,invalid father or mother,legitimate", "legitimate child2,invalid father or mother,legitimate", "legitimate child3,invalid father or mother,legitimate", "legitimate child3,invalid father or mother,legitimate", "legitimate child4,legitimate little one,legitimate", "legitimate father or mother,root,legitimate");
		Set<String> anticipated = new HashSet<>(Arrays.asList("root", "legitimate father or mother"));
		
		Set<String> cleanedTree = new SweepingTrees().determineValidIds(tree);
		
		assertEquals("Didn't delete all kids of invalid entries", anticipated, cleanedTree);
	}
	
}

Related Articles

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Latest Articles