company ownerships. Data Structure/DFS


  • 0
    M

    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.


  • 0
    Y
    This post is deleted!

  • 0
    J

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


Log in to reply
 

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