Sliding Window Optimization | Dataford Interview Questions

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 question is Sliding Window Optimization. Start with the requirements in the Question tab.

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

Problem