Solve several streaming, DAG, and DP tasks

You were asked multiple algorithmic questions.

1) Streaming longest subarray with average S

You receive an infinite stream of integers (can be positive or negative). A real number S is given.

After each new integer arrives, output the longest contiguous subarray within the elements seen so far whose average equals S.

Clarify/assume for the interview version:

• If multiple longest subarrays exist, return any one (or the earliest).
• Output can be the length, or (start_index, end_index) .
• You should process elements online (do not re-scan the entire prefix each time).

2) Task scheduling on a dependency graph (DAG)

You are given N tasks. Each task i has a duration time[i]. Some tasks depend on others, forming a directed acyclic graph (DAG).

(a) Single worker / unlimited worker time computation

Compute the total time required to finish all tasks subject to dependencies.

(Interviewers often clarify one of these variants; state which you’re solving.)

• Variant A: Unlimited parallelism (tasks can run in parallel as long as dependencies are satisfied). Output the minimum makespan .
• Variant B: Single worker (only one task at a time). Output the minimum time (or any valid schedule length).

(b) M parallel workers

Now you have M identical workers that can run tasks in parallel when dependencies are met.

Compute the total completion time.

(Again clarify/assume):

• Either compute the optimal makespan (typically requires small N ), or
• Compute the makespan under a specified policy (e.g., always start any available tasks when a worker is free).

3) Max-revenue ad selection with sliding-window constraint

You have a time-ordered sequence of ads over N time slots. Ad i has revenue r[i].

Choose which ads to show (e.g., pick a subset of positions, keeping the original order) to maximize total revenue, subject to:

• For every consecutive window of T time slots , the total revenue of the shown ads inside that window is ≤ M .

Follow-up:

• How does your approach change if ads can be repeated (i.e., you are allowed to reuse the same ad creative/type multiple times in the overall schedule)?