# company ownerships. Data Structure/DFS

• This question was given to me during a phone interview from a hot bay area startup: Rubrik. It goes something like this
If:
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];
else
visit(source);
return A[source][target];

visit(source)
for i = 0 ~ N {
if (i != source && !visited.contains(i) && A[source][i] != 0)
visit(i)
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.

• This post is deleted!

• 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)?

• @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()
for edge in ownlist:
u, v, w = edge

def visit(source):
if v not in visited:
visit(v)
if j != v and j in adj_map[v]:
visit(source)

if source in visited: