How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Google during technical interviews.

Solve several streaming, DAG, and DP tasks

Q: Solve several streaming, DAG, and DP tasks

This multi-part question evaluates proficiency in streaming and online algorithms, DAG-based scheduling and parallelism reasoning, and constrained dynamic programming/optimization for sliding-window resource limits, within the Coding & Algorithms domain.

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)?

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)?

Solve several streaming, DAG, and DP tasks

Quick Overview

1) Streaming longest subarray with average `S`

2) Task scheduling on a dependency graph (DAG)

(a) Single worker / unlimited worker time computation

(b) `M` parallel workers

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

Comments (0)

Solve several streaming, DAG, and DP tasks

Quick Overview

1) Streaming longest subarray with average `S`

2) Task scheduling on a dependency graph (DAG)

(a) Single worker / unlimited worker time computation

(b) `M` parallel workers

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

Comments (0)

Solve several streaming, DAG, and DP tasks

Quick Overview