Cheapest Cache TTL Meeting a Freshness SLA
Problem Statement
Choose the largest cache TTL (to save the most cost) such that the fraction of served responses that are stale stays within a freshness SLA, given a trace of requests and underlying-data change times.
Background
A cached entry created at time t is valid until t + ttl. For a request stream (sorted times), the cache serves a key from cache if a valid entry exists (created within ttl of now and after the last data change for that key); otherwise it recomputes and creates a fresh entry. A served-from-cache response is stale if the underlying data changed after the cached entry was created. We are given, per request, whether serving it from a cache of a given ttl would be stale — abstracted as: for candidate ttl values, a function tells us the stale fraction. Concretely: given candidates (sorted ascending ttl values) and a parallel list stale_fraction (the resulting stale fraction at each ttl, non-decreasing in ttl), return the largest ttl whose stale fraction <= sla. If even the smallest exceeds sla, return -1.
Your Task
def best_ttl(candidates, stale_fraction, sla):
- candidates: ascending ttl values; stale_fraction[i] corresponds to candidates[i] and is non-decreasing.
- Return the largest qualifying ttl, or -1.
Input Format
- candidates (list of ints, ascending), stale_fraction (list of floats, non-decreasing), sla (float).
Output Format
- An int (a ttl) or -1.
Sample
print(best_ttl([10, 60, 300], [0.0, 0.02, 0.2], 0.05))
Output:
60
Example:
print(best_ttl([10, 60, 300], [0.0, 0.02, 0.2], 0.05))
60
- We identify the valid range of TTLs by checking which candidates have a stale fraction ≤0.05. The fractions are [0.0,0.02,0.2], so indices 0 and 1 qualify, while index 2 (0.2>0.05) does not.
- To find the largest valid TTL efficiently, we perform a binary search on the sorted
candidateslist [10,60,300], aiming to find the rightmost index where the condition holds. - In the first step, we check the middle element at index 1: the stale fraction is 0.02, which is ≤0.05. Since this is valid, we record
60as a potential answer and search the right half for a larger valid TTL. - In the next step, we check the new middle element at index 2: the stale fraction is 0.2, which is >0.05. This is invalid, so we discard this right half and stop searching further right.
- The search concludes with the last recorded valid candidate, which is the largest TTL meeting the SLA.
- The final output is 60
Constraints:
stale_fractionis non-decreasing in ttl, so qualifying ttls form a prefix.- Return the largest ttl with
stale_fraction <= sla(binary search the prefix). - Return
-1if none qualify.
1. Background Knowledge
This problem sits at the intersection of caching economics and service-level agreements (SLAs). In production systems, a cache entry created at time t with a time-to-live (TTL) of τ is considered valid until t+τ. When the underlying data changes, any cached entry created before that change is stale. Serving stale data can violate freshness guarantees, so systems often impose an SLA: the fraction of responses served from cache that are stale must not exceed a threshold ssla​.
The key insight here is the monotonicity of the stale fraction with respect to TTL. As you increase the TTL, entries live longer, so more of them outlive data changes. Consequently, the stale fraction is a non-decreasing function of TTL. This monotonicity is what makes the problem tractable: instead of checking every candidate, you can exploit the ordered structure to find the boundary where the constraint flips from satisfied to violated.
In practice, you would measure or simulate the stale fraction for various TTLs. Here, that measurement is abstracted away: you are given a sorted list of candidate TTLs and their corresponding stale fractions, and your job is purely to find the optimal TTL under the constraint.
2. Algorithm Approach
Because stale_fraction is non-decreasing and candidates is ascending, the set of valid TTLs (those with stale fraction ≤ sla) forms a prefix of the candidate list. You are looking for the rightmost element in this prefix.
This is a classic binary search scenario. Specifically, you want to find the largest index i such that stale_fraction[i] <= sla. If no such index exists (i.e., even the first element exceeds the SLA), return -1.
Binary search works because the predicate stale_fraction[mid] <= sla is True for a contiguous prefix and False for the remaining suffix. You search for the boundary between these two regions.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.