At Nimbus Storage, block requests are processed in order, but the retrieval layer can prefetch a limited number of distinct blocks at a time. Given a sequence of requested block IDs and a cache capacity k, write a function that returns the length of the longest contiguous request segment that can be served using at most k distinct block IDs.
This models optimizing retrieval by maximizing the largest request window that fits within the storage system's active block set.
requests: a list of integers representing block IDsk: an integer representing the maximum number of distinct block IDs allowed in the active retrieval windowk distinct valuesExample 1
requests = [1, 2, 1, 2, 3], k = 24[1, 2, 1, 2], which contains only block IDs 1 and 2.Example 2
requests = [4, 4, 4, 4], k = 141 <= len(requests) <= 10^50 <= requests[i] <= 10^90 <= k <= len(requests)requests = [1, 2, 1, 2, 3], k = 2Output4WhyThe longest contiguous segment with at most 2 distinct block IDs is `[1, 2, 1, 2]`.requests = [4, 4, 4, 4], k = 1Output4WhyOnly one distinct block ID appears, so the full request list is valid.requests = [1, 2, 3, 4], k = 2Output2WhyAny valid window can contain at most 2 distinct values, so the maximum length is 2.1 <= requests.length <= 10^50 <= requests[i] <= 10^90 <= k <= requests.lengthThe answer must be computed in O(n) timedef longest_retrieval_window(requests, k):
