Find the Highest-Cost Top-Level Job
Company: Collegevine
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a local JSON file, `jobs.json`, containing an array of background job records. Each record has:
- `id`: a unique job identifier
- `parent_id`: the identifier of the parent job, or missing/null for a top-level job
- `duration_ms`: the amount of time this job took to run, in milliseconds
A job may spawn child jobs, and those child jobs may spawn more jobs, forming a forest of job trees. The total cost of a top-level job is defined as:
`its own duration_ms + the duration_ms of all descendant jobs`
Write a function that computes the total cost for every top-level job and returns the top-level job with the largest total cost, along with that cost. If multiple top-level jobs have the same maximum total cost, returning any one of them is acceptable.
Example:
```text
A: 5ms
├── B: 1ms
└── C: 3ms
```
The total cost for `A` is `5 + 1 + 3 = 9ms`.
Follow-up: What improvements would you make for large inputs or production use, such as avoiding recursion-depth issues, handling malformed data, detecting cycles, or improving performance?
Quick Answer: This question evaluates the ability to process hierarchical JSON data, aggregate durations across tree-structured job relationships, and reason about robustness and scalability concerns such as malformed input handling and performance for large datasets.
Return [top_level_job_id,total_cost] for the root job with the largest own-plus-descendant duration.
Constraints
- Jobs are dictionaries with id, optional parent_id, and duration_ms.
- If totals tie, return the root with the smallest string id for deterministic grading.
Examples
Input: ([{"id":"A","duration_ms":5},{"id":"B","parent_id":"A","duration_ms":1},{"id":"C","parent_id":"A","duration_ms":3}],)
Expected Output: ['A', 9]
Explanation: A includes both descendants.
Input: ([{"id":"A","duration_ms":5},{"id":"B","duration_ms":5}],)
Expected Output: ['A', 5]
Explanation: Ties are broken by smallest id string.
Input: ([],)
Expected Output: None
Explanation: No jobs returns None.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.