BFS Debugging: Offshore Ownership | Dataford Interview Questions

Debug a broken BFS that finds who owns certain offshore companies, then compute how many shares of each company they own.

Asked in the debugging stage. Bonus: what do you do when there are cycles?

Implement compute_owned_shares(ownership, total_shares, person, targets). ownership maps an owner to pairs of [owned_entity, percentage]. Starting at person, traverse ownership links with BFS. The effective percentage along a path is the product of its edge percentages. For every target company reached, return the effective percentage multiplied by that company’s total shares. Return zero for unreachable targets. Assume BFS’s first discovered path is the applicable path for each entity.

Constraints

1 <= number of entities <= 10^4
0 <= number of ownership links <= 5 * 10^4
0 <= percentage <= 100
Each target has an entry in total_shares
The first BFS-discovered path is the applicable path for each entity

Function Signature

def compute_owned_shares(ownership, total_shares, person, targets):

Your question is BFS Debugging: Offshore Ownership. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Debug a broken BFS that finds who owns certain offshore companies, then compute how many shares of each company they own.

Asked in the debugging stage. Bonus: what do you do when there are cycles?

Constraints

1 <= number of entities <= 10^4
0 <= number of ownership links <= 5 * 10^4
0 <= percentage <= 100
Each target has an entry in total_shares
The first BFS-discovered path is the applicable path for each entity

Function Signature

def compute_owned_shares(ownership, total_shares, person, targets):

Your question is BFS Debugging: Offshore Ownership. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.