Sliding Window Optimization

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Sliding Window Optimization. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

During a TikTok Shop live stream, product IDs are recorded in viewing order. Find the longest contiguous segment containing at most k distinct product IDs.

Use a sliding window that expands to include new products and shrinks from the left whenever the window contains more than k distinct IDs.

Formal Specification

Implement longest_product_segment(product_ids, k).

Input: product_ids, a list of integers representing product IDs, and k, a positive integer limit on distinct products.
Output: An integer representing the maximum length of a contiguous segment with at most k distinct product IDs.

Constraints

1 <= len(product_ids) <= 10^5
1 <= product_ids[i] <= 10^9
1 <= k <= len(product_ids)

Function Signature

def longest_product_segment(product_ids, k):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output