Fewest Cache Fetches
Hard About 45 min Free, no account needed
Use tomorrow's requests to find the smallest possible number of cache misses today.
The brief
A replay tool has the complete request log from a finished job. It wants to measure how few fetches a cache could have made with perfect knowledge of the remaining requests.
Implement int Solve(int[] requests, int capacity). The cache starts empty and can hold at most capacity distinct item IDs. Process requests in their given order:
- If the requested item is cached, serve it without a fetch.
- Otherwise, fetch it once. If capacity is positive, the fetched item must enter the cache. When the cache is full, evict a currently cached item first.
- With capacity zero, every request requires a fetch and nothing is retained.
You may choose evictions using the entire log. You cannot reorder requests, prefetch an item, or bypass insertion on a miss. Return the minimum possible total number of fetches.
For Solve([1, 2, 3, 1, 2, 3], 2), return 4. Fetch 1 and 2. To load 3, evict 2; the next request for 1 is then a hit. Fetch 2, evict 1, and serve the final 3 from cache. That costs four fetches. Evicting the least recently requested item at every miss would cost six.
For Solve([8, 8, 8], 0), return 3. With capacity 1, the same log needs only 1 fetch. An empty log returns 0.
There are at most 200,000 requests, 0 <= capacity <= 200,000, and IDs may be any signed 32-bit integer. IDs identify items; their numeric order has no significance. Do not change the request array.
Starter code
public class Solution
{
public int Solve(int[] requests, int capacity)
{
// Return the minimum fetch count with the complete future log available.
throw new System.NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Greedy algorithms
- Make the locally best choice when an exchange argument proves it stays globally optimal.
- Heaps and priority queues
- Pull the smallest or largest pending item cheaply for top-k, scheduling and eviction.
Related katas
- Magnetic Force Between Two Balls Hard Free Place m balls in baskets to maximize the smallest gap between any two.
- Text Justification Hard Free Greedily pack words into fully justified lines, spaces and all.
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Container With Most Water Medium Free Pick two lines that, with the x-axis, hold the most water.