Trace Terminal Company Ownership
Updated
Problem statement
You are given n numbered entities and a target entity. Each entry [company, owner, points] in edges means that owner holds points / 10000 of company. Follow edges from a company toward its owners.
For this exercise, a terminal owner is an entity with no outgoing edges in the supplied data. This is a graph definition only. The effective fraction held by a terminal owner is the sum, over all directed paths from target to that owner, of the product of the edge fractions along the path.
Return a double[] of length n. Entry i is that fraction when i is a terminal owner and is zero otherwise. An unreachable terminal owner has fraction zero. If the target itself is terminal, its fraction is one.
Parallel edges represent separate ownership blocks and contribute separately. Outgoing points for a company sum to at most 10000. Any unlisted fraction is ignored; do not renormalize the listed fractions.
If any directed cycle is reachable from target, return the one-element array [-1.0] instead. An unreachable cycle does not affect the result. Answers are accepted within absolute or relative error 10^-8.
Function
terminalOwnership(n: int, target: int, edges: int[][]) → double[]Examples
Example 1
n = 4target = 0edges = [[0,1,6000],[0,2,4000],[1,3,5000],[2,3,10000]]return = [0.0,0.0,0.0,0.7]Owner 3 receives 0.6 × 0.5 + 0.4 × 1 = 0.7. Entities 0, 1 and 2 have outgoing edges, so their output entries are zero. The unlisted half of entity 1 is not redistributed.
Example 2
n = 3target = 0edges = [[0,1,10000],[1,0,5000],[1,2,5000]]return = [-1.0]The cycle 0 → 1 → 0 is reachable, so return the cycle sentinel even though entity 2 is terminal.
Example 3
n = 4target = 0edges = [[2,3,10000],[3,2,10000]]return = [1.0,0.0,0.0,0.0]The target 0 is terminal and holds fraction one of itself. The cycle between 2 and 3 is unreachable and is ignored.
Constraints
1 <= n <= 100.0 <= target < n.0 <= edges.length <= 1000.- Every edge contains exactly three integers: company, owner, and points.
- Company and owner indices are in
[0, n). 1 <= points <= 10000.- For each company, the sum of its outgoing points is at most
10000, counting parallel edges separately.
More Palantir interview questions
- Map and Accumulate Learning QueriesONSITE INTERVIEW · Seen Oct 2026
- Relational Learning QueriesONSITE INTERVIEW · Seen Apr 2025
- Find Unmet Users With Shared InterestsONSITE INTERVIEW · Seen Mar 2025
- Maximum Profit with Repeated Stock TradesONSITE INTERVIEW · Seen Sep 2024
- Minimum Calls for Repeated API LookupsONSITE INTERVIEW · Seen Oct 2022
- Find Cookable RecipesONSITE INTERVIEW · Seen Nov 2019
- Simulate Multiplayer WarONSITE INTERVIEW · Seen Nov 2019
- Query Words Within K PositionsPHONE SCREEN · Seen Nov 2026
- Basic Item DiscountsOA · Seen Nov 2026
- Optimize Discount Selection Under a Point BudgetOA · Seen Nov 2026
Similar questions at other companies
- Course SchedulePlaud · ONSITE INTERVIEW
- Course ScheduleAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Course ScheduleFlexTrade · ONSITE INTERVIEWFlexTrade interview questions
- Course ScheduleBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Can All Courses Be FinishedC3.ai · ONSITE INTERVIEWC3.ai interview questions
- Course ScheduleNykaa · PHONE SCREENNykaa interview questions
- Course Schedule FeasibilityTesla · PHONE SCREENTesla interview questions
- Can You Finish All Courses?Intuit · OAIntuit interview questions
- Course Schedule Cycle DetectionGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions