Optimize Sequential Block Retrieval | Dataford Interview Questions

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.

Formal Specification

Input:
- requests: a list of integers representing block IDs
- k: an integer representing the maximum number of distinct block IDs allowed in the active retrieval window
Output:
- An integer: the maximum length of a contiguous subarray containing at most k distinct values

Constraints

1 <= requests.length <= 10^5
0 <= requests[i] <= 10^9
0 <= k <= requests.length
The answer must be computed in O(n) time

Function Signature

def longest_retrieval_window(requests, k):

Your question is Optimize Sequential Block Retrieval. 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