Katkat
Back

Find the Highest-Cost Top-Level Job

CollegevineSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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:

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?