How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at Bytedance during technical interviews.

Maximize watch time under adjacency constraint

Quick Overview

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.

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.

Part 1: Maximize Subsequence Watch Time Under Adjacent Duration Limit

You are given a feed of videos in a fixed order. The length of video i is duration[i]. Choose any subsequence of videos, preserving the original order. For every two adjacent videos in your chosen subsequence, the sum of their durations must be at most A. Return the maximum possible total watch time. A single selected video is always valid because it has no adjacent selected pair. Selecting no videos is allowed and has total watch time 0.

Constraints

0 <= len(duration) <= 200000
0 <= duration[i] <= 10^9
0 <= A <= 10^9
The answer fits in a signed 64-bit integer.

Examples

Input: ([], 10)

Expected Output: 0

Explanation: There are no videos, so the best total watch time is 0.

Input: ([12], 5)

Expected Output: 12

Explanation: A single video has no adjacent selected pair, so it can be watched even though its duration exceeds A.

Hints

Let dp[i] be the maximum total watch time of a valid subsequence that must end at video i.
For video i, you need the best dp[j] among earlier videos j where duration[j] <= A - duration[i]. Maintain these best values by duration and query a prefix maximum.

Part 2: Maximize Exact-Length Watch Session With Rewatching

You are given a set of videos by duration. A watch session consists of exactly m selections. At each selection, you may choose any video from the list, and the same video may be chosen multiple times. The original feed order does not restrict the session. For every two consecutive selections, the sum of their durations must be at most A. Return the maximum possible total watch time for exactly m selections. If no valid session of exactly m selections exists, return -1. If m is 0, the empty session is valid and has total watch time 0.

Constraints

0 <= len(duration) <= 2000
0 <= m <= 2000
0 <= duration[i] <= 10^9
0 <= A <= 10^9
The answer fits in a signed 64-bit integer.

Examples

Input: ([], 10, 0)

Expected Output: 0

Explanation: Exactly zero selections means the empty session, which is valid.

Input: ([12, 3], 5, 1)

Expected Output: 12

Explanation: With only one selection, there is no adjacency constraint, so choose the longest video.

Hints

Use dynamic programming over the session length: dp[t][d] can represent the best total for a length-t session ending with duration d.
For each next duration d, the previous duration must be at most A - d. Sorting distinct durations lets you use prefix maximums to speed up each transition round.