Maximize watch time under adjacency constraint
Company: Bytedance
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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?
Quick Answer: 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.