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];

}

}

visited.add(source);

"""

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