How should I practice Root Job with the Largest Total Duration?

Start by reading the full statement, solve the visible examples, then compare the pattern against related College Vine phone screen problems in FastPrep.

Is Root Job with the Largest Total Duration associated with College Vine?

FastPrep tags this as a College Vine phone screen coding practice problem when the problem catalog has that company and stage context.

Root Job with the Largest Total Duration

College Vine● MediumFULLTIMEPHONE SCREEN

Learn

Problem statement

A job file describes a forest of jobs. The equally sized arrays ids, parentIds and durations give one record per position. A parent of -1 represents the source file’s null root parent. Otherwise the parent is another job ID. IDs are unique and the relationships have no cycles.

A job’s total duration is its own duration plus the durations of all descendants. Return the ID of the root with the largest total. Sum the work of every descendant; this is not an elapsed-time or critical-path calculation.

For this exercise, assume input records may arrive in any order, durations are nonnegative integer units, equal totals choose the smaller root ID, and an empty file returns -1. A job has at most fifteen direct children.

Further discussion

Explain how a min-heap of size three can retain the three largest root totals as a self-check. This discussion does not change the required result: return the root with the largest total, not the third largest.

Function

largestRootJob(ids: int[], parentIds: int[], durations: int[]) → int

Examples

Example 1

ids = [10,11,12,20]parentIds = [-1,10,10,-1]durations = [2,4,5,10]return = 10

Descendant sum beats single long root.

Example 2

ids = [7,2]parentIds = [-1,-1]durations = [5,5]return = 2

Tie chooses smaller root identity.

Example 3

ids = []parentIds = []durations = []return = -1

Empty job file.

Constraints

0 <= ids.length = parentIds.length = durations.length <= 512.
IDs are distinct positive integers at most 10^9.
Each parent is -1 or another input ID; the input is an acyclic forest.
Every job has at most 15 direct children.
0 <= durations[i] <= 10^6; totals fit a signed 32-bit integer.