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

The problem

You may be given an inventory of strings representing nodes in a rooted tree. A visible illustration of a quite simple rooted tree could possibly be:

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

On this case, the foundation node has two youngsters, nodes A and B. A extra advanced instance can be:

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

Right here, The basis has two youngsters (nodes A and B), and node A in flip additionally has two youngsters (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 guardian node
• its standing, which can both be “legitimate” or “invalid”

The basis node of a tree at all times has an empty string as its guardian id. The straightforward instance from above can 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 advanced 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 every one nodes other than A have the standing “legitimate”.

Activity

The objective 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’s best to each take away the invalid nodes in addition to all of their descendants (i.e. their youngsters, the youngsters of their youngsters and so forth).

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

["root", "node B"]

Notes

The listing at all times represents a sound tree. Because of this

• there is just one root node within the listing
• the guardian id of every node will correspond to the id of one other node within the listing (other than the foundation node, after all, whose guardian id is an empty string)
• there aren’t any cycles within the tree

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

The lists might include a lot of nodes. If any take a look at fails due to a timeout, this probably signifies that whereas your resolution 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;
  }
}

Check instances to validate our resolution

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.Check;

public class SweepingTreesExampleTest {
	
	@Check
	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);
	}
	
	@Check
	public void test2() {
		Listing<String> tree = Arrays.asList("root,,legitimate", "invalid guardian,root,invalid", "legitimate little one,invalid guardian,legitimate", "legitimate child2,invalid guardian,legitimate");
		Set<String> anticipated = new HashSet<>(Arrays.asList("root"));
		
		Set<String> cleanedTree = new SweepingTrees().determineValidIds(tree);
		
		assertEquals(anticipated, cleanedTree);
	}
	
	@Check
	public void test3() {
		Listing<String> tree = Arrays.asList("root,,legitimate", "invalid guardian,root,invalid", "legitimate little one,invalid guardian,legitimate", "legitimate child2,invalid guardian,legitimate", "legitimate child3,invalid guardian,legitimate", "legitimate child3,invalid guardian,legitimate", "legitimate child4,legitimate little one,legitimate", "legitimate guardian,root,legitimate");
		Set<String> anticipated = new HashSet<>(Arrays.asList("root", "legitimate guardian"));
		
		Set<String> cleanedTree = new SweepingTrees().determineValidIds(tree);
		
		assertEquals("Didn't delete all youngsters of invalid entries", anticipated, cleanedTree);
	}
	
}