company ownerships. Data Structure/DFS

  • 2

    This question was given to me during a phone interview from a hot bay area startup: Rubrik. It goes something like this
    Company A owns 10% of Company B,
    Company B owns 5% of Company C,
    Company B owns 5% of Company D,
    Company A owns 2% of Company C

    then, how much of Company C does A own? 2.5%

    My task was to represent the given data with the correct data structure (which I chose a 2-d array, aka. 'grid'), and then write the function:

    double getOwnership(source, target) => getOwnership(A, C) would give 0.025 in this instance. Pay attention there could be multi-layer ownership, A owns part of B, B owns part of C, C owns part of D, and then A also owns part of D...

    I gave a dfs solution during the interview but couldn't get it 100% right. Below if what I wrote up after the interview. I also assumed there would not be any cyclic ownership, meaning A owns B, B will not own A. Since that will cause a cyclic in the dfs, and cause infinite ownership. (But not 100% sure if this assumption should hold, since maybe if A owns B, and B also owns A, we simply do not explore that relationship? Please comment if someone has seen the problem)

    Here is the pseudo-code I have came up with:
    N: number of companies;
    Represent the ownership grid to: A = int[N][N]; (assume given)
    Also represent a visited array: visited = {}; (hash set)

    getOwnership(source, target):
    if (visited.contains(source))
    return A[source][target];
    return A[source][target];

    for i = 0 ~ N {
    if (i != source && !visited.contains(i) && A[source][i] != 0)
    for j = 0 ~ N {
    if (j != node && j != i && A[i][j] != 0)
    A[node][j] += A[node][i]*A[i][j];

    If you have seen similar problem or very familiar with dfs, please share your opinion.

  • 0
    This post is deleted!

  • 0

    I got a two 'for' nested loops solution and time complexity is O(n^2). The input is a 2D array in which you are supposed to enter weight value data manually. An easy way to understand. It seems that the time complexity of your solution is much better. Is that O(n)?

  • 0

    @martin20 in your proposed solution did you mean "source" instead of "node" in the following lines?

    if (j != node && j != i && A[i][j] != 0)
    A[node][j] += A[node][i]*A[i][j];

    Here is my implementation of the DFS idea. Yes I have assumed that the graph is acyclic as well.

    # company ownerships
    from collections import defaultdict
    def get_ownership(ownlist, source, target):
        ownlist = example [(A, B, 10), (A, C, 5) ....]
        source = example A 
        target = example C
        visited = set()
        adj_map = defaultdict(dict)
        for edge in ownlist:
            u, v, w = edge
            adj_map[u][v] = w*1.0/100.0
        #print adj_map
        def visit(source):
            for v in adj_map[source].keys():
                if v not in visited:
            for j in adj_map[source].keys():
                if j != v and j in adj_map[v]:
                    adj_map[source][j] += adj_map[source][v] * adj_map[v][j]
            print "from source={} adj_map {}".format(source, adj_map)
        if source in visited:
            return adj_map[source].get(target, 0)
    print get_ownership([('A', 'B', 10.0), ('A', 'C', 2.0), ('B', 'C', 5.0), ('B', 'D', 2.0)], 'A', 'C') # ans 0.025
    print get_ownership([('A', 'B', 10.0), ('A', 'C', 2.0), ('B', 'C', 5.0), ('B', 'D', 2.0)],'A', 'D') # ans 0
    print get_ownership([('A', 'B', 10.0), ('A', 'C', 2.0), ('B', 'C', 5.0), ('B', 'D', 2.0), ('D', 'C', 50.0)],
                  'A', 'C') # ans 0.026

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.