CareerCup

You are given a directed cyclic graph represented by an adjacency matrix. The graph has at least one terminal node (i.e. the node with no outgoing edges).

Each edge of the graph is assigned a positive integer representing a probability of taking this edge. E.g. if you have 3 outgoing edges with numbers 3, 2, and 4, this means that the prob. of taking these edges are: 3/9, 2/9 and 4/9, respectively.

You need to find the probability of reaching each terminal node from the starting node 0.

Example:
adjacency matrix 5x5:

m = {{0 1 0 0 1},
        {0 0 3 2 0},
        {4 0 0 1 0},
        {0 0 0 0 0},
        {0 0 0 0 0}}

so we have two terminal nodes here: 3 and 4
we can take the following paths:
0 -> 1 -> 3 = probability: 1/2*2/5 = 1/5
0 -> 1 -> 2 -> 3 = probability: 1/2*3/5*1/5 = 3/50
0 -> 1 -> 2 -> 0 -> 1 -> 3 ... and so on

or to the node 4:
0 -> 4: probability: 1/2
0 -> 1 -> 2 -> 0 -> 4: probability 1/2*3/5*4/5*1/2 = 3/25

and so on, summing up probabilities of all possible paths we get:
total probability to reach node 3: 13/38
total probability to reach node 4: 25/38

Say that you have p1(Child) - > a & b and p2 (Child) -> c & d. Which return list p1 and p2 child and see p1 and p2 are related. We need to check if they going over the tree.

Inupt assumption is : p1 -> a & b
p2 -> c & d
a - it own parent & b - it own parent
c - it own parent & d - it own parent and so on.

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 positive integer identifier.
<p>
For example, in this diagram, 3 is a child of 1 and 2, and 5 is a child of 4:
<p>
1 2 4 15
\ / / | \ /
3 5 8 9
\ / \ \
6 7 11
<p>
<p>
Sample input/output (pseudodata):
<p>
parentChildPairs = [
(1, 3), (2, 3), (3, 6), (5, 6), (15, 9),
(5, 7), (4, 5), (4, 8), (4, 9), (9, 11)
]
<p>
<p>
Write a function that takes this data as input and returns two collections: one containing all individuals with zero known parents, and one containing all individuals with exactly one known parent.
<p>
<p>
Output may be in any order:
<p>
findNodesWithZeroAndOneParents(parentChildPairs) => [
[1, 2, 4, 15], // Individuals with zero parents
[5, 7, 8, 11] // Individuals with exactly one parent
]
<p>
n: number of pairs in the input

public static void main(String[] argv) {
        int[][] parentChildPairs = new int[][]{
                {1, 3},
                {2, 3},
                {3, 6},
                {5, 6},
                {15, 9},
                {5, 7},
                {4, 5},
                {4, 8},
                {4, 9},
                {9, 11}};
        findNodesWithZeroAndOneParents(parentChildPairs);
    }

    public static void findNodesWithZeroAndOneParents(int[][] parentChildPairs) {
        Map<Integer, List<Integer>> childAncestor = new HashMap<>();
        for (int[] parentChildPair : parentChildPairs) {
            int parent = parentChildPair[0];
            int child = parentChildPair[1];
            if (!childAncestor.containsKey(child)) {
                childAncestor.put(child, new ArrayList<>());
            }
            List<Integer> parentValue = childAncestor.get(child);
            parentValue.add(parent);
            childAncestor.put(child, parentValue);
        }
        System.out.println(childAncestor.toString());

        dfs(childAncestor);
    }

    private static void dfs(Map<Integer, List<Integer>> childAncestor) {
        Set<Integer> childerOneParent = new HashSet<>();
        Set<Integer> parentWithOutParent = new HashSet<>();
        for (Map.Entry<Integer, List<Integer>> parent : childAncestor.entrySet()) {
            if (parent.getValue().size() == 1) {
                childerOneParent.add(parent.getKey());
            }
            List<Integer> part = parent.getValue();
            for (Integer p : part) {
                if (!childAncestor.containsKey(p)) {
                    parentWithOutParent.add(p);
                }
            }
        }
        System.out.println(childerOneParent.toString() + " / " + parentWithOutParent.toString());
    }
}

22) What is the advantage of collapsing white space?

21) What are Web Workers?