How should I practice Earliest Dataset Readiness in a Pipeline?

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

Is Earliest Dataset Readiness in a Pipeline associated with xAI?

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

Problem · Graph

Earliest Dataset Readiness in a Pipeline

Learn this problem

● Medium

xAIFULLTIMEPHONE SCREEN

Problem statement

You are given a data pipeline containing n tasks. Task i consumes every dataset in taskInputs[i], produces taskOutputs[i], and takes durations[i] time units after it starts.

A dataset that is consumed but is not produced by any task is an external input and is available at time 0. A task starts as soon as all its input datasets are available. Tasks have unlimited parallel workers, so one task never delays an otherwise-ready task. Its output becomes available exactly durations[i] time units after it starts.

Return the earliest time when targetDataset is available. The target may itself be an external input.

Function

earliestDatasetReadyTime(taskInputs: String[][], taskOutputs: String[], durations: int[], targetDataset: String) → int

Examples

Example 1

taskInputs = [["d0","d1","d2"],["d1","d2"],["d2","d3"],["d0","d3","d4"]]taskOutputs = ["d3","d4","d5","d6"]durations = [30,15,100,60]targetDataset = "d6"return = 90

d3 and d4 finish at times 30 and 15. The task producing d6 waits for both, starts at 30, and finishes at 90. The slower d5 branch is irrelevant to the target.

Example 2

taskInputs = [["seed"],["a"]]taskOutputs = ["a","b"]durations = [10,20]targetDataset = "seed"return = 0

seed is not produced by a task, so it is an external dataset available at time 0.

Constraints

1 <= n <= 200000.
taskInputs.length == taskOutputs.length == durations.length == n.
1 <= taskInputs[i].length, and the total number of consumed-dataset entries is at most 400000.
Every task output name is unique, and all dataset names are nonempty printable ASCII strings of length at most 50.
1 <= durations[i] <= 10000.
The task dependency graph is acyclic.
The earliest target readiness time fits in a signed 32-bit integer.