Maximize watch time under adjacency constraint

Q: Maximize watch time under adjacency constraint

This Coding & Algorithms question for a Data Engineer role evaluates dynamic programming and sequence-optimization skills by requiring selection of a subsequence under a pairwise adjacency constraint on video durations, at a moderate-to-advanced algorithmic abstraction level.

Q: 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.

Question

You are given a sequence of videos in a feed.

Input:
- An integer array duration[1..n] , where duration[i] is the length of video i in seconds.
- An integer A (the user’s attention limit).
Task:
- Select a subset of videos in the original order (i.e., choose a subsequence).
- Let the selected videos be i1 < i2 < ... < ik . The constraint is:
  - For every adjacent pair in the selected subsequence, duration[ij] + duration[ij+1] <= A .
- Maximize the total watch time: sum(duration[ij]) .
Output:
- Return the maximum achievable total watch time.

Follow-up:

Suppose the user is allowed to rewatch the same video multiple times, and the session consists of exactly m selections (so repetitions are allowed, but the number of watched items is capped). How would you modify your approach to compute the maximum total watch time under the same adjacency constraint?

Maximize watch time under adjacency constraint

Quick Overview

Comments (0)