Katkat
Back

Maximize watch time under adjacency constraint

ByteDanceData Engineer · Technical Screen
HardData EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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?