Question:
Suppose we have some input data describing a graph of relationships between parents and children over multiple generations. The data is formatted as a list of (parent, child) pairs, where each individual is assigned a unique integer identifier.
|
1 2 3 4 5 |
1 2 4 \ / / \ 3 5 8 \ / \ \ 6 7 9 |
Write a method that takes a list of parent – child tuples and x number. It returns all the nodes having a parent count equals to x.
Input : [ [1, 3], [2, 3], [3, 6], [5, 6], [5, 7], [4, 5], [4, 8], [8, 9]] and 0
Sample output : 1, 2, 4
Input : [ [1, 3], [2, 3], [3, 6], [5, 6], [5, 7], [4, 5], [4, 8], [8, 9]] and 1
Sample output : 8, 7, 9
Input : [ [1, 3], [2, 3], [3, 6], [5, 6], [5, 7], [4, 5], [4, 8], [8, 9]] and 2
Sample output : 3, 5, 6
Solution:
Key to solving this question is to come up with a (N+1) x N matrix. N is the number of nodes. An extra row is to store the sum of the column. The column of this matrix represents the child node and row represents parent nodes. For each input pair value, you can mark 1 at relevant position in a matrix. For example, [1, 3] suggest matrix[1][3] =1. So, each 1 in the matrix represents parent to child connection. Once you form this. It is very easy to derive the parent count. Each column sum is the total number of parents pointing to that child.
For this solution, have considered -1 as the parent value for the root nodes. So, if you have a root node, it will have a parent value as -1 and that is the reason you will see -1 check in the code.
Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
package interviewque; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class FindChildren { public static void main(String[] args){ /* 1 2 4 \ / \ / \ 3 5 8 \ / \ \ 6 7 9 */ List<Node> nodeList = new ArrayList<Node>(); nodeList.add(new Node(-1, 1)); nodeList.add(new Node(-1, 2)); nodeList.add(new Node(-1, 4)); nodeList.add(new Node(1, 3)); nodeList.add(new Node(2, 3)); nodeList.add(new Node(2, 5)); nodeList.add(new Node(4, 5)); nodeList.add(new Node(4, 8)); nodeList.add(new Node(3, 6)); nodeList.add(new Node(5, 6)); nodeList.add(new Node(5, 7)); nodeList.add(new Node(8, 9)); printNodesByParent(nodeList, 2); printNodesByParent(nodeList, 1); printNodesByParent(nodeList, 0); } public static void printNodesByParent(List<Node> nodeList, int parent){ Map<Integer, Integer> nodeIndexMap = scanNodes(nodeList); Map<Integer, Integer> indexNodeMap = inverseMap(nodeIndexMap); int[][] graph = new int[nodeIndexMap.size()+1][nodeIndexMap.size()+1]; for(Node node : nodeList){ if(node.getParent() != -1){ graph[nodeIndexMap.get(node.getParent())][nodeIndexMap.get(node.getValue())] = 1; } } for(int j = 0; j < graph[0].length - 1; j++){ int sum = 0; for(int i = 0; i < graph.length - 1; i ++){ sum += graph[i][j]; } graph[graph.length - 1][j] = sum; } /* Uncomment it to print matrix for(int i = 0;i < graph.length; i++){ for(int j = 0; j < graph[0].length; j++){ System.out.print(graph[i][j] + " "); } System.out.println(); }*/ System.out.println("Nodes with " + parent + " parent "); for(int i = graph.length - 1, j = 1; j < graph[0].length - 1 ; j++){ if(graph[i][j] == parent){ System.out.print(indexNodeMap.get(j) +" "); } } System.out.println(); } public static Map<Integer, Integer> inverseMap(Map<Integer, Integer> inputMap){ Map<Integer, Integer> indexNodeMap = new HashMap<Integer, Integer>(); for(Map.Entry<Integer, Integer> entry : inputMap.entrySet()){ indexNodeMap.put(entry.getValue(), entry.getKey()); } return indexNodeMap; } public static Map<Integer, Integer> scanNodes(List<Node> nodeList){ Map<Integer, Integer> nodeIndexMap = new HashMap<Integer, Integer>(); nodeIndexMap.put(-1, 0); int index = 1; for(Node node: nodeList){ if(!nodeIndexMap.containsKey(node.getValue())){ nodeIndexMap.put(node.getValue(), index); index++; } } return nodeIndexMap; } } class Node { int parent = -1; // parent value with -1 is root int value = 0; public Node(int parent, int value){ this.parent = parent; this.value = value; } public int getParent(){ return parent; } public int getValue(){ return value; } } |
Git Url: FindChildren.java
Complexity: O( n * n ). As we need to traverse entire matrix for the column sum.