0
\$\begingroup\$

I am preparing for online coding assessment, where I have come across a question to write an algorithm to find the list of direct parents and transitive parents for each vertex in a directed acyclic graph.

Input: The first line is a number indicating how many lines follow. On each following line of input, the first item represents a module in our dependency graph, then a comma, followed by all of it's children also separated by commas. There is no circles in the dependency graph. For the example, the input looks like this:

5

A,E,N,S

S,H,N

E,N

H

N

Output

A,0(no parents)

E,1(A is direct parent)

H,2(S direct parent, A transitive parent)

N,3(A,S,E are direct parents)

S,1(A is a direct parent)

public class Solution {
    
    public static void main(String[] args) {
        List<List<Character>> list = new ArrayList<>();
        list.add(Arrays.asList(new Character[]{'A','E','N','S'}));
        list.add(Arrays.asList(new Character[]{'S','H','N'}));
        list.add(Arrays.asList(new Character[]{'E','N'}));
        list.add(Arrays.asList(new Character[]{'H'}));
        list.add(Arrays.asList(new Character[]{'N'}));
        Solution sol = new Solution();
        sol.calculateCost(5,list);
    }

    public void calculateCost(int number, List<List<Character>> list){
        Map<Character,Node> nodeMap = constructGraph(list);
        StringBuilder sb = new StringBuilder();
        for(Map.Entry<Character,Node> entry: nodeMap.entrySet()){
            sb.append(entry.getKey());
            sb.append(",");
            sb.append(entry.getValue().allParentCount()+1);
            sb.append(" ");
        }
        System.out.println(sb.toString().trim());
    }

    private Map<Character,Node> constructGraph(List<List<Character>> list){
        Map<Character,Node> nodeMap = new HashMap<>();

        for(List<Character> edges : list){
            Character sourceVertex = edges.get(0);
            Node node = new Node(sourceVertex);
            nodeMap.put(sourceVertex,node);
        }
        for(List<Character> edges : list){
            Character sourceVertex = edges.get(0);
            Node parentNode = nodeMap.get(sourceVertex);
            List<Character> destinationVertices = edges.subList(1,edges.size());
            for(Character destinationVertex : destinationVertices){
                nodeMap.get(destinationVertex).parents.add(parentNode);
            }
        }
        return nodeMap;
    }
}


class Node{
    Character vertex;
    Set<Node> parents = new HashSet<>();

    Node(Character vertex){
        this.vertex = vertex;
    }
    public void addParent(Node parent){
        this.parents.add(parent);
    }
    public int allParentCount(){
        return allParents().size();
    }
    public Set<Node> allParents(){
        Set<Node> allParents = new HashSet<>();
        allParents.addAll(parents);
        for(Node parent : parents){
            allParents.addAll(parent.allParents());
        }
        return allParents;
    }
}

Is there any solution with better time complexity/space complexity?

\$\endgroup\$
1
  • \$\begingroup\$ You say that you exceeded some time limit. What is the time limit? \$\endgroup\$
    – Xtros
    Jan 3 at 1:52

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.