Sweeping bushes in Java | Software program Enginering Authority

The problem

You’ll be given a listing of strings representing nodes in a rooted tree. A visible illustration of a quite simple rooted tree might be:

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

On this case, the basis node has two kids, nodes A and B. A extra advanced 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 accommodates three comma-separated values within the given order:

• a singular, non-zero size, alphanumeric node id
• the id of its mum or dad 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 mum or dad id. The straightforward instance from above could be represented by the next checklist (assuming all nodes have the standing “legitimate”):

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

The extra advanced instance would end result within the checklist

["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 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 you need to each take away the invalid nodes in addition to all of their descendants (i.e. their kids, the kids of their kids and so forth).

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

["root", "node B"]

Notes

The checklist all the time represents a sound tree. Because of this

• there is just one root node within the checklist
• the mum or dad id of every node will correspond to the id of one other node within the checklist (other than the basis node, after all, whose mum or dad id is an empty string)
• there are not any cycles within the tree

The nodes within the checklist could also be in any order, irrespectively of their mum or dad/little one relations.

The lists might include a lot of nodes. If any check fails due to a timeout, this doubtless signifies 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.cut 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> end result = new LinkedHashSet<>();
 
        if (!dirtyTree.accommodates("root,,legitimate")) return end result;
    
        Map<String, String> treeMap = new HashMap<>();
        for (String s : dirtyTree) {
            String[] itemSplit = s.cut 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("")) {
                end result.add(key);
            }else if (treeMap.containsKey(worth)) {
                if (checkKey(worth, treeMap)) end result.add(key);
            }
        }
        return end result;
    }

    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.accommodates(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 circumstances 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.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 mum or dad,root,invalid", "legitimate little one,invalid mum or dad,legitimate", "legitimate child2,invalid mum or dad,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 mum or dad,root,invalid", "legitimate little one,invalid mum or dad,legitimate", "legitimate child2,invalid mum or dad,legitimate", "legitimate child3,invalid mum or dad,legitimate", "legitimate child3,invalid mum or dad,legitimate", "legitimate child4,legitimate little one,legitimate", "legitimate mum or dad,root,legitimate");
		Set<String> anticipated = new HashSet<>(Arrays.asList("root", "legitimate mum or dad"));
		
		Set<String> cleanedTree = new SweepingTrees().determineValidIds(tree);
		
		assertEquals("Didn't delete all kids of invalid entries", anticipated, cleanedTree);
	}
	
}